Премахване на двоично търсене дърво 1

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

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

Книга: основните алгоритми и структури от данни в Делфи

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

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

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

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

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

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

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

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

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

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

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

Обявата 8.15. Премахване на двоично търсене дърво

функция TtdBinarySearchTree.bstFindNodeToDelete (aItem. указател)