Двоично дърво за търсене
| Двоично дърво за търсене | ||||
 Двоично дърво за търсене с размер 9 и дълбочина 3, с числото 8 като корен. Листата не са показани | ||||
| Информация | ||||
|---|---|---|---|---|
| Тип | Дърво | |||
| Година | 1960 г. | |||
| Изобретено от | П.Ф.Уиндли, А.Д.Бут, А.Д.Т.Колин, и Т.Н.Хибърд | |||
| Сложност в O-нотация | ||||
| ||||
| ||||
| ||||
| ||||
| ||||
| Двоично дърво за търсене в Общомедия | ||||
В информатиката двоичните дървета за търсене, също така наричани подредени или сортирани двоични дървета, са специфичен тип структури, които складират в паметта елементи от произволен нареден тип — числа, низове и т.н. Този тип дървета позволяват бързо търсене, добавяне и премахване на елементи и могат да бъдат използвани за реализирането на динамични множества от елементи или речници, които позволяват бързо търсене по ключ (например намиране на телефонния номер на човек по името му).
Двоичните дървета за търсене пазят ключовете си в подреден ред, затова при тях може да се използва двоично търсене: когато се търси ключ или място за поставяне на нов, те обхождат дървото, като по пътя сравняват търсената стойност със стойностите във възлите на дървото и според резултата от проверката избират да продължат търсенето в лявото или дясното поддърво. Всяко сравнение води до отхвърлянето на около половината от поддървото, затова търсенето на елемент в най-лошия случай отнема време, пропорционално на логаритъма от броя на всички елементи — много по-бързо от търсенето на елемент в неподреден масив, което изразходва време, пропорционално на броя на елементите. Същото важи за операциите добавяне и изтриване на елемент.
Определение[редактиране | редактиране на кода]
Двоично дърво за търсене се нарича такова двоично дърво, чиито вътрешни върхове пазят всеки по един ключ (евентуално и допълнителна стойност), като ключът във всеки връх е по-голям от всички ключове в лявото поддърво и е по-малък от всички ключове в дясното поддърво.[1] Листата не съдържат ключове, нито каквато и да е информация, по която да бъдат различени едно от друго. Листата най-често се представят със специален знак 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)
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), което по подобен начин търси често използвани елементи близо до корените на дървото. Дървото на Хъфман обаче съхранява елементите само в листата и тези елементи не се нуждаят от подреждане.
Ако не се знае ръдът, в който елементите в дървото ще бъдат използвани, може да се използва Сплей (скосени) дървета.
Азбучни дървета са вид дървета на Хъфман, но с допълнително ограничение относно реда. Това са дървета за търсене, където всички елементи се пазят в листата на дървото. Съществуват по-бързи алгоритми, които могат да се използват при оптимални азбучни дървета за търсене.
Източници[редактиране | редактиране на кода]
- ↑ 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.
- ↑ Mehlhorn, Kurt, Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox. Springer.
- ↑ 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. Архив на оригинала от 2014-03-27 в Wayback Machine.
- ↑ Gonnet, Gaston. Optimal Binary Search Trees // Scientific Computation. ETH Zürich. Посетен през декември 2013. Архивиран от оригинала на 2002-08-30. Посетен на 2015-09-30.