Odniesienie do podstawowego twierdzenia o rotacji drzew

13

Mówi się, że dwa drzewa wyszukiwania binarnego są liniowo równoważne, jeśli zgadzają się w swoich wędrówkach w kolejności. Poniższe twierdzenie wyjaśnia, dlaczego rotacje drzew są tak fundamentalne:

Niech A i B będą binarnymi drzewami wyszukiwania. Zatem A i B są liniowo równoważne wtedy i tylko wtedy, gdy są połączone sekwencją obrotów drzewa.

Zauważyłem ten wynik, kiedy po raz pierwszy uczyłem się o strukturach danych i chciałem głębiej zrozumieć specjalny status rotacji drzew.

Dowód jest prosty i intuicyjny: obróć najmniejszy element do pozycji korzenia wzdłuż lewego kręgosłupa. Zgodnie z niezmienną kolejnością to uporządkowane drzewo nie może mieć lewego poddrzewa. Teraz wróć do prawego poddrzewa. Wynik jest normalną formą do badania równoważności liniowej.

Chociaż jest to podstawowe twierdzenie, nigdy nie spotkałem go w literaturze. Byłbym bardzo wdzięczny za odniesienie, gdy będę musiał użyć tego wyniku.

(Dodatkowa łamigłówka: jaki jest najlepszy algorytm znajdowania najkrótszej sekwencji rotacji drzew łączących dwa liniowo równoważne drzewa wyszukiwania binarnego?)

reference-request ds.data-structures Per Vognsen
źródło
Innym miejscem do poszukiwania może być odniesienie, że moduł równoważności operatora asocjacyjnego jest rozstrzygalny, ponieważ sprowadza się to do tej samej rzeczy. Jednak wszystkie referencje, o których wiem, biorą ten fakt za pewnik.
Rob Simmons,

Odpowiedzi:

10

Jak wskazuje tutaj David Eppstein , nawet znalezienie najkrótszej ścieżki dla drzew binarnych nie jest znane w P. W komentarzach do tej odpowiedzi odwołuje się do najlepszych obecnych granic

Suresh Venkat
źródło
Przyjmuję tę odpowiedź, ponieważ nauczyłem się z niej czegoś. Jednak nadal chciałbym znaleźć odniesienie do twierdzenia o strukturze, jeśli ktoś je zna.
Per Vognsen
11

Wczesną pracą, która wyraźnie uczyniła to spostrzeżenie - że rotacje zachowują wewnętrzne przemierzenia - są (na ryc. 2) samoregulujące się drzewa binarne Sleator i Tarjana z 1983 roku . Heurystykę przejścia do roota zbadano w artykule na temat samoorganizujących się drzew binarnych Allen i Munro z 1978 roku .

Lew Reyzin
źródło
Interesującym kierunkiem równoważności Pera nie jest to, że rotacje zachowują kolejność, ale że można podróżować pomiędzy dowolnymi dwoma drzewami, które mają tę samą kolejność za pomocą rotacji.
Radu GRIGore,
Tak - dlatego uwzględniłem przejście do rootowania. Jest też inny artykuł Sleatora, Tarjana i Thurstona (Odległość obrotu, triangulacje i geometria hiperboliczna), w którym wyliczono odległości między dowolnymi dwoma drzewami, których nie uwzględniłem w mojej odpowiedzi. Nie sądzę, aby spostrzeżenie Pera pojawiło się w jakimkolwiek dokumencie, ale chciałbym, aby udowodniono, że się mylę.
Lev Reyzin
Racja, łatwy kierunek jest niezbędną częścią dowodów poprawności dla drzew AVL, 2-3 drzew itp. Kierunek przeciwny jest głębszy. Mówi, że nie potrzebujesz żadnych transformacji zachowujących strukturę innych niż rotacje drzew dla kompletności.
Per Vognsen,
5

O(1)O(1)

Joan M. Lucas, Wykres rotacji drzew binarnych to Hamiltonian, Journal of Algorytmy, tom 8, wydanie 4, grudzień 1987, strony 503-535, ISSN 0196-6774, DOI: 10.1016 / 0196-6774 (87) 90048-4 .

Prostszy dowód, również konstruktywny, na prostszy fakt, że ścieżka Hamiltona istnieje na wykresie rotacji, można znaleźć w tym późniejszym artykule współautorem Lucas i jej współpracowników.

Lucas JM, Vanbaronaigien DR, Ruskey F., On Rotations and the Generation of Binary Trees, Journal of Algorytms, Tom 15, Issue 3, November 1993, Pages 343-366, ISSN 0196-6774, DOI: 10.1006 / jagm.1993.1045 .

Maverick Woo
źródło
-2

W tym ostatnim można znaleźć prostszy dowód, również konstruktywny, na prostszy fakt, że ścieżka Hamiltona wychodzi z wykresu obrotu.

007singh
źródło
4
Twoja odpowiedź wydaje się niepełna?
Jeremy