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.
