Egy csomópont törlése egy AVL fából hasonló a bináris keresési fához. A törlés megzavarhatja az AVL fa egyensúlytényezőjét, ezért a fát újra ki kell egyensúlyozni az AVL-ség fenntartása érdekében. Ebből a célból forgatásokat kell végrehajtanunk. A kétféle forgatás az L forgatás és az R forgás. Itt az R forgatásokról fogunk beszélni. Az L elforgatások a tükörképeik.

Ha a törölni kívánt csomópont a kritikus csomópont bal oldali részfájában található, akkor L elforgatást kell alkalmazni, ha egyébként a törölni kívánt csomópont a kritikus csomópont jobb oldali részfájában található. , akkor az R elforgatás kerül alkalmazásra.

Nézzük meg, hogy A a kritikus csomópont, és B a gyökércsomópontja a bal oldali részfájának. Ha az A jobb oldali részfájában található X csomópontot törölni kell, akkor három különböző helyzet adódhat:

R0 forgás (B csomópont 0 egyensúlyi tényezővel rendelkezik)

Ha a B csomópont 0 egyensúlytényezővel rendelkezik, és az A csomópont egyensúlyi tényezője az X csomópont törlésekor megzavarodik, akkor a fa R0 forgatást használó fa elforgatásával kerül újraegyensúlyozásra.

A kritikus A csomópont jobbra kerül, és a B csomópont lesz a fa gyökere, T1 pedig a bal oldali részfa. A T2 és T3 részfák az A csomópont bal és jobb oldali részfáivá válnak. Az R0 elforgatás folyamatát a következő kép mutatja be.

Példa:

Törölje a 30-as csomópontot a következő képen látható AVL-fából.

Megoldás

Ebben az esetben a B csomópont egyensúlyi tényezője 0, ezért a fa R0 elforgatással kerül elforgatásra, ahogy az a következő képen látható. A B(10) csomópont lesz a gyökér, míg az A csomópont jobbra kerül. A B csomópont jobb gyermeke mostantól az A csomópont bal gyermeke lesz.

.net tutorial

R1 forgás (B csomópont 1-es egyensúlyi tényezővel rendelkezik)

Az R1 elforgatást akkor kell végrehajtani, ha a B csomópont egyensúlytényezője 1. Az R1 forgatásnál az A kritikus csomópont jobbra kerül, amelynek bal és jobb gyermeke a T2 és T3 részfa. A T1-et a B csomópont bal oldali részfájaként kell elhelyezni.

Az R1 forgásának folyamata a következő képen látható.

Példa

Törölje az 55-ös csomópontot a következő képen látható AVL-fából.

Megoldás:

Az 55-ös törlése az AVL-fából megzavarja az 50-es csomópont egyensúlyi tényezőjét, azaz az A csomópontot, amely a kritikus csomóponttá válik. Ez az R1 forgatás feltétele, amelyben az A csomópont jobbra kerül (az alábbi képen látható). B jobb oldala most A bal baljává válik (azaz 45).

A megoldás folyamatát a következő kép mutatja.

R-1 forgatás (B csomópont egyensúlyi tényezője -1)

R-1 forgatást kell végrehajtani, ha a B csomópont egyensúlyi tényezője -1. Ezt az esetet ugyanúgy kezeljük, mint az LR forgatást. Ebben az esetben a C csomópont, amely a B csomópont jobb gyermeke, a fa gyökércsomópontjává válik, melynek bal és jobb gyermeke B és A.

A T1, T2 részfák B bal és jobb oldali részfáivá, míg T3, T4 A bal és jobb oldali részfáivá válnak.

java tömb

Az R-1 forgatás folyamata a következő képen látható.

Példa

Törölje a 60-as csomópontot a következő képen látható AVL-fából.

Megoldás:

ebben az esetben a B csomópont egyensúlyi tényezője -1. A 60 csomópont törlése megzavarja az 50 csomópont egyensúlyi tényezőjét, ezért azt R-1 elforgatni kell. A C, azaz a 45 csomópont lesz a fa gyökere, amelynek a B(40) és A(50) csomópont a bal és jobb oldali gyermeke.