Историята на този текст е следната. Детето получи задачата да програмира btree. Понякога му помагам. Реших, че това е тривиално. Но опитите за бързо разрешаване на проблема бяха неуспешни. Търсенията за разумно описание и/или код също бяха напразни. Синът ми премина тест отдавна, но параноичният ми характер ме накара да разреша проблема. Може би някой ще дойде по-удобно.

sudo

Балансирано дърво за търсене btree (B дърво) I

не дават определение. Намирането му не е трудно. Търсене, вмъкване на ключ са тривиални.

Премахване на ключ от btree

Възел ще бъде наречен празен, ако съдържа ключове t-1, т.е. никой ключ не може да бъде изтрит от него. Коренът по дефиниция никога не е празен. Също така поддърво ще бъде наречено празно, ако всичките му възли са празни. Празно дърво е подредено еднозначно. Съответно, пълен възел ще бъде наречен възел с броя на ключовете 2t-1. Броят на ключовете в празното дърво очевидно е
(t-1) * (1 + t + t ^ 2 +. + t ^ h) = t ^ (h + 1) -1, където h е височината на дървото (височина на корена = 0).
Ако вмъкването на ключ в btree е недвусмислено, тогава изтриването е двусмислено.
Ако възелът, където се намира намереният ключ, е листен, тогава ако възелът не е празен, ключовете се преместват, заменяйки изтрития:

Ако възелът е празен, трябва да преобразувате дървото, така че да стане празно.

Наречете този ключ на десен лист отляволистен възел, в който натискаме първо се движим към левия потомък на този ключ, а след това към листния възел според последните потомци. По същия начин ляв лист отдясно е решителен. Първо към десния поток, после до нула потомци.

Ако възелът не е листен, този ключ има десен и ляв потомък и родител (ако не е коренът), в който нашият възел е на позиция i. По дефиницията на btree всички ключове на лявото дете са по-малки, а всички ключове на дясното дете са по-големи от този ключ. Без да нарушавам определението за btree, кой ключ може да замени изтрития?

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

За да решите проблема с превръщането на този листен възел в непразен, помислете за две трансформации на btree: сливане и превес. Ако този възел не е празен и и двамата потомци на този ключ са празни, можете да направите трансформация на сливане. Този ключ се изтрива от неговия възел, прави се един възел от него и неговите потомци. Тъй като коренът никога не е празен, ако всички възли са празни и коренът има един ключ, се извършва обединяване и старият корен се изтрива.

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

По същия начин има предимство вдясно. Височината на ръба е от една до височината на дървото.

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

Ляв брат - възел на същото ниво вляво от текущия. Братята имат общ прародител и ключа на общ прародител. Чрез ключа на общия прародител ключовете се претеглят отново.

Ако левият брат не е празен, ние надвишаваме ключа. Проблемът е решен. Ако левият брат или сестра е празен, но родителят не е празен, обединете. Проблемът е решен. Ако и родителят е празен, и левият брат, ние рекурсивно искаме завъртането от родителя, а след това от левия (който и да е) брат.

По същия начин се извършва кримпване вляво. Неяснотата на изтриването е дали можете първо да изкривите надясно или наляво. Можете също така първо да заявите предимство, а след това да обедините или обратно.

За да докаже нежелание, но интуицията показва, че тя винаги е изкривена.

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

Като едно от заключенията може да се твърди, че за да се ускори премахването на ключовете, е желателно да се запазят листните възли непразни. Тези. в свободното си време от важни въпроси, направете компресия на дървото надолу чрез сливане. Няма смисъл да надделяваме.

Можете също така да предложите някаква оптимизация.

Btree - дърво е кратко, но широко. Разходката по клоните може да бъде отгоре. За оптимизация можете да предложите параметър клон тегло - броят на ключовете в него. Тъй като теглото на празното дърво е константа за една височина, можете да проверите теглото, докато вървите по клоните. Ако е равно на теглото на празно дърво, там няма какво да се прави, ако не, ще спрем на него, определено ще натиснем един клавиш от него. Управлението на теглото е просто. Когато се вмъкне ключ, теглото на всички възли по пътя на вмъкването се увеличава; когато текущият възел и всички родители бъдат изтрити, той се намалява до корена.

Сбогувам се с това, надявам се, че не се уморих. Приложен е списък на C ++ (без оптимизация и не прекалено пениран).

PS Доказателството е узряло.

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

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