В информатиката двоичните дървета за търсене, също така наричани подредени или сортирани двоични дървета, са специфичен тип структури, които складират в паметта елементи от произволен нареден тип — числа, низове и т.н. Този тип дървета позволяват бързо търсене, добавяне и премахване на елементи и могат да бъдат използвани за реализирането на динамични множества от елементи или речници, които позволяват бързо търсене по ключ (например намиране на телефонния номер на човек по името му).
Двоичните дървета за търсене пазят ключовете си в подреден ред, затова при тях може да се използва двоично търсене: когато се търси ключ или място за поставяне на нов, те обхождат дървото, като по пътя сравняват търсената стойност със стойностите във възлите на дървото и според резултата от проверката избират да продължат търсенето в лявото или дясното поддърво. Всяко сравнение води до отхвърлянето на около половината от поддървото, затова търсенето на елемент в най-лошия случай отнема време, пропорционално на логаритъма от броя на всички елементи — много по-бързо от търсенето на елемент в неподреден масив, което изразходва време, пропорционално на броя на елементите. Същото важи за операциите добавяне и изтриване на елемент.
Определение Двоично дърво за търсене се нарича такова двоично дърво, чиито вътрешни върхове пазят всеки по един ключ (евентуално и допълнителна стойност), като ключът във всеки връх е по-голям от всички ключове в лявото поддърво и е по-малък от всички ключове в дясното поддърво.Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. p. 287. ISBN 0-262-03384-4. Листата не съдържат ключове, нито каквато и да е информация, по която да бъдат различени едно от друго. Листата най-често се представят със специален знак nil.
Двоичните дървета за търсене са важни за изграждането на абстрактни структури, като множества и асоциативни масиви.
Най-голямото предимство на двоичните дървета за търсене е, че свързаните с тях сортиращи алгоритми и алгоритми за търсене са много бързи и лесни за писане.
Двоичните дървета за търсене имат и някои слабости: Формата им зависи от реда на добавяне на елементите и може да се изроди в списък. След голям брой произволно подредени операции добавяне и изтриване на елемент, очакваната височина на дървото е приблизително квадратният корен от броя на ключовете, което е много повече от логаритъма.
Операции Двоичните дървета за търсене поддържат три главни операции: търсене, добавяне и изтриване на ключ. Всяка операция изисква компаратор — подпрограма за сравняване на два ключа. Компараторът може да бъде определен явно или неявно — в зависимост от езика, на който дървото е програмирано. В много езици операциите „>“ и „<“ могат да се използват само когато се проверяват числови стойности. За всички останали проверки обикновено се ползват ръчно написани компаратори. Общоприета практика в програмирането е методите за сравнение да връщат числова стойност като резултат от сравнението. Върнатата стойност трябва да е отрицателно число, ако левият ключ е по-малък от десния; положително число, ако левият ключ е по-голям от десния; нула, ако двата ключа са равни. Примерна реализация на метод за сравнение на езика Java: public int compare(Object left, Object right) { return ((Comparable)left).compareTo(right); //returns 1 if "left" is greater than "right" //returns 0 if "left" equals "right" //returns -1 if "left" is less than "right" }
Търсене Търсенето започва от корена и продължава в лявото или дясното поддърво в зависимост от резултата от сравняването на търсения ключ с ключа на корена. Търсенето продължава до намирането на ключа или до изчерпването на възможностите. Този алгоритъм може да се програмира рекурсивно или итеративно.
Рекурсивно описание:
Java: public Node search(Object value) { return search(_root, value); }
private Node search(Node node, Object value) { if (node != null) { int cmp = _comparator.compare(value, node.getValue());
if (cmp < 0) { return search(node.getLeft(), value); } else if (cmp > 0) { return search(node.getRight(), value);
return node; //node == null || cmp == 0 }
Python: def search_recursively(key, node): if node is None or node.key == key: return node elif key < node.key: return search_recursively(key, node.left) else: # key > node.key return search_recursively(key, node.right) return None
Итеративно описание:
Java: public Node search(Object value) { Node node = _root;
while (node != null) { int cmp = _comparator.compare(value, node.getValue());
if (cmp < 0) { node = node.getLeft(); } else if (cmp > 0) { node = node.getRight(); } else { //cmp == 0 break;
return node; }
Python: def search_iteratively(key, node): current_node = node while current_node is not None: if key == current_node.key: return current_node elif key < current_node.key: current_node = current_node.left else: # key > current_node.key: current_node = current_node.right return None Понеже в най-лошия случай този алгоритъм трябва да търси от корена на дървото до най-далечното листо, операцията по търсене отнема време пропорционално на височината на дървото (виж терминологията). Средно, двоично дърво за търсене с n възела има O(log n) височина. Обаче в най-лошия случай, двоичните дървета за търсене може да имат O(n) височина, когато небалансираното дърво реално представлява обикновен свързан списък (дегенерирало дърво).
Добавяне Добавянето на стойност в двоично дърво, може да се раздели на алгоритъм от две части – търсене на подходящо място за новата стойност в дървото и реалното вмъкване на стойността под формата на нов възел.
Добавянето започва, както би започнало стандартно търсене на стойност – ако стойността не е равна на стойността на корена, следваме левия или десния дъщерен възел, докато не достигнем съвпадение на стойности или външен възел (възел равен на null). И в двата случая създаваме нов възел с ключ равен на стойността, която искаме да вмъкнем в дървото. Ако имаме съвпадение на стойности (дървото вече има съществуващ възел, чиято стойност е равна на стойността за вмъкване), то стандартната практика е да добавим новия възел като ляв дъщерен възел на вече съществуващата стойност. В случая, когато нямаме съвпадение на стойности, което е и по-често срещания вариант, то сме стигнали до листо (възел без наследници) и добавяме новата стойност като ляв или десен дъщерен възел, в зависимост от това дали новия възел е с по-голяма или по-малка стойност от стойността на листото. Пример за алгоритъм за добавяне на нова стойност в двоично дърво, използващ итеративно търсене на място за вмъкване, написан на Java, би изглеждал по следния начин: public Node insert(Object value) { Node parent = null; Node node = _root; int cmp = 0;
while (node != null) { parent = node; cmp = _comparator.compare(value, node.getValue()); if (cmp <= 0) { node = node.getLeft(); } else { node = node.getRight();
Node inserted = new Node(value); inserted.setParent(parent);
if (parent == null) { _root = inserted; } else if (cmp < 0) { parent.setSmaller(inserted); } else { parent.setLarger(inserted);
return inserted; }
При добавяне на случайно генерирани стойности, дървото до голяма степен ще запази височина O(log n). Трябва, обаче, да се има предвид, че добавяне на всякакви стойности в подреден формат, неизбежно ще доведе до свеждането на дървото до обикновен свързан списък, което е и най-лошия възможен вариант. В такъв случай, височината на дървото, а с това и средното време за търсене, нараства до O(N). Различни вариации на двоичното дърво за търсене, имат свойството да се самобалансират, което позволява на структурата от данни да запази дървовидната си форма и добрата си производителност при търсене. Вариации на двоично дърво за търсене, които поддържат балансиране, са например Червено-Черни дървета, AVL дървета и Splay дървета. Олекотен вариант на подобна структура от данни, са също и B-Tree дърветата.
Изтриване Има три случая които да се обмислят: Изтриване на възел без деца: просто изтриваме възела от дървото. Изтриване на възел с едно дете: изтриваме възела и го подменяме с детето му. Изтриване на възел с две деца: в този случай, трябва да разменим възела, който ще изтрием, с неговия наследник или предшественик (виж in-order обхождане на дърво). Продължаваме да разменяме възлите, докато не стигнем до ситуация, в която възела остане само с едно дете или без деца. Трябва да се има предвид, че използването на последователния наследник или на последователния предшественик за всяка инстанция на случаят с две деца може да доведе до небалансирано дърво, затова някой имплементации избират единия или другия в различни случаи.
Изтриване на възел без деца (листо) е най-добрия възможен вариант. В този случай е достатъчно просто да разрушим връзката на възела с неговия родител.
Следващия най-добър вариант е, когато възела има едно дете. В такава ситуация, трябва да слепим дъщерното листо, с родителя на възела, дефакто подменяйки възела със собственото му листо. Процеса на подмяна е еквивалентен с този на разрушаване на връзката между възела и родителя му, за това след като слепването е приключило, изтриването се счита за приключено.
Най-сложния вариант за изтриване на възел, е когато възела има две деца. Ако имаме ситуация, в която трябва да изтрием корена на дърво с височина три, трябва да определим точно кой възел, ще използваме за заместник. Реално, можем да използваме както левия, така и десния дъщерен възел на корена, но всеки един от тези два възела има свои собствени наследници, което допълнително затруднява простата замяна на корена с някой от наследниците му. В такава ситуация, намираме наследника или предшественика на корена и разменяме стойностите им. След това, се опитваме да изтрием не корена, а възела, който прие оригиналната стойност на корена. Ако новия възел отново има две деца, то повтаряме процедурата с намиране на наследник/предшественик и смяна на стойности. Повтаряйки процедурата отново и отново, то неизбежно ще попаднем в един от първите два варианта, при които вече преминаваме към разрушаване на връзката родител-дете.
Анализ по време на работа: Въпреки че тази операция не винаги обхожда дървото до листо, винаги има шанс за това, съответно в най-лошия случай изисква време пропорционално на височината на дървото. Не се изисква повече време дори и когато възела има две деца, тъй като операцията все още продължава надолу по една пътека и не посещава един и същи възел два пъти. Примери за изтриване на стойност в двоично дърво за търсене:
Java: public Node delete(Object value) { Node node = search(value); if (node == null) { return null;
Node deleted; if (node.getLeft() != null && node.getRight() != null) { deleted = node.successor(); } else { deleted = node;
Node replacement; if (deleted.getLeft() != null) { replacement = deleted.getLeft(); } else { replacement = deleted.getRight();
if (replacement != null) { replacement.setParent(deleted.getParent());
if (deleted == _root) { _root = replacement; } else if (deleted.isLeftChild()) { deleted.getParent().setLeftChild(replacement); } else { deleted.getParent().setRightChild(replacement);
if (deleted != node) { Object deletedValue = node.getValue(); node.setValue(deleted.getValue()); deleted.setValue(deletedValue);
return deleted; } 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)