Двоично дърво

Двоично дърво в информатиката се нарича дърво с разклоненост 2. При двоичното дърво всеки възел (англ. node) може да има не повече от двама наследници – дъщерни елементи (child nodes) със същата структура, които често биват обособени като „ляв“ (left) и „десен“ (right). Обща практика е даден елемент да пази и референция към своя родителски (parent node) елемент. Всяко двоично дърво има елемент наречен корен (root), на който всички останали са наследници (или наследници на наследниците му). Обикновено с двоичното дървото се работи чрез корена му, който позволява да се достигне всеки друг негов елемент.

Пример за двоично дърво.

Двоично дърво за претърсване

Двоичното дърво за претърсване е структура от данни, която служи за съхраняване и намиране на данни по ключ, за който съществува наредба. Данните са разпределени в дървото по следния начин: за всеки връх, всички данни, които се намират в лявото му поддърво имат по-малък ключ, а всички данни, които се намират в дясното поддърво, имат по-голям ключ.

Ефикасност на двоичните дървета за търсене

Средната сложност на операциите добавяне и търсене в двоичните дървета за претърсване е 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