Внедряване на двоично дърво за търсене

2024 Автор: Angel Austin | [email protected]. Последно модифициран: 2023-12-17 05:17

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

Често се нарича BST, което има специално свойство: възлите, по-големи от корена, са разположени вдясно от него, а по-малките отляво.

Обща теория и терминология

В едно двоично дърво за търсене всеки възел, с изключение на корена, е свързан чрез насочен ръб от един възел към друг, който се нарича родител. Всеки от тях може да бъде свързан с произволен брой възли, наречени деца. Възлите без "деца" се наричат листа (външни възли). Елементите, които не са листа, се наричат вътрешни. Възлите със същия родител са братя и сестри. Най-горният възел се нарича корен. В BST задайте елемент на всеки възел и се уверете, че има специално зададено свойство за тях.

Терминология на дървото:

Дълбочината на възел е броят на ръбовете, дефинирани от корена до него.
Височината на възел е броят на ръбовете, дефинирани от него до най-дълбокия лист.
Височината на дървото се определя от височината на корена.
Дървото за двоично търсене е специален дизайн, осигурява най-доброто съотношение на височина и брой възли.
Височина h с N възли най-много O (log N).

Можете лесно да докажете това, като преброите възлите на всяко ниво, започвайки от корена, като приемем, че съдържа най-големия брой от тях: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Решаването на това за h дава h=O (log n).

Предимства на дървото:

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

Метод на търсене

Общо взето, за да определите дали дадена стойност е в BST, стартирайте двоично дърво за търсене в неговия корен и определете дали отговаря на изискванията:

бъдете в основата;
бъдете в лявото поддърво на корен;
в дясното поддърво на корен.

Ако нито един основен регистър не е удовлетворен, се извършва рекурсивно търсене в съответното поддърво. Всъщност има две основни опции:

Дървото е празно - върне false.
Стойността е в основния възел - върнете true.

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

С други думи, има връзка между броя на възлите в BST и височината на дървото, в зависимост от неговата "форма". В най-лошия случай възлите имат само едно дете, а балансираното двоично дърво за търсене по същество е свързан списък. Например:

Това дърво има 5 възела и височина=5. Намирането на стойности в диапазона 16-19 и 21-29 ще изисква следния път от корена до листа (възела, съдържащ стойността 20), т.е., ще отнеме време, пропорционално на броя на възлите. В най-добрия случай всички те имат 2 деца и листата са разположени на една и съща дълбочина.

Това двоично дърво за търсене има 7 възела и височина=3. Като цяло дърво като това (пълно дърво) ще има височина приблизително log 2 (N), където N е броят на възлите в дървото. Стойността на log 2 (N) е броят пъти (2), които N може да бъде разделено, преди да се достигне нула.

Обобщаване: най-лошото време, необходимо за търсене в BST, е O (височина на дървото). Най-лошото "линейно" дърво е O(N), където N е броят на възлите в дървото. В най-добрия случай "пълно" дърво е O(log N).

BST двоично вмъкване

Чудя се къде трябва да бъденовият възел се намира в BST, трябва да разберете логиката, той трябва да бъде поставен там, където потребителят го намери. Освен това трябва да запомните правилата:

Дубликатите не са разрешени, опитът за вмъкване на дублирана стойност ще доведе до изключение.
Общественият метод за вмъкване използва помощен рекурсивен "помощник" метод за действително вмъкване.
Възел, съдържащ нова стойност, винаги се вмъква като лист в BST.
Общественият метод за вмъкване връща void, но помощният метод връща BSTnode. Прави това, за да се справи със случая, когато възелът, прехвърлен към него, е нулев.

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

Изтриване в двоичен алгоритъм

Както може да очаквате, изтриването на елемент включва намиране на възел, който съдържа стойността, която трябва да бъде премахната. Има няколко неща в този код:

