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

от Уикипедия, свободната енциклопедия
Направо към навигацията Направо към търсенето
Двоично дърво за търсене
Binary search tree.svg
Двоично дърво за търсене с размер 9 и дълбочина 3, с числото 8 като корен. Листата не са показани
Информация
Тип Дърво
Година 1960 г.
Изобретено от П.Ф.Уиндли, А.Д.Бут, А.Д.Т.Колин, и Т.Н.Хибърд
Сложност в O-нотация
Средно Най-лошо
Място O(log n) O(n)
Търсене O(log n) O(n)
Добяване O(log n) O(n)
Изтриване O(log n) O(n)
Двоично дърво за търсене в Общомедия

В информатиката, двоичните дървета за търсене също така наричани подредени или сортирани двоични дървета, са специфичен тип структури които складират „елементи“ (като числа, текст и т.н.) в паметта. Те позволяват бързо търсене, добавяне и премахване на елементи и могат да бъдат използвани за имплементирането на динамични множества от елементи или речници, които позволяват за бързото търсене по ключ (например намиране на телефонния номер на човек по името му).

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

Определение[редактиране | редактиране на кода]

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

Най-голямото предимство на двоичните дървета за търсене пред другите структури от данни е че свързаните с тях сортиращите алгоритми и алгоритми за търсене могат да бъдат много ефективни и лесни за писане.

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

  • Формата на двоичното дърво за търсене зависи изцяло от реда на добавяне и може да дегенерира.
  • Когато се търси или поставя елемент в двоично дърво за търсене, ключът на всеки обходен възел трябва да бъде сверяван със ключа на елемента, който се търси или ще се поставя, т.е. отнема много време да се намери елемент в двоично дърво за търсене.
  • Ключовете в двоичното дърво за търсене може да са дълги и времето за изпълнение на програмата да се увеличи.
  • След голям брой произволни преплетени операции по добавяне и изтриване, очакваната височина на дървото приближава корен квадратен от броя ключове, √n, което расте много по бърз от log n.

Операции[редактиране | редактиране на кода]

Двоичните дървета за търсене поддържат три главни операции: добавяне на ключове, изтриване на ключове и търсене (проверяване дали даден ключ съществува). Всяка операция изисква компаратор, подпрограма която пресмята реда (линейната подредба) на всеки два ключа. Този компаратор може да бъде експлицитно или имплицитно определен, в зависимост от езика на който дървото е имплементирано. Компараторите обикновено са функции от тип по-малко от (<) или по-голямо от (>): например a < b или a > b, където a и b са ключове на два възела. В много езици, оператори от типа „>“ и „<“ могат да се използват, само когато се проверяват числови стойности. За всички останали проверки, обикновено се ползват ръчно написани Comparator класове, които дефинират в себе си метод за сравнение на два ключа. Общоприета практика в програмирането е методи за сравнение, да връщат числова стойност като резултат от сравнението. Върнатата стойност трябва да е отрицателно число ако левия ключ е по-малък от десния, положително число ако левия ключ е по-голям от десния и нула ако двата ключа са равни. В Java, метод за сравнение, който сравнява два обекта по естествената им подредба, би изглеждал по следния начин:

1 public int compare(Object left, Object right) {
2     return ((Comparable)left).compareTo(right);
3     //returns 1 if "left" is greater than "right"
4     //returns 0 if "left" equals "right"
5     //returns -1 if "left" is less than "right"
6 }

Търсене[редактиране | редактиране на кода]

Търсенето за определен ключ в двоично дърво за търсене може да е рекурсивен или итеративен процес.

Когато търсим определена стойност в двоично дърво, започваме търсенето от корена и следваме съответно левите или десните възли, в зависимост от търсената стойност, докато не намерим съвпадение на стойностите или до изчерпване на възлите, които можем да следваме. Процедурата може лесно да се обобщи в няколко стъпки:

1. Започваме от корена.

2. Ако дървото е null т.е. не съществува, стойността не е намерена и търсенето е приключило. В противен случай преминаваме към стъпка 3.

3. Сравняваме търсената стойност със стойността на текущия възел.

4. Ако двете стойности съвпадат, значи търсенето е приключило. В противен случай, продължаваме към стъпка 5.

5. Ако търсената стойност е по-малка от стойността на текущия възел, тогава следваме лявата връзка на текущия възел и се връщаме на стъпка 2.

6. Ако търсената стойност е по-голяма, тогава продължаваме търсенето следвайки дясната връзка на възела и се връщаме на стъпка 2.

