Mielőtt megértené a Piros-fekete fa és AVL fa különbségeket, külön tudnunk kell a vörös-fekete fáról és az AVL fáról.

Mi az a vörös-fekete fa?

A vörös-fekete fa önkiegyensúlyozott bináris keresőfa amelyben minden csomópont egy plusz információ bitet tartalmaz, amely a csomópont színét jelöli. A csomópont színe lehet piros vagy fekete, a csomópont által tárolt bitinformációtól függően.

Tulajdonságok

A vörös-fekete fához tartozó tulajdonságok a következők:

• A fa gyökércsomópontja fekete legyen.
• Egy vörös csomópontnak csak fekete gyermekei lehetnek. Vagy azt is mondhatjuk, hogy két szomszédos csomópont nem lehet piros színű.
• Ha a csomópontnak nincs bal vagy jobb gyermeke, akkor ezt a csomópontot levélcsomópontnak nevezzük. Tehát a bal és jobb oldali gyerekeket az úgynevezett levélcsomópont alá helyezzük nulla

Egy levélcsomópont fekete mélysége vagy fekete magassága meghatározható a fekete színek számaként, amellyel a levél csomópontjától a gyökércsomópont felé haladva találkozunk. A vörös-fekete fa egyik legfontosabb tulajdonsága, hogy minden levélcsomópontnak azonos feketemélységűnek kell lennie.

legjobb autó a világon

Értsük meg ezt a tulajdonságot egy példán keresztül.

A fenti fában öt csomópont található, amelyek közül az egyik piros, a másik négy pedig fekete. A fenti fán három levélcsomópont található. Most kiszámítjuk az egyes levélcsomópontok fekete mélységét. Megfigyelhetjük, hogy mindhárom levélcsomó fekete mélysége 2; ezért vörös-fekete fa.

Ha a fa nem felel meg a fenti három tulajdonság egyikének sem, akkor nem vörös-fekete fa.

Vörös-fekete fa magassága

Tekintsük h-t az n csomóponttal rendelkező fa magasságának. Mi lenne n legkisebb értéke?. Az n értéke akkor a legkisebb, ha az összes csomópont fekete. Ha a fa tartalmazza az összes fekete csomópontot, akkor a fa egy teljes bináris fa lenne. Ha egy teljes bináris fa magassága h, akkor egy fa csomópontjainak száma:

mergesort java

n = 2 óra -1

Mi lenne n legnagyobb értéke?

Az n értéke akkor a legnagyobb, ha minden fekete csomópontnak két piros gyermeke van, de a piros csomópontnak nem lehet vörös gyermeke, így fekete gyermekei lesznek. Ily módon a fekete és a vörös gyerekek váltakozó rétegei vannak. Tehát, ha a fekete rétegek száma h, akkor a vörös rétegek száma is h; így a fa teljes magassága 2 óra lesz. A csomópontok teljes száma:

n = 2*2h-1

Mi az AVL fa?

An AVL fa egy önkiegyensúlyozó bináris keresőfa, ha megfigyeljük az alábbi esetet, ami egy bináris keresőfa és egy kiegyensúlyozott fa.

A fenti fában az elem keresésének legrosszabb eseti bonyolultsága O(h), azaz a fa magassága. A fenti esetben a 17 elem kereséséhez végzett összehasonlítások száma 4, és a fa magassága is 4.

Ha figyelembe vesszük a ferde bináris fát, az alábbiak szerint:

A fenti jobb oldali ferde fában a 17 elem kereséséhez végzett összehasonlítások száma 5, és a fában lévő elemek száma is 5. Ezért elmondhatjuk, hogy ha a fa egy ferde bináris fa, akkor az időbonyolultság. O(n) lenne.

Most ki kell egyensúlyoznunk ezeket a ferde fákat, hogy O(h) időbonyolításúak legyenek. Van egy olyan kifejezés, amely a egyensúlyi tényező , amely a bináris keresési fa önkiegyensúlyozására szolgál. Az egyensúlyi tényező a következőképpen számítható ki:

