Двоично дърво
Двоично дърво в информатиката се нарича дърво с разклоненост 2. Понякога наследниците на всеки връх се определят като ляв и десен. Най-често двоичните дървета се използват за реализация на логаритмични структури от данни като двоично дърво за претърсване или приоритетна опашка.
Двоично дърво за претърсване [редактиране]
Двоичното дърво за претърсване е структура от данни, която служи за съхраняване и намиране на данни по ключ, за който съществува наредба. Данните са разпределни в дървото по следния начин: за всеки връх, всички данни, които се намират в лявото му поддърво имат по-малък ключ, а всички данни, които се намират в дясното поддърво, имат по-голям ключ.
Ефикасност на двоичните дървета за търсене [редактиране]
Средната сложност на операциите добавяне и търсене в двоичните дървета за претърсване е O(logN), където N е броят на елементите, добавени в структурата. Ако елементите се добавят подредени по големина, дървото може да се изроди до свързан списък, което води до сложност O(N). Съществуват алгоритми, които поддържат структурата балансирана и запазват добрите сложности.
Използвана литература [редактиране]
- An Introduction to Data Structures and Algorithms with Java, Glenn W. Rowe, Prentice Hill Europe 1998, ISBN 0-13-857749-8
