Дърво на двоично търсене (BST) с пример

Какво е бинарно дърво за търсене?

Бинарното дърво за търсене е усъвършенстван алгоритъм, използван за анализ на възела, неговите ляв и десен клон, които са моделирани в дървовидна структура и връщане на стойността. BST е разработен върху архитектурата на основен двоичен алгоритъм за търсене; следователно позволява по-бързо търсене, вмъкване и премахване на възли. Това прави програмата наистина бърза и точна.

В този урок за Структура на данни ще научите:

• Какво е бинарно дърво за търсене?
• Атрибути на бинарното дърво за търсене
• Защо се нуждаем от двоично дърво за търсене?
• Видове бинарни дървета
• Как работи бинарното дърво за търсене?
• Важни условия

Атрибути на бинарното дърво за търсене

BST се състои от множество възли и се състои от следните атрибути:

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

1. Там е основният възел или родителско ниво 11. Под него има леви и десни възли / разклонения със собствени ключови стойности
2. В дясното поддърво има ключови стойности, по-големи от родителския възел
3. Лявото поддърво има стойности от родителския възел

Защо се нуждаем от двоично дърво за търсене?

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

Видове бинарни дървета

Три вида бинарни дървета са:

• Пълно двоично дърво: Всички нива в дърветата са пълни с възможните изключения от последното ниво. По същия начин всички възли са пълни, насочвайки крайното ляво.
• Пълно двоично дърво: Всички възли имат 2 дъщерни възела с изключение на листа.
• Балансирано или перфектно двоично дърво: В дървото всички възли имат две деца. Освен това има едно и също ниво на всеки подвъзел.

Как работи бинарното дърво за търсене?

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

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

BST основно предлага следните три вида операции за ваше използване:

• Търсене: търси елемента от двоичното дърво
• Вмъкване: добавя елемент към двоичното дърво
• Изтриване: изтриване на елемента от двоично дърво

Всяка операция има своя собствена структура и метод за изпълнение / анализ, но най-сложната от всички е операцията Delete.

Операция за търсене

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

1. Елементът за търсене е 10
2. Сравнете елемента с кореновия възел 12, 10 <12, следователно се премествате в лявото поддърво. Няма нужда да анализирате дясното поддърво
3. Сега сравнете 10 с възел 7, 10> 7, така че преминете към дясното поддърво
4. След това сравнете 10 със следващия възел, който е 9, 10> 9, погледнете в дясното поддерево дете
5. 10 съвпадения със стойността в възела, 10 = 10, връща стойността на потребителя.

Вмъкване на операция

Това е много права операция. Първо се вмъква коренният възел, след това следващата стойност се сравнява с коренния възел. Ако стойността е по-голяма от корен, тя се добавя към дясното поддърво, а ако е по-малка от корен, се добавя към лявото поддърво.

1. Има списък от 6 елемента, които трябва да бъдат вмъкнати в BST, за да бъдат отляво надясно
2. Поставете 12 като основен възел и сравнете следващите стойности 7 и 9 за вмъкване по съответния начин в дясно и ляво поддърво
3. Сравнете останалите стойности 19, 5 и 10 с коренния възел 12 и ги поставете съответно. 19> 12 го поставете като дясно дете на 12, 5 <12 и 5 <7, следователно го поставете като ляво дете на 7.
   1. Сега сравнете 10, 10 е <12 и 10 е> 7 и 10 е> 9, поставете 10 като дясно поддърво от 9.

Изтриване на операции

Изтриването е най-напредналото и сложно сред всички останали операции. Има много случаи, обработени за изтриване в BST.

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

1. Това е първият случай на изтриване, при който изтривате възел, който няма деца. Както можете да видите на диаграмата, че 19, 10 и 5 нямат деца. Но ще изтрием 19.
2. Изтрийте стойността 19 и премахнете връзката от възела.
3. Вижте новата структура на BST без 19

1. Това е вторият случай на изтриване, при който изтривате възел, който има 1 дете, както можете да видите на диаграмата, че 9 има едно дете.
2. Изтрийте възела 9 и го заменете с неговото дъщерно устройство 10 и добавете връзка от 7 до 10
3. Вижте новата структура на BST без 9

1. Тук ще изтриете възела 12, който има две деца
2. Изтриването на възела ще се извърши въз основа на правилото за предшественик по ред, което означава, че най-големият елемент в лявото поддърво от 12 ще го замени.
3. Изтрийте възела 12 и го заменете с 10, тъй като това е най-голямата стойност в лявото поддърво
4. Вижте новата структура на BST след изтриване на 12

1. 1 Изтрийте възел 12, който има две деца
2. 2 Изтриването на възела ще се извърши въз основа на правилото In Order Successor, което означава, че най-големият елемент в дясното поддърво от 12 ще го замени
3. 3 Изтрийте възела 12 и го заменете с 19, тъй като той е най-голямата стойност в дясното поддърво
4. 4 Прегледайте новата структура на BST след изтриване на 12

Важни условия

• Вмъкване - Вмъква елемент в дърво / създава дърво.
• Търсене - Търси елемент в дърво.
• Прекратяване на предварителна поръчка - обхожда дърво по начин на предварителна поръчка.
• Inorder Traversal - Преминава дърво по ред.
• Пренасочване след поръчка - Преминава дърво по начин след поръчка.

Обобщение

• BST е алгоритъм за напреднали нива, който изпълнява различни операции, базирани на сравнението на стойностите на възела с основния възел.
• Всяка от точките в йерархията родител-дете представлява възела. Поне един родителски или корен възел остава наличен през цялото време.
• Има ляво и дясно поддърво. Лявото поддърво съдържа стойности, които са по-малки от основния възел. Въпреки това, дясното поддърво съдържа стойност, която е по-голяма от основния възел.
• Всеки възел може да има нула, едно или две деца.
• Двоично дърво за търсене улеснява първични операции като търсене, вмъкване и изтриване.
• Изтриването като най-сложното има множество случаи, например възел без дете, възел с едно дете и възел с две деца.
• Алгоритъмът се използва в реални решения като игри, автодовършване на данни и графики.