Двоично дърво за търсене (BST) с пример
Какво е двоично дърво за търсене?
Двоичното дърво за търсене е усъвършенстван алгоритъм, използван за анализиране на възела, неговите леви и десни клонове, които са моделирани в дървовидна структура и връщане на стойността. BST е разработен върху архитектурата на основен алгоритъм за двоично търсене; следователно позволява по-бързо търсене, вмъкване и премахване на възли. Това прави програмата наистина бърза и точна.
Атрибути на двоично дърво за търсене
BST се състои от множество възли и се състои от следните атрибути:
- Възлите на дървото са представени във връзка родител-дете
- Всеки родителски възел може да има нула дъщерни възли или максимум два подвъзела или поддървета от лявата и дясната страна.
- Всяко поддърво, известно още като двоично дърво за търсене, има подклонове отдясно и отляво на себе си.
- Всички възли са свързани с двойки ключ-стойност.
- Ключовете на възлите, присъстващи в лявото поддърво, са по-малки от ключовете на техния родителски възел
- По подобен начин ключовете на левите възли на поддървото имат по-малки стойности от ключовете на техния родителски възел.
- Има основния възел или родителско ниво 11. Под него има леви и десни възли/клонове със собствени ключови стойности
- Дясното поддърво има ключови стойности, по-големи от родителския възел
- Лявото поддърво има стойности от родителския възел
Защо се нуждаем от двоично дърво за търсене?
- Двата основни фактора, които правят двоичното дърво за търсене оптимално решение за всякакви проблеми от реалния свят, са скоростта и точността.
- Поради факта, че двоичното търсене е във формат, подобен на клон с отношения родител-дете, алгоритъмът знае в кое местоположение на дървото трябва да се търсят елементите. Това намалява броя на сравненията ключ-стойност, които програмата трябва да направи, за да намери желания елемент.
- Освен това, в случай че елементът за търсене е по-голям или по-малък от родителския възел, възелът знае коя страна на дървото да търси. Причината е, че лявото поддърво винаги е по-малко от родителския възел, а дясното поддърво винаги има стойности, равни или по-големи от родителския възел.
- BST обикновено се използва за прилагане на сложни търсения, стабилна логика на играта, дейности за автоматично завършване и графики.
- Алгоритъмът ефективно поддържа операции като търсене, вмъкване и изтриване.
Видове двоични дървета
Три вида двоични дървета са:
- Пълно двоично дърво: Всички нива в дърветата са пълни с възможни изключения от последното ниво. По същия начин всички възли са пълни, насочвайки крайно вляво.
- Пълно двоично дърво: Всички възли имат 2 дъщерни възела с изключение на листа.
- Балансирано или перфектно двоично дърво: В дървото всички възли имат две деца. Освен това има едно и също ниво на всеки подвъзел.
Научете повече за Двоично дърво в структурата на данните ако си заинтересован.
Как работи дървото за двоично търсене?
Дървото винаги има основен възел и допълнителни дъщерни възли, независимо дали отляво или отдясно. Алгоритъмът изпълнява всички операции, като сравнява стойностите с корена и неговите следващи дъщерни възли съответно в лявото или дясното поддърво.
В зависимост от елемента, който трябва да бъде вмъкнат, търсен или изтрит, след сравнението алгоритъмът може лесно да изпусне лявото или дясното поддърво на основния възел.
BST предлага предимно следните три вида операции за ваша употреба:
- Търсене: търси елемента от двоичното дърво
- Вмъкване: добавя елемент към двоичното дърво
- Изтриване: изтрива елемента от двоично дърво
Всяка операция има своя собствена структура и метод на изпълнение/анализ, но най-сложната от всички е операцията Delete.
Търсене OperaАЦИ
Винаги започвайте анализиращо дърво от основния възел и след това се придвижете към дясното или лявото поддърво на основния възел в зависимост от това дали елементът, който трябва да се намери, е по-малък или по-голям от корена.
- Елементът за търсене е 10
- Сравнете елемента с коренния възел 12, 10 < 12, следователно се премествате в лявото поддърво. Няма нужда да анализирате дясното поддърво
- Сега сравнете 10 с възел 7, 10 > 7, така че преминете към дясното поддърво
- След това сравнете 10 със следващия възел, който е 9, 10 > 9, погледнете в дясното дъщерно поддърво
- 10 съвпада със стойността във възела, 10 = 10, връща стойността на потребителя.
Псевдо код за търсене в 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 – В предшественика на поръчката: трябва да изтриете възела с две деца и да го замените с най-голямата стойност в лявото поддърво на изтрития възел
- 3b – В наследник на поръчка: трябва да изтриете възела с две деца и да го замените с най-голямата стойност в дясното поддърво на изтрития възел
- Това е първият случай на изтриване, при който изтривате възел, който няма деца. Както можете да видите на диаграмата, 19, 10 и 5 нямат деца. Но ние ще изтрием 19.
- Изтрийте стойността 19 и премахнете връзката от възела.
- Вижте новата структура на BST без 19
- Това е вторият случай на изтриване, при който изтривате възел, който има 1 дете, както можете да видите на диаграмата, че 9 има едно дете.
- Изтрийте възела 9 и го заменете с неговия дъщерен 10 и добавете връзка от 7 към 10
- Вижте новата структура на BST без 9
- Тук ще изтриете възел 12, който има две деца
- Изтриването на възела ще се извърши въз основа на правилото за предшественик по ред, което означава, че най-големият елемент в лявото поддърво от 12 ще го замени.
- Изтрийте възела 12 и го заменете с 10, тъй като това е най-голямата стойност в лявото поддърво
- Вижте новата структура на BST след изтриване на 12
- 1 Изтрийте възел 12, който има две деца
- 2 Изтриването на възела ще се извърши въз основа на правилото за наследник в ред, което означава, че най-големият елемент в дясното поддърво от 12 ще го замени
- 3 Изтрийте възела 12 и го заменете с 19, тъй като това е най-голямата стойност в дясното поддърво
- 4 Вижте новата структура на BST след изтриване 12
Псевдо код за изтриване на възел
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 to the root #we're deleting the successor free(newNode) else free(y)
Важни условия
- Вмъкване: Вмъква елемент в дърво/създава дърво.
- Търсене: Търси елемент в дърво.
- Preorder Traversal: Обхожда дърво по начин на предварителна поръчка.
- Обхождане по ред: Обхожда дърво по ред.
- Postorder Traversal: Преминава през дърво по начин след поръчка.
Oбобщение
- BST е алгоритъм за усъвършенствано ниво, който изпълнява различни операции въз основа на сравнението на стойностите на възела с основния възел.
- Всяка от точките в йерархията родител-дете представлява възела. Поне един родителски или основен възел остава присъстващ през цялото време.
- Има ляво поддърво и дясно поддърво. Лявото поддърво съдържа стойности, които са по-малки от основния възел. Дясното поддърво обаче съдържа стойност, която е по-голяма от коренния възел.
- Всеки възел може да има нула, едно или две деца.
- Двоично дърво за търсене улеснява основните операции като търсене, вмъкване и изтриване.
- Изтриването е най-сложният и има множество случаи, например възел без дете, възел с едно дете и възел с две деца.
- Алгоритъмът се използва в решения от реалния свят като игри, данни за автоматично попълване и графики.