Kako utvrditi je li binarno stablo uravnoteženo u Javi

1. Pregled

Drveće je jedna od najvažnijih struktura podataka u računalnoj znanosti. Obično nas zanima uravnoteženo drvo zbog njegovih vrijednih svojstava. Njihova struktura omogućuje izvođenje operacija poput upita, umetanja, brisanja u logaritamskom vremenu.

U ovom uputstvu naučit ćemo kako odrediti je li binarno stablo uravnoteženo.

2. Definicije

Prvo, predstavimo nekoliko definicija kako bismo bili sigurni da smo na istoj stranici:

  • Binarno stablo - vrsta stabla u kojem svaki čvor ima nula, jedno ili dvoje djece
  • Visina stabla - maksimalna udaljenost od korijena do lista (ista kao i dubina najdubljeg lista)
  • Uravnoteženo drvo - vrsta drveta gdje za svako podstablo maksimalna udaljenost od korijena do bilo kojeg lista je najviše jedna za najmanju udaljenost od korijena do bilo kojeg lista

Primjer uravnoteženog binarnog stabla možemo pronaći u nastavku. Tri zelena ruba jednostavna su vizualizacija kako odrediti visinu, dok brojevi označavaju razinu.

3. Objekti domene

Pa, krenimo s klasom za naše stablo:

drvo javne klase {private int vrijednost; privatno Drvo lijevo; privatno Drvo desno; javno stablo (int vrijednost, stablo lijevo, stablo desno) {this.value = value; this.left = lijevo; this.right = desno; }} 

Radi jednostavnosti, recimo svaki čvor ima cijelu vrijednost. Imajte na umu, to ako su lijevo i desno drveće null, onda to znači da je naš čvor list.

Prije nego što predstavimo našu primarnu metodu, pogledajmo što bi trebala vratiti:

rezultat privatne klase {private boolean isBalanced; visina privatnog int; privatni rezultat (logička isBalanced, int visina) {this.isBalanced = isBalanced; this.height = visina; }}

Tako ćemo za svaki pojedini poziv imati informacije o visini i ravnoteži.

4. Algoritam

Imajući definiciju uravnoteženog stabla, možemo smisliti algoritam. Ono što trebamo učiniti je provjeriti željeno svojstvo za svaki čvor. To se lako može postići rekurzivnim pretraživanjem dubinskog pretraživanja.

Sada će se pozivati ​​naša rekurzivna metoda za svaki čvor. Uz to će pratiti trenutnu dubinu. Svaki poziv vraća podatke o visini i ravnoteži.

Pogledajmo sada našu metodu koja se temelji na dubini:

privatni rezultat jeBalancedRecursive (stablo stabla, dubina int) {if (stablo == null) {return new Result (true, -1); } Rezultat leftSubtreeResult = isBalancedRecursive (tree.left (), dubina + 1); Rezultat rightSubtreeResult = isBalancedRecursive (tree.right (), dubina + 1); boolean isBalanced = Math.abs (leftSubtreeResult.height - rightSubtreeResult.height) <= 1; boolean subtreesAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced; int visina = Math.max (leftSubtreeResult.height, rightSubtreeResult.height) + 1; vrati novi rezultat (isBalanced && subtreesAreBalanced, visina); }

Prvo, moramo razmotriti slučaj ako je naš čvor null: vratit ćemo se pravi (što znači da je stablo uravnoteženo) i -1 kao visina.

Zatim, upućujemo dva rekurzivna poziva za lijevo i desno podstablo, održavajući dubinu ažurnom.

U ovom trenutku imamo izvedene izračune za djecu trenutnog čvora. Sad imamo sve potrebne podatke za provjeru stanja:

  • the jeUravnoteženo varijabla provjerava visinu za djecu, i
  • substreesAreBalanced pokazuje jesu li i podstabla uravnotežena

Napokon, možemo vratiti podatke o ravnoteži i visini. Također bi mogla biti dobra ideja pojednostaviti prvi rekurzivni poziv fasadnom metodom:

javna boolean isBalanced (stablo stabla) {return isBalancedRecursive (stablo, -1) .isBalanced; }

5. Sažetak

U ovom smo članku razgovarali o tome kako odrediti je li binarno stablo uravnoteženo. Objasnili smo pristup pretraživanju dubinski.

Kao i obično, izvorni kod s testovima dostupan je na GitHubu.