streamalism.org

1. Oversikt

Trær er en av de viktigste datastrukturene innen informatikk. Vi er vanligvis interessert i et balansert tre på grunn av dets verdifulle egenskaper. Strukturen deres gjør det mulig å utføre operasjoner som spørsmål, innsettinger, slettinger i logaritmisk tid.

I denne opplæringen skal vi lære å bestemme om et binært tre er balansert.

2. Definisjoner

La oss først introdusere noen definisjoner for å sikre at vi er på samme side:

• Et binært tre - et slags tre der hver node har null, ett eller to barn
• En høyde på et tre - en maksimal avstand fra en rot til et blad (samme som dybden på det dypeste bladet)
• Et balansert tre - et slags tre hvor for hvert undertre er den maksimale avstanden fra roten til et hvilket som helst blad høyst større enn ett enn minimumsavstanden fra roten til hvilket som helst blad

Vi kan finne et eksempel på et balansert binært tre nedenfor. Tre grønne kanter er en enkel visualisering av hvordan du skal bestemme høyden, mens tallene indikerer nivået.

3. Domeneobjekter

Så la oss starte med en klasse for treet vårt:

public class Tree {private int value; private Tree igjen; private Tree høyre; public Tree (int verdi, Tree venstre, Tree høyre) {this.value = verdi; denne. venstre = venstre; this.right = right; }} 

La oss si for enkelhets skyld hver node har et heltall. Noter det hvis venstre og høyre trær er null, da betyr det at noden vår er et blad.

Før vi introduserer vår primære metode, la oss se hva den skal returnere:

privat klasse Resultat {privat boolsk isBalanced; privat int høyde; privat resultat (boolsk isBalanced, int høyde) {this.isBalanced = isBalanced; dette. høyde = høyde; }}

Dermed vil vi ha informasjon om høyde og balanse for hver eneste samtale.

4. Algoritme

Å ha en definisjon av et balansert tre, kan vi komme opp med en algoritme. Det vi trenger å gjøre er å sjekke ønsket eiendom for hver node. Det kan enkelt oppnås med rekursiv dybde-første søkeprosess.

Nå vil vår rekursive metode bli påkalt for hver node. I tillegg vil den holde oversikt over gjeldende dybde. Hver samtale vil gi informasjon om høyde og balanse.

La oss ta en titt på vår dybde-første metode:

privat resultat erBalancedRecursive (Tree tree, int depth) {if (tree == null) {returner nytt resultat (true, -1); } Resultat leftSubtreeResult = isBalancedRecursive (tree.left (), dybde + 1); Resultat rightSubtreeResult = isBalancedRecursive (tree.right (), dybde + 1); boolsk isBalanced = Math.abs (leftSubtreeResult.height - rightSubtreeResult.height) <= 1; boolske subtreesAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced; int høyde = Math.max (leftSubtreeResult.height, rightSubtreeResult.height) + 1; returner nytt resultat (isBalanced && subtreesAreBalanced, height); }

Først må vi vurdere saken hvis noden vår er det null: vi kommer tilbake ekte (som betyr at treet er balansert) og -1 som en høyde.

Deretter, vi foretar to rekursive samtaler for venstre og høyre undertre, og holder dybden oppdatert.

På dette punktet har vi utført beregninger for barn av en nåværende node. Nå har vi alle nødvendige data for å sjekke saldoen:

• de er balansert variabel sjekker høyden for barn, og
• substreesAreBalanced indikerer om undertrærne begge er balanserte også

Til slutt kan vi returnere informasjon om balanse og høyde. Det kan også være lurt å forenkle den første rekursive samtalen med en fasademetode:

public boolean isBalanced (Tree tree) {return isBalancedRecursive (tree, -1) .isBalanced; }

5. Sammendrag

I denne artikkelen har vi diskutert hvordan vi kan avgjøre om et binært tre er balansert. Vi har forklart en dybde-første søkemetode.

Som vanlig er kildekoden med tester tilgjengelig på GitHub.