Алгоритъмът за търсене на стойност, може да се изрази рекурсивно или итеративно, но и в двата случая, в повечето имплементации на двоично дърво, като резултат получаваме или възела, който съдържа търсената стойност или null, ако стойността не е намерена.

Примери за рекурсивно търсене на стойност в двоично дърво:

Java:

 1 public Node search(Object value) {
 2     return search(_root, value);
 3 }
 4 
 5 private Node search(Node node, Object value) {
 6     if (node != null) {
 7         int cmp = _comparator.compare(value, node.getValue());
 8 
 9         if (cmp < 0) {
10             return search(node.getLeft(), value);
11         } else if (cmp > 0) {
12             return search(node.getRight(), value);
13         }
14     }
15 
16     return node; //node == null || cmp == 0
17 }

Python:

1 def search_recursively(key, node):
2     if node is None or node.key == key:
3         return node
4     elif key < node.key:
5         return search_recursively(key, node.left)
6     else:  # key > node.key
7         return search_recursively(key, node.right)
8     return None

Итеративната версия на алгоритъма, би изглеждала по следния начин:

Java:

 1 public Node search(Object value) {
 2     Node node = _root;
 3 
 4     while (node != null) {
 5         int cmp = _comparator.compare(value, node.getValue());
 6 
 7         if (cmp < 0) {
 8             node = node.getLeft();
 9         } else if (cmp > 0) {
10             node = node.getRight();
11         } else { //cmp == 0
12             break;
13         }
14     }
15 
16     return node;
17 }

Python:

 1 def search_iteratively(key, node):
 2     current_node = node
 3     while current_node is not None:
 4         if key == current_node.key:
 5             return current_node
 6         elif key < current_node.key:
 7             current_node = current_node.left
 8         else:  # key > current_node.key:
 9             current_node = current_node.right
10     return None

Понеже в най-лошият случай този алгоритъм трябва да търси от корена на дървото до най-далечното листо, операцията по търсене отнема време пропорционално на височината на дървото (виж терминологията). Средно, двоично дърво за търсене със n възела има O(log n) височина. Обаче в най-лошият случай, двоичните дървета за търсене може да имат O(n) височина, когато небалансираното дърво реално представлява обикновен свързан списък (дегенерирало дърво).

Добавяне[редактиране | редактиране на кода]

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

Добавянето започва, както би започнало стандартно търсене на стойност – ако стойността не е равна на стойността на корена, следваме левия или десния дъщерен възел, докато не достигнем съвпадение на стойности или външен възел (възел равен на null). И в двата случая създаваме нов възел с ключ равен на стойността, която искаме да вмъкнем в дървото. Ако имаме съвпадение на стойности (дървото вече има съществуващ възел, чиято стойност е равна на стойността за вмъкване), то стандартната практика е да добавим новия възел като ляв дъщерен възел на вече съществуващата стойност. В случая, когато нямаме съвпадение на стойности, което е и по-често срещания вариант, то сме стигнали до листо (възел без наследници) и добавяме новата стойност като ляв или десен дъщерен възел, в зависимост от това дали новия възел е с по-голяма или по-малка стойност от стойността на листото. Пример за алгоритъм за добавяне на нова стойност в двоично дърво, използващ итеративно търсене на място за вмъкване, написан на Java, би изглеждал по следния начин:

 1 public Node insert(Object value) {
 2     Node parent = null;
 3     Node node = _root;
 4     int cmp = 0;
 5 
 6     while (node != null) {
 7         parent = node;
 8         cmp = _comparator.compare(value, node.getValue());
 9         if (cmp <= 0) {
10             node = node.getLeft();
11         } else {
12             node = node.getRight();
13         }
14     }
15 
16     Node inserted = new Node(value);
17     inserted.setParent(parent);
18 
19     if (parent == null) {
20         _root = inserted;
21     } else if (cmp < 0) {
22         parent.setSmaller(inserted);
23     } else {
24         parent.setLarger(inserted);
25     }
26 
27     return inserted;
28 }

При добавяне на случайно генерирани стойности, дървото до голяма степен ще запази височина O(log n). Трябва, обаче, да се има предвид, че добавяне на всякакви стойности в подреден формат, неизбежно ще доведе до свеждането на дървото до обикновен свързан списък, което е и най-лошия възможен вариант. В такъв случай, височината на дървото, а с това и средното време за търсене, нараства до O(N). Различни вариации на двойчното дърво за търсене, имат свойството да се самобалансират, което позволява на структурата от данни да запази дървовидната си форма и добрата си производителност при търсене. Вариации на двойчно дърво за търсене, които поддържат балансиране, са на пример Червено-Черни дървета, AVL дървета и Splay дървета. Олекотен вариант на подобна структура от данни, са също и B-Tree дърветата.

