streamalism.org

1. Uvod

U ovom uputstvu predstavit ćemo AVL stablo i razmotrit ćemo algoritme za umetanje, brisanje i traženje vrijednosti.

2. Što je AVL stablo?

Stablo AVL, nazvano po izumiteljima Adelson-Velskyju i Landisu, samo je uravnotežljivo binarno stablo pretraživanja (BST).

Stablo samobalansiranja je binarno stablo pretraživanja koje uravnotežuje visinu nakon umetanja i brisanja prema nekim pravilima uravnoteženja.

Najgora vremenska složenost BST-a ovisi o visini stabla. Točnije, najduži put od korijena stabla do čvora. Za BST s N čvorova, recimo da svaki čvor ima samo nula ili jedno dijete. Stoga je njegova visina jednaka N, a vrijeme pretraživanja u najgorem slučaju je O (N). Dakle, naš glavni cilj u BST je zadržati maksimalnu visinu blizu dnevnika (N).

Faktor ravnoteže čvora N je visina (desno (N)) - visina (lijevo (N)). U AVL stablu faktor ravnoteže čvora može biti samo jedna od vrijednosti 1, 0 ili -1.

Definirajmo a Čvor objekt za naše stablo:

javni razred Node {int ključ; visina int; Čvor lijevo; Čvor desno; ...}

Dalje, definirajmo AVLTree:

javna klasa AVLTree {korijen privatnog čvora; void updateHeight (čvor n) {n.height = 1 + Math.max (visina (n.lijevo), visina (n.desno)); } int visina (čvor n) {return n == null? -1: n.visina; } int getBalance (čvor n) {return (n == null)? 0: visina (n.desno) - visina (n.lijevo); } ...}

3. Kako uravnotežiti AVL stablo?

AVL stablo provjerava faktor ravnoteže svojih čvorova nakon umetanja ili brisanja čvora. Ako je faktor ravnoteže čvora veći od jednog ili manji od -1, stablo se ponovno uravnoteži.

Postoje dvije operacije rebalansa stabla:

• desna rotacija i
• lijeva rotacija.

3.1. Desna rotacija

Krenimo s pravom rotacijom.

Pretpostavimo da imamo BST pod nazivom T1, s Y kao korijenskim čvorom, X kao lijevim podređenim dijelom Y i Z kao desnim podređenim dijelom X. S obzirom na karakteristike BST-a, znamo da je X <Z <Y.

Nakon desne rotacije Y, imamo stablo zvano T2 s X kao korijenom i Y kao desno dijete X i Z kao lijevo dijete Y. T2 je i dalje BST jer zadržava redoslijed X <Z <Y .

Pogledajmo pravu operaciju rotacije za našu AVLTree:

Čvor rotateRight (čvor y) {Čvor x = y.left; Čvor z = x.desno; x.desno = y; y.lijevo = z; updateHeight (y); updateHeight (x); povrat x; }

3.2. Lijeva rotacija

Imamo i operaciju lijeve rotacije.

Pretpostavimo BST pod nazivom T1, s Y kao korijenskim čvorom, X kao desnim podređenim dijelom Y i Z kao lijevim podređenim dijelom X. S obzirom na to, znamo da je Y <Z <X.

Nakon lijeve rotacije Y, imamo stablo zvano T2 s X kao korijenom i Y kao lijevim podređenim dijelom X i Z kao desnim podređenim Y. T2 je i dalje BST jer zadržava redoslijed Y <Z <X .

Pogledajmo operaciju lijeve rotacije za naš AVLTree:

Čvor rotateLeft (Node y) {Čvor x = y.desno; Čvor z = x.lijevo; x.lijevo = y; y.desno = z; updateHeight (y); updateHeight (x); povrat x; }

3.3. Tehnike rebalansa

Operacije desne rotacije i lijeve rotacije možemo koristiti u složenijim kombinacijama za održavajte AVL stablo uravnoteženim nakon bilo koje promjene u njegovim čvorovima. U neuravnoteženoj strukturi, najmanje jedan čvor ima faktor ravnoteže jednak 2 ili -2. Pogledajmo kako u tim situacijama možemo uravnotežiti drvo.

Kada je faktor ravnoteže čvora Z 2, podstablo sa Z kao korijenom nalazi se u jednom od ova dva stanja, smatrajući Y pravim podređenim dijelom Z.

U prvom slučaju, visina u desnom djetetu Y (X) veća je od visine lijevog djeteta (T2). Stablo možemo lako uravnotežiti lijevom rotacijom Z.

U drugom slučaju, visina desnog djeteta Y (T4) manja je od visine lijevog djeteta (X). Za ovu situaciju potrebna je kombinacija rotacijskih operacija.

U ovom slučaju prvo okrećemo Y udesno, pa stablo dobiva isti oblik kao i prethodni slučaj. Tada možemo uravnotežiti stablo lijevom rotacijom Z.

Također, kada je faktor ravnoteže čvora Z -2, njegovo podstablo je u jednom od ova dva stanja, pa Z smatramo korijenom, a Y lijevim djetetom.

