Validate Binary Search Tree

Najpierw zobaczmy, jak poruszać się po tablicy. Węzeł o indeksie i ma lewe dziecko pod indeksem 2*i+1, a prawe pod indeksem 2*i+2. Dziecko istnieje tylko wtedy, gdy jego indeks znajduje się w tablicy, a wartość pod tym indeksem nie jest równa -1. W tablicy [10, 5, 15, -1, -1, 6, 20] korzeń 10 ma węzły 5 i 15 pod indeksami 1 i 2, a węzeł 15 ma węzły 6 i 20 pod indeksami 5 i 6.

Pierwszy pomysł, na który wpada większość osób, polega na porównaniu każdego węzła tylko z jego dwojgiem dzieci. Właśnie dlatego to drzewo pokazuje, że takie podejście nie działa: 5 < 10, 15 > 10, 6 < 15 i 20 > 15 są prawdziwe, ale węzeł 6 znajduje się na prawo od 10. Definicja mówi o każdej wartości w poddrzewie, więc sprawdźmy dokładnie to.

Dla węzła przechowującego v wszystkie wartości po jego lewej stronie są mniejsze od v dokładnie wtedy, gdy największa wartość po jego lewej stronie jest mniejsza od v. Podobnie wszystkie wartości po jego prawej stronie są większe od v, gdy najmniejsza wartość po tej stronie jest większa od v. Dwie niewielkie funkcje rekurencyjne znajdują tę największą i najmniejszą wartość. Dla pustej strony największą wartością jest -1, a najmniejszą 100001 — są to wartości spoza dozwolonego zakresu, więc pusta strona nigdy nie spowoduje niepowodzenia.

To rozwiązanie jest poprawne, ale powtarza pracę. Węzeł jest przeglądany raz dla każdego swojego przodka, więc łączna liczba odwiedzin wynosi około n × h dla drzewa o głębokości h. Przy głębokości nieprzekraczającej 14 nie stanowi to tutaj problemu, ale w drzewie będącym jedną długą ścieżką złożoną z n węzłów złożoność rośnie do O(n²).

Przejście inorder odwiedza lewe poddrzewo, następnie węzeł, a potem prawe poddrzewo. W drzewie przeszukiwań binarnych ta kolejność jest posortowana: wszystko po lewej stronie jest mniejsze, więc pojawia się wcześniej, a wszystko po prawej stronie jest większe, więc pojawia się później. Pierwszy przykład daje 1, 3, 6, 8, 10, 12, 15.

Zależność działa też w drugą stronę i właśnie dlatego jest to test. Weź dowolny węzeł v. W sekwencji inorder całe jego lewe poddrzewo znajduje się bezpośrednio przed nim, a całe prawe poddrzewo — bezpośrednio po nim. Jeśli sekwencja jest ściśle rosnąca, każda wartość przed v jest mniejsza, a każda wartość po nim jest większa, więc reguła jest spełniona dla v i tak samo dla każdego innego węzła.

Przejdź więc drzewo w kolejności inorder, zbierz wartości i sprawdź każdą z nich względem poprzedniej. Drugi przykład daje 5, 10, 6, 15, 20: krok od 10 w dół do 6 ujawnia węzeł po niewłaściwej stronie. Trzeci daje 7, 12, 12, a powtórzone 12 nie przechodzi ścisłego sprawdzenia. Każdy węzeł jest odwiedzany raz, co daje czas O(n), a lista zajmuje O(n) miejsca.

Spójrz na tę regułę z perspektywy węzła. Każdy przodek wyznacza dla niego jedno ograniczenie. Jeśli węzeł znajduje się w lewym poddrzewie przodka zawierającego a, jego wartość musi być mniejsza od a; jeśli znajduje się w prawym poddrzewie, musi być większa od a. Wszystkie te ograniczenia razem tworzą jeden otwarty przedział (low, high), a węzeł jest na właściwym miejscu dokładnie wtedy, gdy jego wartość leży ściśle wewnątrz tego przedziału.

Możesz wyznaczać ten przedział podczas schodzenia w dół. Korzeń nie ma ograniczeń. Przechodząc od węzła zawierającego v do jego lewego dziecka, zachowujesz low i obniżasz high do v; przechodząc do prawego dziecka, zachowujesz high i podnosisz low do v. Nowe ograniczenie jest zawsze bardziej rygorystyczne niż zastępowane, ponieważ samo v przeszło sprawdzian względem poprzedniego przedziału.

W drugim przykładzie 15 otrzymuje przedział (10, no limit) i przekazuje go swojemu lewemu dziecku jako (10, 15). Wartość 6 jest mniejsza od 10, więc sprawdzian kończy się niepowodzeniem już w tym miejscu, bez sprawdzania jakiegokolwiek innego węzła. Wartości mieszczą się w zakresie od 0 do 10^5, więc -1 i 100001 pełnią funkcję „braku ograniczenia”.

Przechowuj oczekujące węzły wraz z ich przedziałami na stosie. Każdy węzeł jest sprawdzany raz, co zajmuje O(n) czasu, a stos przechowuje oczekujące węzły leżące wzdłuż jednej ścieżki, co wymaga O(h) pamięci. Pierwszy nieprawidłowy przedział kończy wyszukiwanie.