Изтриване[редактиране | редактиране на кода]

Има три случая които да се обмислят:

  • Изтриване на възел без деца: просто изтриваме възела от дървото.
  • Изтриване на възел с едно дете: изтриваме възела и го подменяме с детето му.
  • Изтриване на възел с две деца: в този случай, трябва да разменим възела, който ще изтрием, с неговия наследник или предшественик (виж in-order обхождане на дърво). Продължаваме да разменяме възлите, докато не стигнем до ситуация, в която възела остане само с едно дете или без деца. Трябва да се има в предвид, че използването на последователният наследник или на последователният предшественик за всяка инстанция на случаят с две деца може да доведе до небалансирано дърво, затова някой имплементации избират единия или другия в различни случаи.

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

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

Най-сложния вариант за изтриване на възел, е когато възела има две деца. Ако имаме ситуация, в която трябва да изтрием корена на дърво с височина три, трябва да определим точно кой възел, ще използваме за заместник. Реално, можем да използваме както левия, така и десния дъщерен възел на корена, но всеки един от тези два възела има свои собствени наследници, което допълнително затруднява простата замяна на корена с някой от наследниците му. В такава ситуация, намираме наследника или предшественика на корена и разменяме стойностите им. След това, се опитваме да изтрием не корена, а възела, който прие оригиналната стойност на корена. Ако новия възел отново има две деца, то повтаряме процедурата с намиране на наследник/предшественик и смяна на стойности. Повтаряйки процедурата отново и отново, то неизбежно ще попаднем в един от първите два варианта, при които вече преминаваме към разрушаване на връзката родител-дете.

Изтриването на възел с две деца от двоично дърво за търсене. Първо се индентифицира последователният предшественик (най-десният възел в лявото поддърво) 6. Стойността му се копира във възела който изтриваме. Последователният предшественик може вече да бъде лесно изтрит защото има само едно дете. Същият метод работи симетрично като се използва последователният наследник 9.

Анализ по време на работа: Въпреки че тази операция не винаги обхожда дървото до листо, винаги има шанс за това, съответно в най-лошият случай изисква време пропорционално на височината на дървото. Не се изисква повече време дори и когато възела има две деца, тъй като операцията все още продължава надолу по една пътека и не посещава един и същи възел два пъти. Примери за изтриване на стойност в двоично дърво за търсене:

Java:

 1 public Node delete(Object value) {
 2     Node node = search(value);
 3     if (node == null) {
 4         return null;
 5     }
 6 
 7     Node deleted;
 8     if (node.getLeft() != null && node.getRight() != null) {
 9         deleted = node.successor();
10     } else {
11         deleted = node;
12     }
13 
14     Node replacement;
15     if (deleted.getLeft() != null) {
16         replacement = deleted.getLeft();
17     } else {
18         replacement = deleted.getRight();
19     }
20 
21     if (replacement != null) {
22         replacement.setParent(deleted.getParent());
23     }
24 
25     if (deleted == _root) {
26         _root = replacement;
27     } else if (deleted.isLeftChild()) {
28         deleted.getParent().setLeftChild(replacement);
29     } else {
30         deleted.getParent().setRightChild(replacement);
31     }
32 
33     if (deleted != node) {
34         Object deletedValue = node.getValue();
35         node.setValue(deleted.getValue());
36         deleted.setValue(deletedValue);
37     }
38 
39     return deleted;
40 }

Python:

def find_min(self): # Gets minimum node in a subtree
    current_node = self
    while current_node.left_child:
        current_node = current_node.left_child
    return current_node

def replace_node_in_parent(self, new_value=None):
    if self.parent:
        if self == self.parent.left_child:
            self.parent.left_child = new_value
        else:
            self.parent.right_child = new_value
    if new_value:
        new_value.parent = self.parent

def binary_tree_delete(self, key):
    if key < self.key:
        self.left_child.binary_tree_delete(key)
    elif key > self.key:
        self.right_child.binary_tree_delete(key)
    else: # delete the key here
        if self.left_child and self.right_child: # if both children are present
            successor = self.right_child.find_min()
            self.key = successor.key
            successor.binary_tree_delete(successor.key)
        elif self.left_child:   # if the node has only a *left* child
            self.replace_node_in_parent(self.left_child)
        elif self.right_child:  # if the node has only a *right* child
            self.replace_node_in_parent(self.right_child)
        else: # this node has no children
            self.replace_node_in_parent(None)