BST използва помощен, претоварен метод за изтриване. Ако елементът, който търсите, не е в дървото, тогава помощният метод в крайна сметка ще бъде извикан с n==null. Това не се счита за грешка, дървото просто не се променя в този случай. Помощният метод за изтриване връща стойност - указател към актуализираното дърво.
Когато лист е премахнат, премахването от дървото за двоично търсене задава съответния дъщерен указател на неговия родител на null или корена на нула, ако този, който се премахва, евъзелът е корен и няма деца.
Обърнете внимание, че извикването за изтриване трябва да бъде едно от следните: root=delete (корен, ключ), n.setLeft (изтриване (n.getLeft (), ключ)), n.setRight (delete(n. getRight(), ключ)). По този начин и в трите случая е правилно, че методът delete просто връща null.
Когато търсенето на възела, съдържащ стойността, която трябва да бъде изтрита, успее, има три опции: възелът, който трябва да бъде изтрит, е лист (няма деца), възелът, който трябва да бъде изтрит, има едно дете, има две деца.
Когато възелът, който се премахва, има едно дъщерно, можете просто да го замените с дете, връщайки указател към детето.
Ако възелът, който трябва да бъде изтрит, има нула или 1 деца, тогава методът за изтриване ще "следва пътя" от корена до този възел. Така че най-лошото време е пропорционално на височината на дървото, както за търсене, така и за вмъкване.

Ако възелът, който трябва да бъде премахнат, има две деца, се предприемат следните стъпки:

Намерете възела за изтриване, следвайки пътя от корена до него.
Намерете най-малката стойност на v в дясното поддърво, като продължите по пътя към листа.
Рекурсивно премахнете стойността на v, следвайте същия път като в стъпка 2.
Така в най-лошия случай пътят от корена до листа се изпълнява два пъти.

Ред на траверсите

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

дълбочина на пресичане;
първи пас.

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

Има три различни типа пресичане на дълбочина:

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

Пример за четири обиколки на двоично дърво за търсене:

Предварителна поръчка - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
Поръчка - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
Поръчка на ниво - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Фигурата показва реда, в който се посещават възлите. Числото 1 е първият възел в конкретен обход, а 7 е последният възел.

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

Навигация и отстраняване на грешки

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

За да се разбере всичко това, се използва функция, която проверява дали дървото може да е правилно и помага да се намерят много грешки. Например, той проверява дали родителският възел е дъщерен възел. С assert(is_wellformed(root)) много грешки могат да бъдат уловени преждевременно. Използвайки няколко дадени точки на прекъсване в тази функция, можете също да определите точно кой указател е грешен.

Function Konsolenausgabe

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

За да направите това, първо трябва да определите каква информация ще бъде изведена през възела.
И също така трябва да знаете колко широко и високо е дървото, за да отчетете колко място да оставите.
Следните функции изчисляват тази информация за дървото и всяко поддърво. Тъй като можете да пишете в конзолата ред по ред, ще трябва също да отпечатате дървото ред по ред.
Сега се нуждаем от друг начин за тегленецялото дърво, а не само ред по ред.
С помощта на функцията dump можете да прочетете дървото и значително да подобрите алгоритъма на изхода, що се отнася до скоростта.

Тази функция обаче ще бъде трудна за използване при големи дървета.

Конструктор и деструктор за копиране

Тъй като дървото не е тривиална структура от данни, по-добре е да се внедри конструктор за копиране, деструктор и оператор за присвояване. Деструкторът е лесен за изпълнение рекурсивно. За много големи дървета може да се справи с "препълване на купчина". В този случай тя се формулира итеративно. Идеята е да се премахне листът, представляващ най-малката стойност от всички листа, така че да е от лявата страна на дървото. Отрязването на първите листа създава нови и дървото се свива, докато накрая престане да съществува.

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

С този метод изпълнението на дървото за двоично търсене винаги е в здраво състояние и може да бъде премахнато от деструктора дори в непълно състояние. Ако възникне изключение, всичко, което трябва да направите, е да инструктирате деструктора да изтрие полуготовото дърво. оператор на присвояванеможе лесно да се приложи с помощта на Copy & Swap.

