streamalism.org

1. Oversigt

Træer er en af ​​de vigtigste datastrukturer inden for datalogi. Vi er normalt interesserede i et afbalanceret træ på grund af dets værdifulde egenskaber. Deres struktur tillader udførelse af operationer som forespørgsler, indsættelser, sletninger på logaritmisk tid.

I denne vejledning vil vi lære at bestemme, om et binært træ er afbalanceret.

2. Definitioner

Lad os først introducere et par definitioner for at sikre, at vi er på samme side:

• Et binært træ - en slags træ, hvor hver knude har nul, et eller to børn
• En træhøjde - en maksimal afstand fra en rod til et blad (samme som dybden af ​​det dybeste blad)
• Et afbalanceret træ - en slags træ hvor for hvert undertræ er den maksimale afstand fra roden til ethvert blad højst en større end den mindste afstand fra roden til et hvilket som helst blad

Vi kan finde et eksempel på et afbalanceret binært træ nedenfor. Tre grønne kanter er en simpel visualisering af, hvordan man bestemmer højden, mens tallene angiver niveauet.

3. Domæneobjekter

Så lad os starte med en klasse for vores træ:

public class Tree {private int værdi; privat træ tilbage; privat træ til højre; public Tree (int værdi, Tree venstre, Tree højre) {this.value = værdi; this.left = venstre; this.right = højre; }} 

Lad os sige for enkelhedens skyld hver knude har et heltal. Noter det hvis venstre og højre træ er nul, så betyder det, at vores knude er et blad.

Før vi introducerer vores primære metode, skal vi se, hvad den skal returnere:

privat klasse Resultat {privat boolsk isBalanced; privat int højde; privat resultat (boolsk isBalanced, int-højde) {this.isBalanced = isBalanced; denne. højde = højde; }}

Således får vi oplysninger om højde og balance for hvert enkelt opkald.

4. Algoritme

Når vi har en definition af et afbalanceret træ, kan vi komme med en algoritme. Hvad vi skal gøre er at kontrollere den ønskede egenskab for hver node. Det kan nemt opnås med rekursiv dybde-første søgning.

Nu vil vores rekursive metode blive påberåbt for hver node. Derudover holder den styr på den aktuelle dybde. Hvert opkald returnerer oplysninger om højde og balance.

Lad os nu se på vores dybde-første metode:

privat resultat isBalancedRecursive (Tree tree, int depth) {if (tree == null) {returner nyt 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; booleske subtreesAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced; int højde = Math.max (leftSubtreeResult.height, rightSubtreeResult.height) + 1; returner nyt resultat (isBalanced && subtreesAreBalanced, height); }

Først skal vi overveje sagen, hvis vores node er nul: vi vil vende tilbage rigtigt (hvilket betyder, at træet er afbalanceret) og -1 som en højde.

Derefter, vi foretager to rekursive opkald til venstre og højre undertræ og holder dybden opdateret.

På dette tidspunkt har vi udført beregninger for børn af en nuværende node. Nu har vi alle de nødvendige data til at kontrollere saldoen:

• det erBalanceret variabel kontrollerer højden for børn, og
• substreesAreBalanced angiver, om undertrærne også er afbalancerede

Endelig kan vi returnere oplysninger om balance og højde. Det kan også være en god ide at forenkle det første rekursive opkald med en facademetode:

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

5. Resume

I denne artikel har vi diskuteret, hvordan man kan bestemme, om et binært træ er afbalanceret. Vi har forklaret en dybde-første søgning tilgang.

Som normalt er kildekoden med test tilgængelig på GitHub.