Обхождане[редактиране | редактиране на кода]

Елементите на двоично дърво за търсене могат да бъдат обходени рекурсивно. Съществуват различни начини за обхождане — preorder, postorder и inorder. От тях само обхождането от тип inorder има полезно приложение: връща сортиран лист от елементите на възлите.

По-долу е даден код на езика Python за последователно обхождане. За всеки възел в дървото се извиква методът callback.

def traverse_binary_tree(node, callback):
    if node is None:
        return
    traverse_binary_tree(node.leftChild, callback)
    callback(node.value)
    traverse_binary_tree(node.rightChild, callback)

Обхождането изисква O(n) време, тъй като трябва да посети всеки възел. Този алгоритъм е също така със сложност O(n), така че е асимптотично оптимален. Следващият код е примерна имплементация на итеративно последователно обхождане в C#:

Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
var current = this.Root;
while (stack.Count != 0 || current != null)
{
    while (current != null)
    {
        stack.Push(current);
        current = current.Left;
    }
    current = stack.Pop();
    TreeNode<T> node = current;
    current = current.Right;
    yield return node.Value;
}

Сортиране[редактиране | редактиране на кода]

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

Най-лошият случай на build_binary_tree нужното време е  – ако се подаде вече сортиран лист от стойности, тогава двоичното дърво ги подрежда в свързан списък без остатъчни поддървета. Например, при подадени тези стойности: build_binary_tree([1, 2, 3, 4, 5]) – се получава дървото: (1 (2 (3 (4 (5))))).

Има няколко начина за избягване на този недостатък с помощта на прости двоични дървета. Най-често срещаният начин е чрез т.нар. самобалансиращо се двоично дърво. Ако повторим същият пример, посочен по-горе, използвайки самобалансиращото се двоично дърво, в най-лошият случай времето за операцията би било O(n log n), което е асимптотично оптимално за алгоритъм за сортиране. В практиката обаче добавените разходи във време и памет за имплементирането на такъв сорт (особено за създаването и заделянето на памет за възлите) го правят много по-лош от други асимптотично оптимални методи за сортиране (като пирамидално сортиране) за подреждането на статични списъци. От друга страна е един от най-оптималните методи за инкрементално сортиране, където добавяме елементи към лист през времето докато държим листа постоянно сортиран.

Верификация[редактиране | редактиране на кода]

Понякога се налага проверка дали двоичното дърво, с което разполагаме, е двоично дърво за търсене. Решението на този проблем може да се намери рекурсивно.

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

     20
    / \
  10 30
       / \
      5 40

Всеки елемент от показаното дървото удовлетворява условието да съдържа стойност по-голяма от стойността на левия наследник и стойност по-малка от стойността на десния наследник. Въпреки това, то не е двоично дърво за търсене. Стойността 5 се намира в дясното поддърво на елемента със стойност 20, което влиза в противоречие с правилото за ДДТ.

Вместо да правим решения базирано изцяло на стойностите на възел и децата му, ни трябва също информация от родителя. В случая с горното дърво, ако помнехме възела със стойност 20, можеше да видим че стойността 5 нарушава правилото за ДДТ.

Поради тази причина трябва да проверяваме за изпълнението на следните условия за всеки един елемент от дървото:

  • ако даден елемент се пада „ляв“ наследник на своя родител, тогава неговата стойност трябва да бъде по-малка (или равна) на стойността на родителя му. Също така трябва да вземе стойността на родителя си и да я свери с възлите в дясното си поддърво за да е сигурен че няма стойност, която е по голяма от тази на родителя.
  • ако даден елементът се пада „десен“ наследник на родителя, тогава той трябва да бъде по-голям по стойност от родителя му. Също така трябва да свери стойността на родителя си със стойностите в лявото си поддърво за да е сигурен че няма възел в поддървото който да е по малък от родителя му.

Пример с рекурсивно решение на С++:

struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
};

bool isBST(TreeNode *node, int minData, int maxData) {
    if(node == NULL) return true;
    if(node->data < minData || node->data > maxData) return false;

    return isBST(node->left, minData, node->data) && isBST(node->right, node->data, maxData);
}

Първоначалното извикване на финкцуята може да стане по следния начин:

if(isBST(root, INT_MIN, INT_MAX)) {
    puts("This is a BST.");
} else {
    puts("This is NOT a BST!");
}