Създаване на двоично дърво за търсене

Оптималните двоични дървета за търсене са невероятно ефективни, ако се управляват правилно. Някои правила за двоични дървета за търсене:

Родителски възел има най-много 2 дъщерни възела.
Левият дъщерен възел винаги е по-малък от родителския възел.
Валиден дъщерен възел винаги е по-голям или равен на родителския възел.

Масивът, който ще се използва за изграждане на дървото за двоично търсене:

Основен целочислен масив от седем стойности в несортиран ред.
Първата стойност в масива е 10, така че първата стъпка в изграждането на дървото е да се създаде 10 коренен възел, както е показано тук.
С набор от основни възли, всички други стойности ще бъдат дъщерни на този възел. Позовавайки се на правилата, първата стъпка, която трябва да направите, за да добавите 7 към дървото, е да го сравните с основния възел.
Ако стойността 7 е по-малка от 10, тя ще стане левият дъщерен възел.
Ако стойността 7 е по-голяма или равна на 10, тя ще се премести надясно. Тъй като е известно, че 7 е по-малко от 10, то се обозначава като ляв дъщерен възел.
Рекурсивно извършвайте сравнения за всеки елемент.
Следвайки същия модел, извършете същото сравнение с 14-та стойност в масива.
Сравняване на стойността 14 с основния възел 10, като се знае, че 14 е правилното дете.
Разхождайки се през масива,ела до 20.
Започнете, като сравните масива с 10, което от двете е по-голямо. Така че преместете се вдясно и го сравнете с 14, той е над 14 и няма деца вдясно.
Сега има стойност 1. Следвайки същия модел като другите стойности, сравнете 1 с 10, преместете се наляво и сравнете със 7 и накрая с 1 ляво дете на 7-ия възел.
Ако стойността е 5, сравнете я с 10. Тъй като 5 е по-малко от 10, преминете наляво и я сравнете със 7.
Знаейки, че 5 е по-малко от 7, продължете надолу по дървото и сравнете 5 с 1 стойност.
Ако 1 няма деца и 5 е по-голямо от 1, тогава 5 е валидно дете на 1 възел.
Накрая вмъкнете стойността 8 в дървото.
Когато 8 е по-малко от 10, преместете го наляво и го сравнете със 7, 8 е по-голямо от 7, така че го преместете надясно и завършете дървото, правейки 8 правилно дете на 7.

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

Потенциални проблеми с двоично търсене

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

Ако се опитате да стартирате алгоритъм на двоично дърво за търсене на това дърво, той ще работи точно така, сякаш просто се повтаря през масива, докато се намери желаната стойност. Силата на двоичното търсене се крие във възможността за бързо филтриране на нежелани стойности. Когато едно дърво не е балансирано, то няма да осигури същите предимства като балансирано дърво.

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

Примери за изчисление на двоично търсене

Трябва да определим какъв вид дърво ще се получи, ако 25 се вмъкне в следното двоично дърво за търсене:

5 15

/ /

2 12 20

При вмъкване на x в дърво T, което все още не съдържа x, ключът x винаги се поставя в нов лист. Във връзка с това новото дърво ще изглежда така:

5 15

/ /

2 12 20

Какъв вид дърво бихте получили, ако вмъкнете 7 в следното двоично дърво за търсене?

5 15

/ /

2 12 20

Отговор:

5 15

/ / /

2 7 12 20

Дървото за двоично търсене може да се използва за съхраняване на всеки обект. Предимството на използването на двоично дърво за търсене вместо свързан списък е, че ако дървото е разумно балансирано и повече прилича на "пълно" дърво, отколкото на "линейно", вмъкването, търсенето и всички операции за изтриване могат да бъдат приложени, за да се изпълняват в O(log N) време.