Vyvážený binárny strom je známy aj ako výškovo vyvážený strom. Je definovaný ako binárny strom, keď rozdiel medzi výškou ľavého podstromu a pravého podstromu nie je väčší ako m, kde m sa zvyčajne rovná 1. Výška stromu je počet hrán na najdlhšej ceste medzi koreňový uzol a listový uzol.
Vyššie uvedený strom je a binárny vyhľadávací strom . Binárny vyhľadávací strom je strom, v ktorom má každý uzol na ľavej strane nižšiu hodnotu ako jeho rodičovský uzol a uzol na pravej strane má vyššiu hodnotu ako jeho nadradený uzol. Vo vyššie uvedenom strome je n1 koreňový uzol a n4, n6, n7 sú listové uzly. Uzol n7 je najvzdialenejší uzol od koreňového uzla. n4 a n6 obsahujú 2 hrany a medzi koreňovým uzlom a n7 existujú tri hrany. Keďže n7 je najďalej od koreňového uzla; preto je výška vyššie uvedeného stromu 3.
kolekcie java
Teraz uvidíme, či je vyššie uvedený strom vyvážený alebo nie. Ľavý podstrom obsahuje uzly n2, n4, n5 a n7, zatiaľ čo pravý podstrom obsahuje uzly n3 a n6. Ľavý podstrom má dva listové uzly, t.j. n4 a n7. Medzi uzlom n2 a n4 je len jedna hrana a medzi uzlami n7 a n2 dve hrany; preto je uzol n7 najďalej od koreňového uzla. Výška ľavého podstromu je 2. Pravý podstrom obsahuje iba jeden listový uzol, t. j. n6, a má len jednu hranu; teda výška pravého podstromu je 1. Rozdiel medzi výškami ľavého podstromu a pravého podstromu je 1. Keďže sme dostali hodnotu 1, môžeme povedať, že vyššie uvedený strom je výškovo vyvážený strom. Tento proces výpočtu rozdielu medzi výškami by sa mal vykonať pre každý uzol ako n2, n3, n4, n5, n6 a n7. Keď spracujeme každý uzol, potom zistíme, že hodnota k nie je väčšia ako 1, takže môžeme povedať, že vyššie uvedený strom je vyvážený binárny strom .
Vo vyššie uvedenom strome sú n6, n4 a n3 listové uzly, kde n6 je najvzdialenejší uzol od koreňového uzla. Medzi koreňovým uzlom a listovým uzlom existujú tri okraje; výška vyššie uvedeného stromu je teda 3. Keď uvažujeme n1 ako koreňový uzol, potom ľavý podstrom obsahuje uzly n2, n4, n5 a n6, zatiaľ čo podstrom obsahuje uzol n3. V ľavom podstrome je n2 koreňový uzol a n4 a n6 sú listové uzly. Medzi uzlami n4 a n6 je n6 najvzdialenejší uzol od svojho koreňového uzla a n6 má dve hrany; preto je výška ľavého podstromu 2. Pravý podstrom má na ľavej a pravej strane nejaké potomstvo; teda výška pravého podstromu je 0. Keďže výška ľavého podstromu je 2 a pravého podstromu je 0, tak rozdiel medzi výškou ľavého podstromu a pravého podstromu je 2. Podľa definície je rozdiel medzi výškou ľavého podstromu a pravého podstromu nesmie byť väčšia ako 1. V tomto prípade je rozdiel 2, čo je väčšie ako 1; preto je vyššie uvedený binárny strom nevyváženým binárnym vyhľadávacím stromom.
Prečo potrebujeme vyvážený binárny strom?
Poďme pochopiť potrebu vyváženého binárneho stromu prostredníctvom príkladu.
Vyššie uvedený strom je binárny vyhľadávací strom, pretože všetky ľavé uzly podstromu sú menšie ako jeho rodičovský uzol a všetky pravé uzly podstromu sú väčšie ako jeho rodičovský uzol. Predpokladajme, že chceme nájsť hodnotu 79 vo vyššie uvedenom strome. Najprv porovnáme hodnotu uzla n1 s 79; keďže hodnota 79 sa nerovná 35 a je väčšia ako 35 tak sa presunieme do uzla n3, teda 48. Keďže hodnota 79 sa nerovná 48 a 79 je väčšia ako 48, tak sa presunieme doprava potomok 48. Hodnota pravého potomka uzla 48 je 79, čo sa rovná hodnote, ktorá sa má hľadať. Počet skokov požadovaných na vyhľadávanie prvku 79 je 2 a maximálny počet skokov požadovaných na vyhľadávanie akéhokoľvek prvku je 2. Priemerný prípad vyhľadávania prvku je O(logn).
Vyššie uvedený strom je tiež binárny vyhľadávací strom, pretože všetky ľavé uzly podstromu sú menšie ako jeho rodičovský uzol a všetky pravé uzly podstromu sú väčšie ako jeho rodičovský uzol. Predpokladajme, že chceme nájsť hodnotu 79 vo vyššie uvedenom strome. Najprv porovnáme hodnotu 79 s uzlom n4, t.j. 13. Keďže hodnota 79 je väčšia ako 13, presunieme sa k pravému potomkovi uzla 13, t.j. n2 (21). Hodnota uzla n2 je 21, čo je menšie ako 79, preto sa opäť presunieme doprava od uzla 21. Hodnota pravého potomka uzla 21 je 29. Keďže hodnota 79 je väčšia ako 29, presunieme sa doprava potomok uzla 29. Hodnota pravého potomka uzla 29 je 35, čo je menšie ako 79, takže sa presunieme k pravému potomkovi uzla 35, t.j. 48. Hodnota 79 je väčšia ako 48, preto sa presunieme k správnemu potomkovi uzla 48. Hodnota pravého podriadeného uzla 48 je 79, čo sa rovná hodnote, ktorá sa má hľadať. V tomto prípade je počet skokov potrebných na vyhľadanie prvku 5. V tomto prípade je najhorší prípad O(n).
rudyard kipling ako vysvetlenie
Ak sa počet uzlov zvýši, vzorec použitý v stromovom diagrame1 je efektívnejší ako vzorec použitý v stromovom diagrame2. Predpokladajme, že počet dostupných uzlov v oboch vyššie uvedených stromoch je 100 000. Na vyhľadanie akéhokoľvek prvku v stromovom diagrame2 je potrebný čas 100 000 µs, zatiaľ čo čas potrebný na vyhľadanie prvku v stromovom diagrame je log(100 000), čo sa rovná 16,6 µs. Môžeme pozorovať obrovský časový rozdiel medzi nad dvoma stromami. Preto sme dospeli k záveru, že bilančný strom rovnováhy poskytuje vyhľadávanie rýchlejšie ako dátová štruktúra lineárneho stromu.