Създаваме валиден диапазон (започвайки от [MIN_VALUE, MAX_VALUE]) и продължаваме да го стесняваме за всеки елемент на дървото рекурсивно.

Приоритетни опашки[редактиране | редактиране на кода]

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

// Precondition: T is not a leaf
function find-min(T):
    while hasLeft(T):
        T ← left(T)
    return key(T)

Функцията Find-max е аналогична – тя следва пойнтерите отдясно, до толкова далеч, докъдето е възможно. Delete-min (max) може да търси съответно минимума (максимума), след което да го изтрие. В този случай, вмъкването и изтриването отнемат еднакво логаритмично време, както се случва и при двоичният хийп (binary heap). За разлика обаче от двоичният хийп и от повечето имплементации на приоритетни опашки, едно дърво може да поддържа всички функции find-min, find-max, delete-min и delete-max едновременно, правейки двоичните дървета за търсене подходящи да служат като приоритетни опашки с два края.[2]:156

Видове[редактиране | редактиране на кода]

Има различни видове двоични дървета за търсене. AVL и червено-черните дървета са вид самобалансиращи се двоични дървета за търсене. Сплей дърво е вид ДДТ, което автоматично премества често достъпвани елементи, намиращи се близо до корена на дървото. В treap (tree heap), всеки възел също така държи и (произволно избран) приоритет и възела родител има по голям приоритет от децата си. Танго дърветата са вид дървета, които са оптимизирани за по-бързо търсене.

Съществуват два други типа двоични дървета за търсене – завършени и дегенерирали дървета.

Завършено двоично дърво означава, че то е изцяло запълнено, с евентуални изключения на най-долното ниво на дървото, което се запълва от ляво надясно. В завършеното двоично дърво, всички елементи са разположени възможно най-вляво. То има n нива, където за всяко ниво d <= n-1, т.е. броят на съществуващите елементи в ниво d е равно на 2d. Това означава, че всички възможни елементи съществуват в тези нива. Допълнително изискване за завършените двоични дървето е това за n-тото ниво: докато за всеки елемент не е задължително да съществува, то тези, които съществуват, трябва да се пълнят от ляво надясно.

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

Сравнение на ефективността[редактиране | редактиране на кода]

През 2004 Д.А.Хегер показва сравнение на ефективността на двоичните дървета за търсене. Treap е намерен да има най-добрата средностатистическа ефективност, докато червено-черното дърво е намерено да има най-малките разлики в ефективността при различните случаи.

Оптимални двоични дървета за търсене[редактиране | редактиране на кода]

Ротациите на дърветата са често срещани вътрешни операции при двоичните дървета, за да могат те да запазят перфектния си вътрешен баланс.

Ако не се правят модификации на едно дърво за търсене и ако се знае точно колко пъти се достъпва всеки един негов елемент, тогава може да се създаде [3] оптимално двоично дърво за търсене. То ще е вид дърво за търсене, където осреднената цена за търсене на елемент, ще е минимална.[4]

Подобна система значително би ускорила търсенето като цяло. Например, ако имаме ДДТ изпълнено с английски думи, което ДДТ използваме в програма за проверка на граматиката (англ. spell checker), можем да балансираме дървото на база често употребявани думи в текст корпуса и да поставим думи като „the“ близо до корена на дървото, а думи като „agerasia (натрупване)“ близо до листата му. Такова дърво може да бъде сравнено с дървото на Хъфман (Huffman tree), което по подобен начин търси често използвани елементи близо до корените на дървото. Дървото на Хъфман обаче съхранява елементите само в листата и тези елементи не се нуждаят от подреждане.

Ако не се знае ръдът, в който елементите в дървото ще бъдат достъпвани, може да се използва Сплей (скосени) дървета.

Азбучни дървета са вид дървета на Хъфман, но с допълнително ограничение относно реда. Това са дървета за търсене, където всички елементи се пазят в листата на дървото. Съществуват по-бързи алгоритми, които могат да се използват при оптимални азбучни дървета за търсене.

Източници[редактиране | редактиране на кода]

  1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009)[1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. p. 287. ISBN 0-262-03384-4.
  2. Mehlhorn, Kurt, Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox. Springer.
  3. Heger, Dominique A.. A Disquisition on The Performance Behavior of Binary Search Tree Data Structures. European Journal for the Informatics Professional. Т. 5. 2004. с. 67 – 75.
  4. Gonnet, Gaston. Optimal Binary Search Trees. // Scientific Computation. ETH Zürich. Посетен през декември 2013.

Външни препратки[редактиране | редактиране на кода]