Het verwijderen van een knooppunt uit een AVL-boom is vergelijkbaar met dat in een binaire zoekboom. Het verwijderen kan de balansfactor van een AVL-boom verstoren en daarom moet de boom opnieuw in evenwicht worden gebracht om de AVL-status te behouden. Voor dit doel moeten we rotaties uitvoeren. De twee soorten rotaties zijn L-rotatie en R-rotatie. Hier zullen we R-rotaties bespreken. L-rotaties zijn de spiegelbeelden ervan.

Als het knooppunt dat moet worden verwijderd aanwezig is in de linker subboom van het kritieke knooppunt, dan moet L-rotatie worden toegepast. Anders moet het knooppunt dat moet worden verwijderd aanwezig zijn in de rechter subboom van het kritieke knooppunt. , wordt de R-rotatie toegepast.

Laten we bedenken dat A het kritieke knooppunt is en B het hoofdknooppunt van de linker subboom. Als knooppunt X, aanwezig in de rechter deelboom van A, moet worden verwijderd, kunnen er drie verschillende situaties zijn:

R0-rotatie (knooppunt B heeft balansfactor 0)

Als knooppunt B een balansfactor van 0 heeft en de balansfactor van knooppunt A wordt verstoord bij het verwijderen van knooppunt X, dan wordt de boom opnieuw in evenwicht gebracht door de boom te roteren met behulp van R0-rotatie.

Het kritieke knooppunt A wordt naar rechts verplaatst en knooppunt B wordt de wortel van de boom met T1 als linker subboom. De subbomen T2 en T3 worden de linker en rechter subboom van knooppunt A. Het proces dat betrokken is bij R0-rotatie wordt weergegeven in de volgende afbeelding.

Voorbeeld:

Verwijder knooppunt 30 uit de AVL-boom die in de volgende afbeelding wordt weergegeven.

Oplossing

In dit geval heeft knooppunt B een balansfactor 0. Daarom wordt de boom geroteerd met behulp van R0-rotatie, zoals weergegeven in de volgende afbeelding. Het knooppunt B(10) wordt de wortel, terwijl het knooppunt A naar rechts wordt verplaatst. Het rechterkind van knooppunt B wordt nu het linkerkind van knooppunt A.

js onclick

R1 Rotatie (knooppunt B heeft balansfactor 1)

R1-rotatie moet worden uitgevoerd als de balansfactor van knooppunt B 1 is. Bij R1-rotatie wordt het kritische knooppunt A naar rechts verplaatst met subbomen T2 en T3 als respectievelijk het linker en rechter kind. T1 moet worden geplaatst als de linker subboom van knooppunt B.

Het proces dat betrokken is bij R1-rotatie wordt weergegeven in de volgende afbeelding.

Voorbeeld

Verwijder knooppunt 55 uit de AVL-boom die in de volgende afbeelding wordt weergegeven.

Oplossing :

Het verwijderen van 55 uit de AVL-boom verstoort de balansfactor van knooppunt 50, d.w.z. knooppunt A dat het kritische knooppunt wordt. Dit is de toestand van R1-rotatie waarbij knooppunt A naar rechts wordt verplaatst (weergegeven in de onderstaande afbeelding). De rechterkant van B is nu de linkerkant van A geworden (dus 45).

Het proces dat bij de oplossing betrokken is, wordt weergegeven in de volgende afbeelding.

R-1 Rotatie (knooppunt B heeft balansfactor -1)

R-1-rotatie moet worden uitgevoerd als knooppunt B een balansfactor -1 heeft. Dit geval wordt op dezelfde manier behandeld als LR-rotatie. In dit geval wordt knooppunt C, het rechterkind van knooppunt B, het hoofdknooppunt van de boom met respectievelijk B en A als linker- en rechterkinderen.

De deelbomen T1, T2 worden de linker en rechter deelbomen van B, terwijl T3 en T4 de linker en rechter deelbomen van A worden.

mijnlivericket

Het proces dat betrokken is bij R-1-rotatie wordt weergegeven in de volgende afbeelding.

Voorbeeld

Verwijder knooppunt 60 uit de AVL-boom die in de volgende afbeelding wordt weergegeven.

Oplossing:

in dit geval heeft knooppunt B een balansfactor -1. Het verwijderen van knooppunt 60 verstoort de balansfactor van knooppunt 50 en moet daarom R-1 worden geroteerd. Het knooppunt C, d.w.z. 45, wordt de wortel van de boom met het knooppunt B(40) en A(50) als het linker en rechter kind.