streamalism.org

1. Áttekintés

A fák a számítástechnika egyik legfontosabb adatstruktúrája. Értékes tulajdonságai miatt általában egy kiegyensúlyozott fa érdekel minket. Szerkezetük lehetővé teszi olyan műveletek végrehajtását, mint például lekérdezések, beillesztések, törlések a logaritmikus időben.

Ebben az oktatóanyagban megtanuljuk, hogyan lehet meghatározni, hogy a bináris fa kiegyensúlyozott-e.

2. Definíciók

Először mutassunk be néhány meghatározást, hogy megbizonyosodjunk arról, hogy ugyanazon az oldalon vagyunk:

• Egy bináris fa - egyfajta fa, ahol minden csomópontnak nulla, egy vagy két gyermeke van
• Egy fa magassága - a gyökér és a levél közötti maximális távolság (megegyezik a legmélyebb levél mélységével)
• Kiegyensúlyozott fa - egyfajta fa, ahol minden alfa esetében a gyökér és a levél közötti maximális távolság legfeljebb eggyel nagyobb, mint a gyökér és bármely levél közötti minimális távolság

A kiegyensúlyozott bináris fára alább találunk példát. Három zöld szél egy egyszerű megjelenítés a magasság meghatározásának módjáról, míg a számok jelzik a szintet.

3. Domain objektumok

Tehát kezdjük a fánk osztályával:

public class Tree {private int value; magánfa maradt; magánfa jobb; public Tree (int érték, Fa bal, Fa jobb) {this.érték = érték; ez.balra = balra; ez.jobb = jobb; }} 

Mondjuk az egyszerűség kedvéért minden csomópontnak egész értéke van. Vegye figyelembe, hogy ha bal és jobb fák vannak nulla, akkor ez azt jelenti, hogy csomópontunk levél.

Mielőtt bemutatnánk az elsődleges módszerünket, nézzük meg, mit kell hoznia:

privát osztály Eredmény {private boolean isBalanced; privát int magasság; privát Eredmény (logikai isBalanced, int magasság) {this.isBalanced = isBalanced; ez.magasság = magasság; }}

Így minden egyes hívásnál rendelkezünk információkkal a magasságról és az egyensúlyról.

4. Algoritmus

A kiegyensúlyozott fa definíciójával előállhatunk egy algoritmussal. Amit tennünk kell, hogy ellenőrizzük a csomópontok kívánt tulajdonságát. Rekurzív mélység-első keresési bejárással könnyen elérhető.

Most a rekurzív módszerünket minden csomópontra meghívjuk. Ezenkívül nyomon követi az aktuális mélységet. Minden hívás információt ad a magasságról és az egyensúlyról.

Most vessünk egy pillantást a legelső mélységű módszerünkre:

privát Eredmény isBalancedRecursive (Fafa, int mélység) {if (fa == null) {return new Result (true, -1); } Eredmény leftSubtreeResult = isBalancedRecursive (fa.balra (), mélység + 1); Eredmény rightSubtreeResult = isBalancedRecursive (fa.jobb (), mélység + 1); logikai isBalanced = Math.abs (leftSubtreeResult.height - rightSubtreeResult.height) <= 1; logikai részfákAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced; int magasság = Math.max (leftSubtreeResult.height, rightSubtreeResult.height) + 1; return new Result (isBalanced && subtreesAreBalanced, magasság); }

Először meg kell vizsgálnunk az esetet, ha a csomópontunk az nulla: visszatérünk igaz (ami azt jelenti, hogy a fa kiegyensúlyozott) és -1 mint magasság.

Azután, két rekurzív hívást kezdeményezünk a bal és a jobb alfára, a mélység naprakészen tartásával.

Ezen a ponton elvégezzük az aktuális csomópont gyermekeinek számítását. Most már rendelkezünk az összes szükséges adattal az egyenleg ellenőrzéséhez:

• a kiegyensúlyozott változó ellenőrzi a gyermekek magasságát, és
• subreesAreBalanced azt jelzi, hogy az alfák kiegyensúlyozottak-e

Végül visszaadhatunk információt az egyensúlyról és a magasságról. Jó ötlet lehet az első rekurzív hívás homlokzati módszerrel történő egyszerűsítése:

public boolean isBalanced (Fafa) {return isBalancedRecursive (fa, -1) .isBalanced; }

5. Összefoglalás

Ebben a cikkben megvitattuk, hogyan lehet meghatározni, hogy a bináris fa kiegyensúlyozott-e. Megmagyaráztuk a mélységig első keresési megközelítést.

Szokás szerint a tesztekkel ellátott forráskód elérhető a GitHubon.