Двоично дърво за търсене (BST) с пример
Сара Чен
⚡ Умно обобщение
Двоичното дърво на търсене (BST) е дърво, базирано на възли, където лявото поддърво на всеки възел съдържа по-малки ключове, а дясното му поддърво съдържа по-големи ключове, което позволява бързо търсене, вмъкване и изтриване. То обхваща атрибути, типове, операции и псевдокод на BST.
Какво е двоично дърво за търсене?
Двоичното дърво за търсене е усъвършенстван алгоритъм, използван за анализ на възела, неговите ляви и десни клонове, които са моделирани в дървовидна структура, и връщане на стойността. BST е разработено върху архитектурата на основен алгоритъм за двоично търсене; следователно, то позволява по-бързо търсене, вмъкване и премахване на възли. Това прави програмата наистина бърза и точна.
Атрибути на двоично дърво за търсене
BST се състои от множество възли и се състои от следните атрибути:
- Възлите на дървото са представени във връзка родител-дете.
- Всеки родителски възел може да има нула дъщерни възли или максимум два подвъзела или поддървета от лявата и дясната страна.
- Всяко поддърво, известно още като двоично дърво за търсене, има подклонове отдясно и отляво на себе си.
- Всички възли са свързани с двойки ключ-стойност.
- Ключовете на възлите, присъстващи в лявото поддърво, са по-малки от ключовете на техния родителски възел.
- По подобен начин, ключовете на възлите, присъстващи в дясното поддърво, са по-големи от ключовете на техния родителски възел.
- Има главен възел или родителско ниво 11. Под него има леви и десни възли/клонове със собствени ключови стойности.
- Дясното поддърво има ключови стойности, по-големи от родителския възел.
- Лявото поддърво има ключови стойности по-малко от родителския възел.
Защо се нуждаем от двоично дърво за търсене?
- Двата основни фактора, които правят двоичното дърво за търсене оптимално решение за всеки реален проблем, са скорост и точност.
- Поради факта, че двоичното търсене е във формат, подобен на клон с отношения родител-дете, алгоритъмът знае в кое местоположение на дървото трябва да се търсят елементите. Това намалява броя на сравненията ключ-стойност, които програмата трябва да направи, за да намери желания елемент.
- Освен това, в случай че елементът, който ще се търси, е по-голям или по-малък от родителския възел, възелът знае от коя страна на дървото да търси. Причината е, че лявото поддърво винаги е по-малко от родителския възел, а дясното поддърво има стойности, винаги равни или по-големи от родителския възел.
- BST обикновено се използва за прилагане на сложни търсения, стабилна логика на играта, дейности за автоматично завършване и графики.
- Алгоритъмът ефективно поддържа операции като търсене, вмъкване и изтриване.
Видове двоични дървета
Три вида двоични дървета са:
- Пълно двоично дърво: Всички нива в дървото са пълни, с възможно изключение на последното ниво. По подобен начин всички възли са пълни, насочвайки се към най-лявата част.
- Пълно двоично дърво: Всички възли имат 2 дъщерни възела, с изключение на листа.
- Балансирано или перфектно двоично дърво: В дървото всички възли имат по две деца. Освен това, има едно и също ниво за всеки подвъзел.
Научете повече за Двоично дърво в структурата на данните ако си заинтересован.
Как работи дървото за двоично търсене?
Дървото винаги има основен възел и допълнителни дъщерни възли, независимо дали отляво или отдясно. Алгоритъмът изпълнява всички операции, като сравнява стойностите с корена и неговите следващи дъщерни възли съответно в лявото или дясното поддърво.
В зависимост от елемента, който ще бъде вмъкнат, претърсен или изтрит, след сравнението, алгоритъмът може лесно да премахне лявото или дясното поддърво на коренния възел.
BST предлага предимно следните три вида операции за ваша употреба:
- Търсене: търси елемента от двоичното дърво.
- Поставете: добавя елемент към двоичното дърво.
- Изтрий: изтрива елемента от двоично дърво.
Всяка операция има своя собствена структура и метод на изпълнение/анализ, но най-сложната от всички е операцията Delete.
Търсене OperaАЦИ
Винаги започвайте анализа на дървото от коренния възел и след това се придвижвайте по-нататък към дясното или лявото поддърво на коренния възел, в зависимост от това дали елементът, който трябва да бъде локализиран, е по-малък или по-голям от корена.
- Елементът, който ще се търси, е 10.
- Сравнете елемента с коренния възел 12, 10 < 12, следователно се премествате към лявото поддърво. Няма нужда да анализирате дясното поддърво.
- Сега сравнете 10 с възел 7, 10 > 7, така че преминете към дясното поддърво.
- След това сравнете 10 със следващия възел, който е 9, 10 > 9, потърсете в дясното дете на поддървото.
- 10 съвпада със стойността във възела, 10 = 10, връща стойността на потребителя.
Прякор Code за търсене в BST
search(element, root)
if !root
return -1
if root.value == element
return 1
if root.value < element
search(element, root.right)
else
search(element, root.left)
Поставете OperaАЦИ
Това е много проста операция. Първо се вмъква коренният възел, след което следващата стойност се сравнява с него. Ако стойността е по-голяма от корена, тя се добавя към дясното поддърво, а ако е по-малка от корена, се добавя към лявото поддърво.
- Има списък от 6 елемента, които трябва да бъдат вмъкнати в BST по ред отляво надясно.
- Вмъкнете 12 като коренен възел и сравнете следващите стойности 7 и 9 за съответно вмъкване в дясното и лявото поддърво.
- Сравнете останалите стойности 19, 5 и 10 с коренния възел 12 и ги поставете съответно. 19 > 12, поставете го като дясното дете на 12; 5 < 12 и 5 < 7, следователно го поставете като лявото дете на 7. Сега сравнете 10, 10 е < 12 и 10 е > 7 и 10 е > 9, поставете 10 като дясното поддърво на 9.
Псевдокод за вмъкване на възел в BST
insert (element, root)
Node x = root
Node y = NULL
while x:
y = x
if x.value < element.value
x = x.right
else
x = x.left
if y.value < element
y.right = element
else
y.left = element
Изтрий Operaции
За изтриване на възел от BST има някои случаи, например изтриване на корен или изтриване на листен възел. Също така, след изтриване на корен, трябва да помислим за коренния възел.
Да кажем, че искаме да изтрием листов възел, можем просто да го изтрием, но ако искаме да изтрием корен, трябва да заменим стойността на корена с друг възел. Да вземем следния пример:
- Случай 1 – Възел с нула деца: Това е най-лесната ситуация, просто трябва да изтриете възела, който няма други деца отдясно или отляво.
- Случай 2 – Възел с едно дете: След като изтриете възела, просто свържете неговия дъщерен възел с родителския възел на изтритата стойност.
- Случай 3 – Възел с две деца: Това е най-трудната ситуация и тя работи по следните две правила:
- 3a – Предшественик по ред: Трябва да изтриете възела с две деца и да го замените с най-голямата стойност в лявото поддърво на изтрития възел.
- 3б – Наследник по ред: Трябва да изтриете възела с две деца и да го замените с най-малката стойност в дясното поддърво на изтрития възел.
- Това е първият случай на изтриване, при който изтривате възел, който няма деца. Както можете да видите на диаграмата, 19, 10 и 5 нямат деца. Но ние ще изтрием 19.
- Изтрийте стойността 19 и премахнете връзката от възела.
- Вижте новата структура на BST без 19.
- Това е вторият случай на изтриване, при който изтривате възел, който има 1 дете. Както можете да видите на диаграмата, 9 има едно дете.
- Изтрийте възел 9 и го заменете с неговия дъщерен възел 10, и добавете връзка от 7 към 10.
- Вижте новата структура на BST без 9.
- Тук ще изтриете възел 12, който има две деца.
- Изтриването на възела ще се извърши въз основа на правилото за предшественици по ред, което означава, че най-големият елемент в лявото поддърво на 12 ще го замени.
- Изтрийте възел 12 и го заменете с 10, тъй като това е най-голямата стойност в лявото поддърво.
- Вижте новата структура на BST след изтриване на 12.
- Изтрийте възел 12, който има две деца.
- Изтриването на възела ще се извърши въз основа на правилото за наследяване по ред, което означава, че най-малкият елемент в дясното поддърво от 12 ще го замени.
- Изтрийте възел 12 и го заменете с 19, тъй като това е най-малката стойност в дясното поддърво.
- Вижте новата структура на BST след изтриване на 12.
Прякор Code за изтриване на възел
delete (value, root):
Node x = root
Node y = NULL
# searching the node
while x:
y = x
if x.value < value
x = x.right
else if x.value > value
x = x.left
else if value == x
break
# if the node is not null, then replace it with successor
if y.left or y.right:
newNode = GetInOrderSuccessor(y)
root.value = newNode.value
# after copying the value of successor, delete the successor
free(newNode)
else
free(y)
Важни условия
- Поставете: Вмъква елемент в дърво / създава дърво.
- Търсене: Търси елемент в дърво.
- Преминаване през предварителна поръчка: Преминава през дърво по предварителен ред.
- Обход по ред: Преминава през дърво по определен ред.
- Преминаване през пощенска поръчка: Преминава през дърво по начин, следващ реда му.