Az egyensúlytényező értéke 1, 0 vagy -1 lehet. Ha a bináris fa minden csomópontjának értéke 1, 0 vagy -1, akkor azt a fát kiegyensúlyozottnak mondjuk. bináris fa vagy AVL fa.

A fát tökéletesen kiegyensúlyozott fának nevezzük, ha az egyes csomópontok egyensúlytényezője 0. Az AVL fa egy majdnem kiegyensúlyozott fa, mivel a fa minden csomópontjának egyensúlytényezője 1, 0 vagy -1.

A vörös-fekete fa és az AVL fa közötti különbségek.

A következő különbségek vannak a vörös-fekete fa és az AVL fa között:

mi az a klaszterezés

Bináris keresőfa

A piros-fekete fa egy bináris keresőfa, az AVL fa pedig egy bináris keresőfa is.

Szabályok

A következő szabályok érvényesek egy vörös-fekete fára:

1. A vörös-fekete fa csomópontja vagy piros vagy fekete színű.
2. A gyökércsomópont színe fekete legyen.
3. A szomszédos csomópontok nem lehetnek pirosak. Más szóval azt mondhatjuk, hogy a vörös csomópontnak nem lehetnek vörös gyermekei, de a fekete csomópontnak lehetnek fekete gyermekei.
4. Minden útvonalon ugyanannyi fekete csomópont legyen; akkor csak egy fa tekinthető vörös-fekete fának.
5. A külső csomópontok a nulla csomópontok, amelyek mindig fekete színűek.

Az AVL fa szabálya:

Minden csomópont egyensúlyi tényezőjének -1, 0 vagy 1 legyen.

Példa

A fenti ábrán ellenőriznünk kell, hogy a fa vörös-fekete fa-e vagy sem. Ennek ellenőrzéséhez először meg kell vizsgálnunk, hogy a fa bináris keresőfa-e vagy sem. Ahogy a fenti ábrán is megfigyelhetjük, hogy a bináris keresőfa minden tulajdonságát kielégíti; ezért ez egy bináris keresőfa. Másodszor, ellenőriznünk kell, hogy megfelel-e a fent említett szabályoknak vagy sem. A fenti fa mind a fenti öt szabálynak megfelel; ezért arra a következtetésre jut, hogy a fenti fa vörös-fekete fa.

A fenti ábrán ellenőriznünk kell, hogy a fa AVL fa-e vagy sem. Mivel minden csomópontnak van egy egyensúlyi tényezője -1, 0 vagy 1, ezért ez egy AVL fa.

Hogyan tekinthető a fa kiegyensúlyozott fának vagy sem?

Piros-fekete fa esetében, ha a fenti szabályok teljesülnek, feltéve, hogy egy fa bináris keresőfa, akkor a fát vörös-fekete fának mondjuk.

Az AVL fa esetében, ha az egyensúlytényező -1, 0 vagy 1, akkor a fenti fát AVL fának mondjuk.

bash tömbök

Kiegyensúlyozáshoz használt eszközök

Ha a fa nincs kiegyensúlyozott, akkor két eszközt használnak a fa kiegyensúlyozására egy piros-fekete fában:

Átszínezés Forgás

Ha a fa nincs kiegyensúlyozott, akkor egy eszközt használnak a fa kiegyensúlyozására az AVL fában:

Forgás

Melyik művelethez hatékony

A Red-Black fa esetében a beillesztési és törlési műveletek hatékonyak. Ha a fa az átszínezés során kiegyensúlyozottá válik, akkor a beillesztési és törlési műveletek hatékonyak a piros-fekete fában.

Az AVL fa esetében a keresési művelet hatékony, mivel egyetlen eszközre van szükség a fa kiegyensúlyozásához.

Időbeli összetettség

A piros-fekete fa esetében az összes művelet, azaz a beillesztés, törlés és keresés időbeli összetettsége O(logn).

Az AVL fa esetében az összes művelet, azaz a beillesztés, törlés és keresés időbonyolítása O(logn).

Értsük meg a táblázatos formában lévő különbségeket.