Natknąłem się na to stare pytanie, szukając czegoś innego. Zauważyłem, że nigdy nie otrzymałeś pełnej odpowiedzi.
Sposobem rozwiązania tego problemu jest rozpoczęcie od napisania specyfikacji funkcji, którą próbujesz napisać.
Specyfikacja: O dobrze uformowanym drzewie binarnym mówi się, że jest „zrównoważone wysokością”, jeśli (1) jest puste lub (2) jego lewe i prawe elementy potomne mają zrównoważoną wysokość, a wysokość lewego drzewa mieści się w zakresie 1 od wysokość prawego drzewa.
Teraz, gdy masz już specyfikację, napisanie kodu jest banalne. Wystarczy postępować zgodnie ze specyfikacją:
IsHeightBalanced(tree)
return (tree is empty) or
(IsHeightBalanced(tree.left) and
IsHeightBalanced(tree.right) and
abs(Height(tree.left) - Height(tree.right)) <= 1)
Przetłumaczenie tego na wybrany język programowania powinno być banalne.
Dodatkowe ćwiczenie : ten naiwny szkic kodu przemierza drzewo zbyt wiele razy podczas obliczania wysokości. Czy możesz uczynić to bardziej wydajnym?
Super dodatkowe ćwiczenie : załóżmy, że drzewo jest bardzo niezrównoważone. Na przykład milion węzłów po jednej stronie i trzy po drugiej. Czy istnieje scenariusz, w którym ten algorytm rozwala stos? Czy możesz naprawić implementację tak, aby nigdy nie wysadzała stosu, nawet jeśli otrzymujesz masowo niezrównoważone drzewo?
AKTUALIZACJA : Donal Fellows wskazuje w swojej odpowiedzi, że istnieją różne definicje „zrównoważonego”, które można wybrać. Na przykład, można by przyjąć bardziej rygorystyczną definicję „zrównoważonego wzrostu” i wymagać, aby długość ścieżki do najbliższego pustego dziecka znajdowała się w obrębie jednej ze ścieżek do najdalszego pustego dziecka. Moja definicja jest mniej surowa i dlatego dopuszcza więcej drzew.
Można też być mniej restrykcyjne niż moja definicja; można powiedzieć, że zrównoważone drzewo to takie, w którym maksymalna długość ścieżki do pustego drzewa na każdej gałęzi różni się nie więcej niż o dwa, trzy lub o jakąś inną stałą. Albo, że maksymalna długość ścieżki jest ułamkiem minimalnej długości ścieżki, na przykład pół lub ćwiartka.
Zwykle to naprawdę nie ma znaczenia. Celem każdego algorytmu równoważenia drzewa jest zapewnienie, że nie skończysz w sytuacji, w której masz milion węzłów po jednej stronie i trzy po drugiej. Definicja Donala jest w teorii dobra, ale w praktyce wymyślanie algorytmu równoważenia drzewa, który spełnia ten poziom ścisłości, jest uciążliwe. Oszczędności wydajności zwykle nie uzasadniają kosztów wdrożenia. Spędzasz dużo czasu wykonując niepotrzebne przestawianie drzew, aby osiągnąć poziom równowagi, który w praktyce nie ma większego znaczenia. Kogo to obchodzi, jeśli czasami potrzeba czterdziestu gałęzi, aby dostać się do najdalszego liścia w milionie węzłów niedoskonale zrównoważonym drzewie, podczas gdy teoretycznie w idealnie zrównoważonym drzewie może zajmować tylko dwadzieścia? Chodzi o to, że nigdy nie potrzeba miliona. Przejście od najgorszego przypadku miliona do najgorszego przypadku czterdziestki jest zwykle wystarczająco dobre; nie musisz dążyć do optymalnego przypadku.