Ako zistiť, či je binárny strom vyvážený v prostredí Java

1. Prehľad

Stromy sú jednou z najdôležitejších dátových štruktúr v informatike. Zvyčajne nás zaujíma vyvážený strom kvôli jeho cenným vlastnostiam. Ich štruktúra umožňuje vykonávať operácie ako dotazy, vkladanie a mazanie v logaritmickom čase.

V tomto výučbe sa naučíme, ako zistiť, či je binárny strom vyvážený.

2. Definície

Najprv si predstavíme niekoľko definícií, aby sme sa uistili, že sme na rovnakej stránke:

  • Binárny strom - druh stromu, kde každý uzol má nulu, jedno alebo dve deti
  • Výška stromu - maximálna vzdialenosť od koreňa po list (rovnaká ako hĺbka najhlbšieho listu)
  • Vyvážený strom - akýsi strom, kde pre každý podstrom je maximálna vzdialenosť od koreňa po akýkoľvek list nanajvýš väčšia ako minimálna vzdialenosť od koreňa k ľubovoľnému listu

Nižšie nájdeme príklad vyváženého binárneho stromu. Tri zelené okraje sú jednoduchou vizualizáciou spôsobu určovania výšky, zatiaľ čo čísla označujú úroveň.

3. Doménové objekty

Začnime teda s triedou pre náš strom:

public class Tree {private int value; súkromný Strom vľavo; súkromné ​​právo na strom; verejný strom (int hodnota, strom vľavo, strom vpravo) {this.value = hodnota; this.left = left; this.right = right; }} 

Z dôvodu jednoduchosti povedzme každý uzol má celočíselnú hodnotu. Poznač si to ak sú ľavé a pravé stromy nulový, potom to znamená, že náš uzol je list.

Predtým, ako predstavíme našu primárnu metódu, pozrime sa, čo by mala vrátiť:

súkromná trieda Výsledok {private boolean isBalanced; výška súkromného int; private Result (boolean isBalanced, int height) {this.isBalanced = isBalanced; this.height = výška; }}

Pri každom jednom hovore teda budeme mať informácie o výške a vyvážení.

4. Algoritmus

Keď máme definíciu vyváženého stromu, môžeme prísť s algoritmom. Musíme skontrolovať požadovanú vlastnosť pre každý uzol. Dá sa to ľahko dosiahnuť rekurzívnym priechodom hĺbkového prieskumu.

Teraz bude naša rekurzívna metóda vyvolaná pre každý uzol. Ďalej bude sledovať aktuálnu hĺbku. Každý hovor vráti informácie o výške a vyvážení.

Poďme sa teraz pozrieť na našu metódu hĺbkovej kontroly:

private Result isBalancedRecursive (Tree tree, int depth) {if (tree == null) {return new Result (true, -1); } Výsledok leftSubtreeResult = isBalancedRecursive (tree.left (), depth + 1); Výsledok rightSubtreeResult = isBalancedRecursive (tree.right (), depth + 1); boolean isBalanced = Math.abs (leftSubtreeResult.height - pravýSubtreeResult.height) <= 1; boolovské podstromyAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced; int výška = Math.max (leftSubtreeResult.height, rightSubtreeResult.height) + 1; vrátiť nový výsledok (isBalanced && podstromyAreBalanced, výška); }

Najprv musíme zvážiť prípad, ak je náš uzol nulový: vrátime sa pravda (čo znamená, že strom je vyvážený) a -1 ako výška.

Potom, uskutočňujeme dve rekurzívne volania pre ľavý a pravý podstrom, čím udržujeme aktuálnu hĺbku.

V tomto okamihu máme vykonané výpočty pre deti aktuálneho uzla. Teraz máme všetky potrebné údaje na kontrolu zostatku:

  • the je vyvážený premenná kontroluje výšku detí a
  • podkladyAreBalanced označuje, či sú podstromy tiež vyvážené

Na záver môžeme vrátiť informácie o rovnováhe a výške. Môže byť tiež dobrý nápad zjednodušiť prvé rekurzívne volanie metódou fasády:

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

5. Zhrnutie

V tomto článku sme diskutovali o tom, ako zistiť, či je binárny strom vyvážený. Vysvetlili sme prístup pri hľadaní do hĺbky.

Zdrojový kód s testami je ako obvykle k dispozícii na serveri GitHub.