Visina u lijevom djetetu Y veća je od visine njegova desnog djeteta, pa drvo uravnotežujemo desnom rotacijom Z.

Ili u drugom slučaju, desno dijete Y ima veću visinu od svog lijevog djeteta.

Dakle, prije svega, transformiramo ga u prijašnji oblik lijevom rotacijom Y, a zatim uravnotežimo stablo desnom rotacijom Z.

Pogledajmo operaciju rebalansa za naše AVLTree:

Rebalans čvora (čvor z) {updateHeight (z); int ravnoteža = getBalance (z); if (ravnoteža> 1) {if (visina (z.desno.desno)> visina (z.desno.lijevo)) {z = rotateLeft (z); } else {z.desno = rotateRight (z.desno); z = rotateLeft (z); }} inače if (visina ravnoteže (z.lijevo.desno)) z = rotateRight (z); else {z.left = rotateLeft (z.left); z = rotateRight (z); }} povratak z; }

Koristit ćemo rebalans nakon umetanja ili brisanja čvora za sve čvorove na putu od promijenjenog čvora do korijena.

4. Umetnite čvor

Kad ćemo umetnuti ključ u stablo, moramo pronaći njegov pravilan položaj da bismo prošli BST pravila. Dakle, krećemo od korijena i njegovu vrijednost uspoređujemo s novim ključem. Ako je ključ veći, nastavljamo desno - u suprotnom idemo lijevom djetetu.

Jednom kad pronađemo odgovarajući nadređeni čvor, tada dodajemo novi ključ kao čvor lijevo ili desno, ovisno o vrijednosti.

Nakon umetanja čvora imamo BST, ali to možda nije AVL stablo. Stoga provjeravamo čimbenike ravnoteže i ponovno uravnotežujemo BST za sve čvorove na putu od novog čvora do korijena.

Pogledajmo operaciju umetanja:

Umetanje čvora (čvor čvora, int ključ) {if (node ​​== null) {return new Node (key); } else if (node.key> ključ) {node.left = insert (node.left, key); } else if (node.key <key) {node.right = insert (node.right, key); } else {baciti novi RuntimeException ("duplicirani ključ!"); } povratak rebalansa (čvor); }

Važno je zapamtiti da je ključ jedinstven u stablu - niti dva čvora ne dijele isti ključ.

Složenost vremena algoritma za umetanje ovisi o visini. Budući da je naše stablo uravnoteženo, možemo pretpostaviti da je vremenska složenost u najgorem slučaju O (log (N)).

5. Izbrišite čvor

Da bismo izbrisali ključ sa stabla, prvo ga moramo pronaći u BST-u.

Nakon što pronađemo čvor (nazvan Z), moramo predstaviti novog kandidata koji će biti njegova zamjena u stablu. Ako je Z list, kandidat je prazan. Ako Z ima samo jedno dijete, ovo je dijete kandidat, ali ako Z ima dvoje djece, postupak je malo složeniji.

Pretpostavimo desno podređeno dijete Z koje se zove Y. Prvo, pronalazimo krajnji lijevi čvor Y i nazivamo ga X. Zatim postavljamo novu vrijednost Z jednaku vrijednosti X ’s i nastavljamo brisati X iz Y.

Napokon, metodu rebalansa pozivamo na kraju da BST ostane AVL stablo.

Evo naše metode brisanja:

Izbriši čvor (čvor čvora, int ključ) {if (node ​​== null) {return čvor; } else if (node.key> ključ) {node.left = delete (node.left, key); } else if (node.key <key) {node.right = delete (node.right, key); } else {if (node.left == null || node.right == null) {node = (node.left == null)? node.desno: node.left; } else {Čvor mostLeftChild = mostLeftChild (node.right); node.key = mostLeftChild.key; node.right = izbriši (node.right, node.key); }} if (čvor! = null) {node = rebalans (čvor); } povratni čvor; }

Složenost vremena algoritma za brisanje ovisi o visini stabla. Slično metodi umetanja, možemo pretpostaviti da je vremenska složenost u najgorem slučaju O (log (N)).

6. Potražite čvor

Traženje čvora u AVL stablu je isto kao i kod bilo kojeg BST-a.

Počnite od korijena stabla i usporedite ključ s vrijednošću čvora. Ako je ključ jednak vrijednosti, vratite čvor. Ako je ključ veći, tražite od desnog djeteta, u suprotnom nastavite s lijevim djetetom.

Vremenska složenost pretraživanja ovisi o visini. Možemo pretpostaviti da je vremenska složenost u najgorem slučaju O (log (N)).

Pogledajmo uzorak koda:

Pronaći čvor (tipka int) {Čvor čvora = korijen; while (current! = null) {if (current.key == key) {break; } current = current.key <tipka? current.right: current.left; } povratna struja; }

7. Zaključak

U ovom uputstvu implementirali smo AVL stablo s operacijama umetanja, brisanja i pretraživanja.

Kao i uvijek, kod možete pronaći na Githubu.