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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

Двоичните дървета имат широко приложение в информатиката, като ключовите им употреби включват реализацията на логаритмични структури от данни (например двоично дърво за претърсване, приоритетна опашка), алгоритми за прекодиране и компресиране на данни, и не на последно място - за представяне на изрази от двоични операции, каквито са аритметичните действия с числа.

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

Двоично дърво за претърсване[редактиране | edit source]

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

Ефикасност на двоичните дървета за търсене[редактиране | edit source]

Средната сложност на операциите добавяне и търсене в двоичните дървета за претърсване е O(logN), където N е броят на елементите, добавени в структурата. Ако елементите се добавят подредени по големина, дървото може да се изроди до свързан списък, което води до сложност O(N). Съществуват алгоритми, които поддържат структурата балансирана и запазват добрите сложности.

Използвана литература[редактиране | edit source]

  • An Introduction to Data Structures and Algorithms with Java, Glenn W. Rowe, Prentice Hill Europe 1998, ISBN 0-13-857749-8