Vyvážený binární strom je také známý jako výškově vyvážený strom. Je definován jako binární strom, když rozdíl mezi výškou levého podstromu a pravého podstromu není větší než m, kde m se obvykle rovná 1. Výška stromu je počet hran na nejdelší cestě mezi kořenový uzel a listový uzel.
Výše uvedený strom je a binární vyhledávací strom . Binární vyhledávací strom je strom, ve kterém má každý uzel na levé straně nižší hodnotu než jeho nadřazený uzel a uzel na pravé straně má vyšší hodnotu než jeho nadřazený uzel. Ve výše uvedeném stromu je n1 kořenový uzel a n4, n6, n7 jsou listové uzly. Uzel n7 je nejvzdálenější uzel od kořenového uzlu. n4 a n6 obsahují 2 hrany a mezi kořenovým uzlem a uzlem n7 existují tři hrany. Protože n7 je nejdále od kořenového uzlu; výška výše uvedeného stromu je tedy 3.
Nyní uvidíme, zda je výše uvedený strom vyvážený nebo ne. Levý podstrom obsahuje uzly n2, n4, n5 a n7, zatímco pravý podstrom obsahuje uzly n3 a n6. Levý podstrom má dva listové uzly, tj. n4 a n7. Mezi uzly n2 a n4 je pouze jedna hrana a mezi uzly n7 a n2 dvě hrany; proto je uzel n7 nejdále od kořenového uzlu. Výška levého podstromu je 2. Pravý podstrom obsahuje pouze jeden listový uzel, tj. n6, a má pouze jednu hranu; výška pravého podstromu je tedy 1. Rozdíl mezi výškami levého podstromu a pravého podstromu je 1. Protože jsme dostali hodnotu 1, můžeme říci, že výše uvedený strom je výškově vyvážený strom. Tento proces výpočtu rozdílu mezi výškami by měl být proveden pro každý uzel jako n2, n3, n4, n5, n6 a n7. Když zpracujeme každý uzel, pak zjistíme, že hodnota k není větší než 1, takže můžeme říci, že výše uvedený strom je vyvážený binární strom .
Ve výše uvedeném stromu jsou n6, n4 a n3 listové uzly, kde n6 je nejvzdálenější uzel od kořenového uzlu. Mezi kořenovým a listovým uzlem existují tři hrany; výška výše uvedeného stromu je tedy 3. Když uvažujeme n1 jako kořenový uzel, pak levý podstrom obsahuje uzly n2, n4, n5 a n6, zatímco podstrom obsahuje uzel n3. V levém podstromu je n2 kořenový uzel a n4 a n6 jsou listové uzly. Mezi n4 a n6 uzly je n6 nejvzdálenější uzel od kořenového uzlu a n6 má dvě hrany; výška levého podstromu je tedy 2. Pravý podstrom má na levé a pravé straně jakékoli potomky; proto je výška pravého podstromu 0. Protože výška levého podstromu je 2 a pravého podstromu je 0, tak rozdíl mezi výškou levého podstromu a pravého podstromu je 2. Podle definice je rozdíl mezi výškou levého podstromu a pravého podstromu nesmí být větší než 1. V tomto případě je rozdíl 2, což je větší než 1; proto je výše uvedený binární strom nevyváženým binárním vyhledávacím stromem.
Proč potřebujeme vyvážený binární strom?
Pojďme pochopit potřebu vyváženého binárního stromu na příkladu.
azurové předplatné
Výše uvedený strom je binární vyhledávací strom, protože všechny levé uzly podstromu jsou menší než jeho nadřazený uzel a všechny pravé uzly podstromu jsou větší než jeho nadřazený uzel. Předpokládejme, že chceme ve výše uvedeném stromu najít hodnotu 79. Nejprve porovnáme hodnotu uzlu n1 s hodnotou 79; protože hodnota 79 není rovna 35 a je větší než 35, přesuneme se do uzlu n3, tedy 48. Protože hodnota 79 není rovna 48 a 79 je větší než 48, přesuneme se doprava potomek 48. Hodnota pravého potomka uzlu 48 je 79, což se rovná hodnotě, která se má hledat. Počet přeskoků potřebných k prohledání prvku 79 je 2 a maximální počet přeskoků potřebných k prohledání jakéhokoli prvku je 2. Průměrný případ prohledání prvku je O(logn).
Výše uvedený strom je také binární vyhledávací strom, protože všechny levé uzly podstromu jsou menší než jeho nadřazený uzel a všechny pravé uzly podstromu jsou větší než jeho nadřazený uzel. Předpokládejme, že chceme najít hodnotu 79 ve výše uvedeném stromu. Nejprve porovnáme hodnotu 79 s uzlem n4, tj. 13. Protože hodnota 79 je větší než 13, přesuneme se k pravému potomkovi uzlu 13, tj. n2 (21). Hodnota uzlu n2 je 21, což je menší než 79, přesuneme se tedy opět vpravo od uzlu 21. Hodnota pravého potomka uzlu 21 je 29. Protože hodnota 79 je větší než 29, přesuneme se doprava potomek uzlu 29. Hodnota pravého potomka uzlu 29 je 35, což je menší než 79, takže se přesuneme k pravému potomkovi uzlu 35, tj. 48. Hodnota 79 je větší než 48, přesuneme se tedy ke správnému potomkovi uzlu 48. Hodnota pravého podřízeného uzlu 48 je 79, což se rovná hodnotě, která se má hledat. V tomto případě je počet skoků potřebných k vyhledání prvku 5. V tomto případě je nejhorší případ O(n).
Pokud se počet uzlů zvýší, vzorec použitý ve stromovém diagramu1 je efektivnější než vzorec použitý ve stromovém diagramu2. Předpokládejme, že počet uzlů dostupných v obou výše uvedených stromech je 100 000. Prohledání libovolného prvku ve stromovém diagramu2 trvá 100 000 µs, zatímco doba potřebná k vyhledání prvku ve stromovém diagramu je log(100 000), což se rovná 16,6 µs. Můžeme pozorovat obrovský rozdíl v čase mezi nad dvěma stromy. Proto jsme dospěli k závěru, že bilanční strom rovnováhy umožňuje vyhledávání rychleji než datová struktura lineárního stromu.