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

Двоично дърво за търсене е една от различните структури от данни, които ни помагат да организираме и сортираме данни. Това е ефективен начин за съхранение на данни в йерархия и е много гъвкав.

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

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

Двоично дърво за търсене е структура от данни, съставена от възли – подобно на свързаните списъци. Може да има два вида възли: родителски и детски. Коренният възел е началната точка на структурата, която се разклонява на два дъщерни възела, наречени ляв възел и десен възел.

Всеки възел може да бъде препратен само от неговия родител и можем да преминем през възлите на дървото в зависимост от посоката. Дървото за двоично търсене има три основни свойства:

1. Левият възел е по-малък от своя родител.
2. Десният възел е по-голям от своя родител.
3. Лявото и дясното поддървота трябва да са Двоично дърво за търсене.

Перфектно дърво за двоично търсене се постига, когато всички нива са запълнени и всеки възел има ляв и десен дъщерен възел.

Свързани: Библиотеки за наука за данни за Python, които всеки специалист по данни трябва да използва

Основни операции на дърво за двоично търсене

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

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

Търсенето ни позволява да намерим конкретна стойност, присъстваща в дървото. Можем да използваме два типа търсения: търсене в ширина (BFS) и търсене в дълбочина (DFS). Търсенето в ширина е алгоритъм за търсене, който започва от основния възел и преминава хоризонтално, от едната към другата страна, докато се намери целта. Всеки възел се посещава веднъж по време на това търсене.

Търсенето в дълбочина, от друга страна, пресича дървото вертикално – започвайки от коренния възел и продължавайки надолу по един клон. Ако целта бъде намерена, операцията приключва. Но ако не, той и търси другите възли.

2. Операция вмъкване

Операцията за вмъкване използва операцията за търсене, за да определи мястото, където трябва да бъде вмъкнат новият възел. Процесът започва от основния възел и търсенето започва, докато се достигне дестинацията. Има три случая, които трябва да се разгледат с вмъкването.

• Случай 1: Когато не съществува възел. Възелът, който ще бъде вмъкнат, ще стане основен възел.

• Случай 2: Няма деца. В този случай възелът ще бъде сравнен с основния възел. Ако е по-голямо, то ще стане правилното дете; в противен случай ще стане лявото дете.

• Случай 3: Когато присъстват коренът и неговите деца. Новият възел ще бъде сравнен с всеки възел по пътя му, за да се определи кой възел ще посети следващия. Ако възелът е по-голям от основния възел, той ще премине надолу по дясното поддърво или по лявото. По същия начин се правят сравнения на всяко ниво, за да се определи дали ще тръгне надясно или наляво, докато пристигне на местоназначението си.

3. Операция изтриване

Операцията изтриване се използва за премахване на конкретен възел в дървото. Изтриването се счита за трудно, тъй като след премахване на възел дървото трябва да бъде съответно реорганизирано. Има три основни случая за разглеждане:

• Случай 1: Изтриване на листов възел. Листният възел е възел без деца. Това е най-лесното за премахване, тъй като не засяга нито един друг възел; ние просто обикаляме дървото, докато стигнем до него и го изтрием.

• Случай 2: Изтриване на възел с едно дете. Изтриването на родител с един възел ще доведе до това детето да заеме своята позиция и всички следващи възли ще се придвижат нагоре с едно ниво. Няма да има промяна в структурата на поддърветата.

• Случай 3: Изтриване на възел с две деца. Когато трябва да премахнем възел с две деца, първо трябва да намерим следващ възел, който може да заеме неговата позиция. Два възела могат да заменят премахнатия възел, поредния наследник или предшественик. Наследникът в ред е най-лявото дете на дясното поддърво, а предшественикът на поддървото е най-дясното дете на лявото поддърво. Копираме съдържанието на наследника/предшественика в възела и изтриваме наследника/предшественика в поредния ред.

Свързани: Как да изградите структури от данни с JavaScript ES6 класове

Как да преминете през двоично дърво за търсене

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

• Обход в поръчка: Преминаването в ред ще създаде карта във възходящ ред. С този метод започваме от лявото поддърво и продължаваме към коренното и дясното поддърво.

• Обход на предварителна поръчка: При този метод първо се посещава основният възел, последван от лявото поддърво и дясното поддърво.

• Обход след поръчка: Това обхождане включва последно посещение на основния възел. Започваме от лявото поддърво, след това от дясното поддърво и след това от коренния възел.

Приложения в реалния свят

И така, как да използваме алгоритмите за двоично дърво за търсене? Както може да се предположи, те са изключително ефективни при търсене и сортиране. Най-голямата сила на двоичните дървета е тяхната организирана структура. Позволява търсенето да се извършва със забележителни скорости, като намалява наполовина количеството данни, които трябва да анализираме на преминаване.

Дърветата за двоично търсене ни позволяват ефективно да поддържаме динамично променящ се набор от данни в организирана форма. За приложения, в които често се вмъкват и премахват данни, те са много полезни. Двигателите за видеоигри използват алгоритъм, базиран на дървета, известни като двоичен дял на пространството, за да помогнат при изобразяването на обектите подредено. Microsoft Excel и повечето софтуери за електронни таблици използват двоични дървета като основна структура от данни.

Може да се изненадате да разберете, че морзовата азбука използва двоично дърво за търсене за кодиране на данни. Друга важна причина, поради която дърветата за двоично търсене са толкова полезни, са техните множество вариации. Тяхната гъвкавост доведе до създаването на множество варианти за решаване на всякакви проблеми. Когато се използват правилно, дърветата за двоично търсене са страхотен актив.

Дърветата за двоично търсене: Перфектната отправна точка

Един от основните начини за оценка на експертния опит на инженера е чрез тяхното познаване и прилагане на структури от данни. Структурите от данни са полезни и могат да помогнат за създаването на по-ефективна система. Дърветата за двоично търсене са чудесно въведение в структурите от данни за всеки разработчик, който започва.

15 метода за масив на JavaScript, които трябва да овладеете днес

Искате да разберете JavaScript масивите, но не можете да се справите с тях? Вижте нашите примери за JavaScript масиви за насоки.

Прочетете Следващото

За автора