Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
Perfektný binárny strom (tiež nazývaný kompletný binárny strom v tom zmysle, že všetky úrovne sú plné) vykazuje nasledujúce vlastnosti:
1. Všetky vnútorné uzly majú presne dve deti: Každý uzol, ktorý nie je listovým uzlom, musí mať ľavé dieťa a pravé dieťa.
2. Všetky listové uzly sú na rovnakej úrovni: Hĺbka všetkých listových uzlov (uzly bez detí) je rovnaká. To znamená, že strom je dokonale vyvážený.
3. Počet uzlov na úrovni `i` je` 2^i`: Kde sa úroveň koreňov považuje za úroveň 0.
4. Celkový počet uzlov v perfektnom binárnom strome výšky `H` je` 2^(H+1) - 1` .
5. . Toto sa často aproximuje ako `log2 (n)`.
implikácie týchto charakteristík:
* Perfektný binárny strom je vo svojej podstate vyvážený.
* Jeho štruktúra je vysoko predvídateľná a pravidelná.
* Je to vysoko efektívny priestor, s minimálnou premrhanou pamäťou v dôsledku neobvyklých uzlov.
Tu je návod, ako by ste mohli implementovať dokonalý binárny strom v Jave so zameraním na základnú štruktúru a kľúčové operácie:
`` `Java
trieda PerfectBinarytree {
uzol statickej triedy {
údaje int;
Uzol vľavo;
Uzol vpravo;
Uzol (int data) {
this.data =data;
this.left =null;
this.right =null;
}
}
Koreň uzlov;
výška int; // Výška stromu (počet úrovní - 1)
public PerfectBinarytree (int výška) {
this.height =výška;
this.Root =ConstructPerFectBinarytree (0, výška);
}
súkromný uzol konštruktPerfectBinaryTree (int currentLevel, int maxheight) {
if (currentLevel> maxHeight) {
návrat null;
}
// Vytvorte uzol
Uzol uzol =nový uzol ((int) Math.pow (2, CurrentLevel)); // Príklad:Použite úroveň 2^ako hodnota uzla
// rekurzívne vytvorte doľava a pravé podstromky
node.left =constructPerFectBinarytree (currentLevel + 1, maxheight);
Node.right =ConstructPerFectBinaryTree (CurrentLevel + 1, MaxHeight);
návratový uzol;
}
// Príklad:INODER TRASSALE na overenie štruktúry
public void inOrderTaversal (uzol uzol) {
if (uzol! =null) {
inOrdertraversal (uzol.left);
System.out.print (node.data + "");
inOrderTRaversal (uzol.right);
}
}
public static void main (String [] args) {
výška int =2; // 3 úrovne (koreň + 2 viac)
PerfectBinarytree PerfectTree =new PerfectBinarytree (výška);
System.out.println ("INDORD TRAVERSAL:");
PerfectTree.inorderTRaversal (PerfectTree.Root); // Výstup:4 2 5 1 6 3 7
}
}
`` `
Vysvetlenie:
1. `Node` trieda:
* Predstavuje uzol v binárnom strome.
* Obsahuje `Data` (celé číslo v tomto príklade),„ ľavá “a„ pravé “ukazovatele.
2.
* `Root`:Koreňový uzol stromu.
* `Výška:Výška stromu. Koreň je úroveň 0, takže strom výšky `H` má úrovne` H+1`.
* `PerfectBinarytree (int výška)`:Konštruktor. Ako vstup si vyžaduje požadovanú „výšku“ perfektného binárneho stromu. Je dôležité, že volá „ConstructPerFectBinaryTree ()` na rekurzívne budovanie stromovej štruktúry.
3.
* Toto je rekurzívna pomocná funkcia, ktorá vytvára strom.
* `CurrentLevel`:Aktuálna úroveň, ktorá sa vytvára (od 0 pre koreň).
* `Maxheight`:Maximálna výška stromu.
* Základný prípad: `currentLevel> maxheight`:Ak` currentLevel` presahuje `maxheight`, znamená to, že sme sa dostali za uzly listov, takže sa vraciame` null`.
* RECULSIVE KROK:
* Vytvorí nový „uzol“. Hodnota `Data` je nastavená (v tomto príklade) na` 2^CurrentLevel`, aby sa demonštrovala štruktúra založená na úrovni, ale to môže byť akákoľvek logika pre inicializáciu údajov uzla.
* Rekurzívne volá `ConstructperFectBinaryTree ()` na zostavenie ľavých a pravých podstromov, čím sa v každom volaní zvyšuje „CurrentLevel`.
* Pripojí novovytvorené podstroje k aktuálnemu uzlu (`node.left` a` node.right`).
* Vráti novovytvorený uzol.
4.
* Štandard na tlačenie prvkov stromu. Je to len na demonštráciu a overovanie.
* Vľavo -> root -> vpravo
5.
* Demonštruje, ako vytvoriť objekt PerfectBinaryTree` so zadanou výškou.
* Volá `inOrderTaversal` na vytlačenie stromu.
Dôležité úvahy:
* konštrukcia: Kľúčom k vytvoreniu dokonalého binárneho stromu je rekurzívny výstavný prístup. Zaisťuje, že všetky úrovne sú úplne vyplnené pred presunom na ďalšiu.
* Inicializácia údajov: Príklad používa `Math.pow (2, CurrentLevel)` na inicializáciu dát uzla, ale môžete to prispôsobiť tak, aby vyplnil strom s akýmikoľvek požadovanými údajmi. Základnou časťou je vyplnenie všetkých uzlov na každej úrovni.
* Imubilita (voliteľné): Ak chcete, aby bol strom po vytvorení nemenný, vytvorte `node`` data`, `ľavú 'a` right' polia `final` a neposkytujte žiadne metódy na zmenu štruktúry stromu po jeho vytvorení.
* Žiadne vkladanie/delécia (zvyčajne): Pretože dokonalé binárne stromy sú vo svojej podstate vyvážené, priame vkladanie alebo vymazanie uzlov * pri zachovaní perfektnej štruktúry * je ťažké a často nepraktické. Ak potrebujete vložiť/odstrániť, po každej operácii by ste zvyčajne potrebovali úplne rekonštruovať strom. Perfektné binárne stromy sa najčastejšie používajú, keď je súbor údajov vopred známy a zostáva statický.
* reprezentácia poľa: Kvôli svojej pravidelnej štruktúre môžu byť dokonalé binárne stromy efektívne reprezentované pomocou polí (najmä ak nemusíte vložiť/vymazať prvky). Koreň je v indexe 0. Ľavé dieťa uzla v indexe `I's je na` 2i + 1` a pravé dieťa je na `2i + 2`. Tým sa zabráni potrebe explicitných „uzlov“ objektov a ukazovateľov, ktoré ukladajú priestor.
Príklad:Zastúpenie poľa dokonalého binárneho stromu
Perfektný binárny strom je možné uložiť veľmi efektívne v poli. Zvážte strom s výškou 2:
`` `
1
/ \
2 3
/ \ / \
4 5 6 7
`` `
Zastúpenie poľa by bolo:
`` `
[1, 2, 3, 4, 5, 6, 7]
`` `
Vzťahy medzi rodičmi a deťmi sú implicitné v indexoch poľa:
* Parent uzla v indexe `i` je v indexe` (i-1)/2` (celé číslo delenie)
* Ľavé dieťa uzla v indexe `I's je v indexe` 2i + 1`
* Pravé dieťa uzla v indexe `I's je v indexe` 2i + 2`
Táto reprezentácia poľa je neuveriteľne priestorovo efektívne pre dokonalé binárne stromy, pretože v poli nie sú medzery.
Kedy používať dokonalé binárne stromy:
* Keď sú údaje známe vopred a zostávajú statické.
* Ak potrebujete zaručenú vyváženú štruktúru stromov.
* Keď uprednostňujete rýchly prístup k uzlom na základe ich polohy v strome.
* Dátové štruktúry haldy (Min-Haps, Max-Heaps) sa bežne implementujú pomocou poľa reprezentácie * takmer kompletného * binárneho stromu, ktorý súvisí s dokonalým binárnym stromom.
Perfektné binárne stromy sú cenné pre konkrétne prípady použitia, keď ich tuhá štruktúra a predvídateľný výkon poskytujú výhody. Avšak pre dynamické scenáre, v ktorých často potrebujete vložiť alebo vymazať uzly, sú vo všeobecnosti vhodnejšie ďalšie vyvážené stromové štruktúry, ako sú stromy AVL alebo červeno-čierne stromy.