Algoritmus egy csomópont törlésére a btree-ről

A szöveg története a következő. A gyermek feladata a btree programozása volt. Néha segítek neki. Úgy döntött, hogy ez triviális. De a probléma gyors megoldására irányuló kísérletek sikertelenek voltak. Bármilyen ésszerű leírás és/vagy kód keresése szintén hiábavaló volt. A fiam már rég letette a tesztet, de paranoiás természetem arra késztetett, hogy megoldjam a problémát. Talán valaki jól jön.

Kiegyensúlyozott keresőfa btree (B fa) I

ne adj definíciót. Megtalálása nem nehéz. A keresés, a kulcs beillesztése triviális.

Kulcs eltávolítása a btree-ről

Egy csomópontot üresnek nevezünk, ha t-1 kulcsokat tartalmaz, vagyis egyetlen kulcs sem törölhető belőle. A gyökér definíció szerint soha nem üres. Ezenkívül egy alfát üresnek nevezünk, ha az összes csomópontja üres. Egy üres fát egyértelműen elrendeznek. Ennek megfelelően egy teljes csomópontot egy csomópontnak nevezünk, amelynek száma a 2t-1 kulcsok száma. Egy üres fa kulcsainak száma nyilvánvaló
(t-1) * (1 + t + t ^ 2 +. + t ^ h) = t ^ (h + 1) -1, ahol h a fa magassága (gyökérmagasság = 0).
Ha a btree kulcsbeillesztése egyértelmű, akkor a törlés kétértelmű.
Ha az a csomópont, ahol a megtalált kulcs található, lombos, akkor ha a csomópont nem üres, akkor a kulcsok eltolódnak, helyettesítve a töröltet:

Ha a csomópont üres, akkor úgy kell átalakítania a fát, hogy az ne legyen üres.

Hívja ezt a kulcsot a jobb levél a bal oldalonlevélcsomópont, amelybe először a kulcs bal leszármazottjához, majd az utolsó leszármazottak szerint a levélcsomópontig tolunk. Hasonlóképpen a bal oldali lap a jobb oldalon van határozott. Először a megfelelő folyamra, majd nulla leszármazottra.

Ha a csomópont nem leveles, akkor ennek a kulcsnak van egy jobb és bal leszármazottja és szülője (ha nem a gyökér), amelyben a csomópontunk az i pozícióban van. A btree definíciója szerint a bal gyermek összes billentyűje kisebb, a jobb gyermeké pedig ennél a kulcsnál nagyobb. A btree definíciójának megsértése nélkül melyik kulcs helyettesítheti a töröltet?

Az ábrán a kékkel jelölt billentyűk ennél kisebbek, a sárga ennél több. A törlendő kulcsot csak a legkisebb vagy a legnagyobb közül lehet kicserélni. Az ábrán piros, illetve kék színnel karikázzák be őket. Az első a bal oldali lap utolsó kulcsa, a második a bal oldali lap első kulcsa a jobb oldalon. Ha egyikük nem üres, egyszerűen cserélje ki a törölni kívánt kulcsot az egyikre, és törölje a pótkulcsot az eredeti lapról, ha nem, akkor térjen vissza arra a feladatra, hogy miként lehet a levélcsomópontot nem üresé tenni.

Annak a problémának a megoldásához, hogy ez a levélcsomópont ne legyen üres, vegyen fontolóra két btranszformációt: egyesítés és túlsúly. Ha ez a csomópont nem üres, és a kulcs mindkét leszármazottja üres, akkor egyesítési transzformációt hajthat végre. Ezt a kulcsot törlik a csomópontjából, egy csomópont készül belőle és leszármazottaiból. Mivel a gyökér soha nem üres, ha az összes csomópont üres, és a gyökérnek egyetlen kulcsa van, akkor egyesítés történik, és a régi gyökér törlõdik.

A második Btree transzformáció előny. Ha a bal oldali jobb oldali lap nem üres ehhez a billentyűhöz, akkor a jobb oldali bal oldali lap nem teljes, akkor elkészítheti a jobb szélét. Ha a jobb oldalon lévő bal lap tele van, hajtson végre osztást. Ezt a kulcsot a jobb oldali bal oldali lap nulla helyzetébe tesszük, egységekkel növelve a benne lévő kulcsok számát. A bal oldali jobb oldali utolsó kulcs segítségével cserélje ki és törölje.

Hasonlóképpen van előnye a jobboldalnak is. Az él magassága egytől a fa magasságáig terjed.

Valójában az algoritmus, hogyan lehet ezt a lapot nem üresé tenni. A folyamatot fa tömörítésnek nevezzük. Fontolja meg a jobb oldali krimpelést.

Bal testvér - egy csomópont ugyanazon a szinten a bal oldaltól. A testvéreknek közös ősük és közös ősük kulcsa van. A közös ős kulcsán keresztül a kulcsokat újra súlyozzák.

Ha a bal testvér nem üres, akkor felülmúljuk a kulcsot. A probléma megoldódott. Ha a bal testvér üres, de a szülő nem üres, egyesítsd. A probléma megoldódott. Ha a szülő is üres és a bal testvér is, rekurzívan kérjük a forgatást a szülőtől, majd a bal (bármelyik) testvértől.

Hasonlóképpen balra krimpelés történik. A törlés kétértelműsége az, hogy először jobbra vagy balra krimpelhet-e. Először is kérhet előnyt, majd egyesülhet, vagy fordítva.

A vonakodás bizonyítására, de az intuíció azt mutatja, hogy mindig göndör.

Emlékeztetni kell arra, hogy egy fa újjáépítésekor a törlésre talált kulcs a fa más csomópontjaiban történt egyesülésekből származhat. De nem tudja elveszíteni a kapcsolatot a pótkulcsokkal.

A következtetések egyikeként azt állíthatjuk, hogy a kulcsok eltávolításának felgyorsítása érdekében kívánatos, hogy a levélcsomópontok ne legyenek mentesek. Azok. Fontos ügyektől való szabadidejében végezze el a fa tömörítését összevonásokkal. Nincs értelme felülmúlni.

Felajánlhat némi optimalizálást is.

Btree - egy fa rövid, de széles. Az ágak mentén járás lehet a fej fölött. Az optimalizálás érdekében felajánlhatja a paraméterág súlyát - a benne lévő kulcsok számát. Mivel egy üres fa súlya állandó egy magasságban, ellenőrizheti a súlyt az ágak mentén járva. Ha megegyezik egy üres fa súlyával, akkor ott nincs mit tenni, ha nem, akkor megállunk rajta, feltétlenül megnyomunk belőle egy gombot. A súlykezelés egyszerű. Kulcs behelyezésekor növekszik az összes csomópont súlya a beszúrási út mentén; az aktuális csomópont és az összes szülő törlésekor a gyökérre csökken.

Búcsúzom ettől, remélem nem fáradtam el. A C ++ lista csatolva van (optimalizálás nélkül és nem is fésült).

PS A bizonyítás beérett.

Ha van legalább egy nem üres lap, akkor mindig átviheti azt a kívántra. Ha nem, és van legalább egy, amely nem üres a lapok felett, akkor elvégezzük az egyesítést. Indukcióval tovább. Tekintettel arra, hogy a gyökér soha nem üres.

Optimalizálási lehetőség is felszínre került. Ha a csomópont, amelyben törölni szeretné a kulcsot, nem üres, és az összes bal és jobb leszármazott üres, a kulcs egyszerűen törlődik, és az utódok összeragadnak. Azok. ha a csomópont nem üres, akkor nem kell tovább mennie, mint a legközelebbi bal és jobb oldali leszármazottak.