streamalism.org

1. Overzicht

Bomen zijn een van de belangrijkste datastructuren in de informatica. Vanwege zijn waardevolle eigenschappen zijn we meestal geïnteresseerd in een uitgebalanceerde boom. Hun structuur maakt het mogelijk om bewerkingen uit te voeren zoals query's, invoegingen en verwijderingen in logaritmische tijd.

In deze tutorial gaan we leren hoe we kunnen bepalen of een binaire boom in evenwicht is.

2. Definities

Laten we eerst een paar definities introduceren om ervoor te zorgen dat we op dezelfde pagina zijn:

• Een binaire boom - een soort boom waar elk knooppunt nul, een of twee kinderen heeft
• Een hoogte van een boom - een maximale afstand van een wortel tot een blad (hetzelfde als de diepte van het diepste blad)
• Een evenwichtige boom - een soort boom waar voor elke subboom is de maximale afstand van de wortel tot elk blad maximaal één groter dan de minimale afstand van de wortel tot een willekeurig blad

We kunnen hieronder een voorbeeld van een gebalanceerde binaire boom vinden. Drie groene randen zijn een eenvoudige visualisatie van hoe je de hoogte bepaalt, terwijl de cijfers het niveau aangeven.

3. Domeinobjecten

Dus laten we beginnen met een les voor onze stamboom:

public class Tree {private int waarde; privé Tree links; privé Tree rechts; openbare boom (int waarde, boom links, boom rechts) {this.value = waarde; this.left = left; this.right = right; }} 

Laten we voor de eenvoud zeggen elk knooppunt heeft een geheel getal. Let daar op als links en rechts bomen zijn nul, dan betekent het dat ons knooppunt een blad is.

Voordat we onze primaire methode introduceren, laten we eens kijken wat deze zou moeten retourneren:

private class Resultaat {private boolean isBalanced; privé int hoogte; privé resultaat (boolean isBalanced, int hoogte) {this.isBalanced = isBalanced; this.height = hoogte; }}

Dus voor elke oproep hebben we informatie over lengte en balans.

4. Algoritme

Als we een definitie hebben van een gebalanceerde boom, kunnen we een algoritme bedenken. Wat we moeten doen, is de gewenste eigenschap voor elk knooppunt controleren. Het kan eenvoudig worden bereikt met recursieve diepte-eerst zoekdoorloop.

Nu wordt onze recursieve methode aangeroepen voor elk knooppunt. Bovendien houdt het de huidige diepte bij. Elke oproep geeft informatie over lengte en balans.

Laten we nu eens kijken naar onze diepte-eerst-methode:

private Resultaat isBalancedRecursive (Tree tree, int depth) {if (tree == null) {return new Result (true, -1); } Resultaat leftSubtreeResult = isBalancedRecursive (tree.left (), depth + 1); Resultaat rightSubtreeResult = isBalancedRecursive (tree.right (), depth + 1); boolean isBalanced = Math.abs (leftSubtreeResult.height - rightSubtreeResult.height) <= 1; booleaanse substructurenAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced; int hoogte = Math.max (leftSubtreeResult.height, rightSubtreeResult.height) + 1; retourneer nieuw resultaat (isBalanced && subtreesAreBalanced, hoogte); }

Ten eerste moeten we het geval overwegen als ons knooppunt is nul: we komen terug waar (wat betekent dat de boom in balans is) en -1 als een hoogte.

Dan, we doen twee recursieve aanroepen voor de linker en rechter substructuur, waarbij we de diepte up-to-date houden.

Op dit punt hebben we berekeningen uitgevoerd voor kinderen van een huidig ​​knooppunt. Nu hebben we alle benodigde gegevens om het saldo te controleren:

• de isBalanced variabele controleert de hoogte voor kinderen, en
• substreesAreBalanced geeft aan of de substructuren beide ook gebalanceerd zijn

Ten slotte kunnen we informatie over balans en hoogte retourneren. Het kan ook een goed idee zijn om de eerste recursieve aanroep te vereenvoudigen met een gevelmethode:

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

5. Samenvatting

In dit artikel hebben we besproken hoe u kunt bepalen of een binaire boom in evenwicht is. We hebben een eerste zoekaanpak uitgelegd.

Zoals gewoonlijk is de broncode met tests beschikbaar op GitHub.