Zrównoważone drzewo binarne jest również znane jako drzewo o zrównoważonej wysokości. Definiuje się je jako drzewo binarne, gdy różnica wysokości lewego i prawego poddrzewa nie jest większa niż m, gdzie m jest zwykle równe 1. Wysokość drzewa to liczba krawędzi na najdłuższej ścieżce pomiędzy węzeł główny i węzeł liściowy.
Powyższe drzewo to a drzewo wyszukiwania binarnego . Drzewo wyszukiwania binarnego to drzewo, w którym każdy węzeł po lewej stronie ma niższą wartość niż jego węzeł nadrzędny, a węzeł po prawej stronie ma wyższą wartość niż jego węzeł nadrzędny. W powyższym drzewie n1 jest węzłem głównym, a n4, n6, n7 są węzłami liściowymi. Węzeł n7 jest węzłem najdalszym od węzła głównego. Linie n4 i n6 zawierają 2 krawędzie, a pomiędzy węzłem głównym a węzłem n7 istnieją trzy krawędzie. Ponieważ n7 jest najdalej od węzła głównego; dlatego wysokość powyższego drzewa wynosi 3.
format ciągu
Teraz zobaczymy, czy powyższe drzewo jest zrównoważone, czy nie. Lewe poddrzewo zawiera węzły n2, n4, n5 i n7, natomiast prawe poddrzewo zawiera węzły n3 i n6. Lewe poddrzewo ma dwa węzły-liście, tj. n4 i n7. Pomiędzy węzłami n2 i n4 istnieje tylko jedna krawędź oraz dwie krawędzie pomiędzy węzłami n7 i n2; dlatego węzeł n7 jest najdalej od węzła głównego. Wysokość lewego poddrzewa wynosi 2. Prawe poddrzewo zawiera tylko jeden węzeł-liście, tj. n6, i ma tylko jedną krawędź; zatem wysokość prawego poddrzewa wynosi 1. Różnica pomiędzy wysokościami lewego i prawego poddrzewa wynosi 1. Ponieważ otrzymaliśmy wartość 1, możemy powiedzieć, że powyższe drzewo jest drzewem o zrównoważonej wysokości. Ten proces obliczania różnicy między wysokościami należy wykonać dla każdego węzła, np. n2, n3, n4, n5, n6 i n7. Kiedy przetworzymy każdy węzeł, okaże się, że wartość k nie jest większa niż 1, więc możemy powiedzieć, że powyższe drzewo jest zrównoważone drzewo binarne .
W powyższym drzewie n6, n4 i n3 to węzły-liście, gdzie n6 to węzeł położony najdalej od węzła głównego. Pomiędzy węzłem głównym a węzłem liściowym istnieją trzy krawędzie; zatem wysokość powyższego drzewa wynosi 3. Gdy za węzeł główny uznamy n1, to lewe poddrzewo zawiera węzły n2, n4, n5 i n6, natomiast poddrzewo zawiera węzeł n3. W lewym poddrzewie n2 jest węzłem głównym, a n4 i n6 są węzłami liściowymi. Spośród węzłów n4 i n6 n6 jest węzłem położonym najdalej od węzła głównego, a n6 ma dwie krawędzie; dlatego wysokość lewego poddrzewa wynosi 2. Prawe poddrzewo ma po lewej i prawej stronie jakiekolwiek dziecko; zatem wysokość prawego poddrzewa wynosi 0. Ponieważ wysokość lewego poddrzewa wynosi 2, a prawego poddrzewa wynosi 0, więc różnica pomiędzy wysokością lewego i prawego poddrzewa wynosi 2. Zgodnie z definicją różnica pomiędzy wysokością lewego poddrzewa i prawego poddrzewa nie może być większa niż 1. W tym przypadku różnica wynosi 2, czyli jest większa niż 1; dlatego powyższe drzewo binarne jest niezrównoważonym drzewem wyszukiwania binarnego.
Dlaczego potrzebujemy zrównoważonego drzewa binarnego?
Rozumiemy potrzebę zrównoważonego drzewa binarnego na przykładzie.
Powyższe drzewo jest drzewem wyszukiwania binarnego, ponieważ wszystkie lewe węzły poddrzewa są mniejsze niż jego węzeł nadrzędny, a wszystkie prawe węzły poddrzewa są większe niż jego węzeł nadrzędny. Załóżmy, że chcemy znaleźć wartość 79 w powyższym drzewie. Najpierw porównujemy wartość węzła n1 z 79; ponieważ wartość 79 nie jest równa 35 i jest większa od 35 to przechodzimy do węzła n3 czyli 48. Ponieważ wartość 79 nie jest równa 48 a 79 jest większa od 48 więc ruszamy w prawo dziecko 48. Wartość prawego dziecka węzła 48 wynosi 79, co jest równe wartości do przeszukania. Liczba przeskoków wymaganych do przeszukania elementu 79 wynosi 2, a maksymalna liczba przeskoków wymaganych do przeszukania dowolnego elementu wynosi 2. Średni przypadek przeszukania elementu to O(logn).
Powyższe drzewo jest również drzewem wyszukiwania binarnego, ponieważ wszystkie lewe węzły poddrzewa są mniejsze niż jego węzeł nadrzędny, a wszystkie prawe węzły poddrzewa są większe niż jego węzeł nadrzędny. Załóżmy, że chcemy znaleźć wartość 79 w powyższym drzewie. Najpierw porównujemy wartość 79 z węzłem n4, czyli 13. Ponieważ wartość 79 jest większa od 13, zatem przechodzimy do prawego dziecka węzła 13, czyli n2 (21). Wartość węzła n2 wynosi 21, czyli jest mniejsza niż 79, więc ponownie przesuwamy się na prawo od węzła 21. Wartość prawego dziecka węzła 21 wynosi 29. Ponieważ wartość 79 jest większa niż 29, więc przesuwamy się w prawo dziecko węzła 29. Wartość prawego dziecka węzła 29 wynosi 35, czyli jest mniejsza niż 79, więc przechodzimy do prawego dziecka węzła 35, czyli 48. Wartość 79 jest większa niż 48, więc przechodzimy do prawego dziecka węzła 48. Wartość prawego węzła podrzędnego węzła 48 wynosi 79, co jest równe wartości do przeszukania. W tym przypadku liczba przeskoków wymaganych do przeszukania elementu wynosi 5. W tym przypadku najgorszym przypadkiem jest O(n).
obiektywna Java
Jeżeli liczba węzłów wzrasta, formuła zastosowana na schemacie drzewiastym1 jest skuteczniejsza niż formuła zastosowana na schemacie drzewiastym2. Załóżmy, że liczba węzłów dostępnych w obu powyższych drzewach wynosi 100 000. Aby przeszukać dowolny element na diagramie drzewiastym2, czas potrzebny na przeszukanie elementu na diagramie drzewiastym wynosi 100 000 µs, natomiast czas potrzebny na przeszukanie elementu na schemacie drzewiastym wynosi log(100 000), co równa się 16,6 µs. Możemy zaobserwować ogromną różnicę czasu pomiędzy powyższymi dwoma drzewami. Dlatego wnioskujemy, że zrównoważone drzewo binarne zapewnia wyszukiwanie szybsze niż liniowa struktura danych drzewa.