Vörös-fekete fa: Saját kiegyensúlyozott bináris keresési fák példákkal magyarázva

Mi az a piros-fekete fa?

A Red-Black Tree egyfajta önkiegyensúlyozó bináris keresési fa (BST). A vörös-fekete fában minden csomópont a következő szabályokat követi:

  1. Minden csomópontnak két gyermeke van, vörös vagy fekete színnel.
  2. Minden fa levélcsomópont mindig fekete.
  3. Minden vörös csomópont mindkét gyermeke fekete színű.
  4. Nincs két szomszédos piros csomópont (egy piros csomópontnak nem lehet piros szülője vagy piros gyermeke).
  5. A gyökértől a falevél csomópontig minden útnak ugyanannyi fekete csomópontja van (az úgynevezett "fekete magasság").

Beillesztés vörös-fekete fákba

A csomópont kezdetben egy piros-fekete fába kerül, mint bármelyik bináris keresési fa. Ezután az új csomópont piros színt kap. A csomópont beillesztése után a fát érvényesíteni kell, hogy megbizonyosodjon arról, hogy az öt tulajdonság egyikét sem sértették meg. Ha egy tulajdonságot megsértettek, három lehetséges eset van, amelyek vagy bal, jobb irányú és / vagy a csomópontok újraszínezését igénylik. Az esetek az aktuális csomópont "nagybátyjától" függenek. Pontosabban, hogy a "bácsi" csomópont fekete vagy piros-e. A behelyezéssel kapcsolatos további információkért a három eset itt található.

Balra hajló vörös – fekete fa

A balra hajló vörös – fekete (LLRB) fa egyfajta önkiegyensúlyozó bináris kereső fa. Ez a vörös-fekete fa változata, és ugyanolyan aszimptotikus bonyolultságot garantál a műveleteknél, de úgy lett kialakítva, hogy könnyebben kivitelezhető legyen.

A balra hajló vörös-fekete fák tulajdonságai

Az összes javasolt vörös-fekete fa algoritmust a legrosszabb keresési idő jellemzi, amelyet egy log N kis konstans többszöröse határol az N kulcsú fán, és a gyakorlatban megfigyelt viselkedés jellemzően ugyanaz a többszörös, mint a legrosszabb esetben kötött, közel az optimális log N vizsgált csomópont, amely egy tökéletesen kiegyensúlyozott fán figyelhető meg.

Pontosabban egy balra hajló vörös-fekete 2-3 fában, amely N véletlenszerű kulcsból épül fel: -> Egy véletlenszerű sikeres keresés megvizsgálja log2 N- 0,5 csomópont. -> Az átlagos famagasság kb2 log2 N