Referensi untuk teorema dasar rotasi pohon

13

Dua pohon pencarian biner dikatakan setara secara linear ketika mereka setuju dalam traversal berurutan mereka. Teorema berikut menjelaskan mengapa rotasi pohon sangat mendasar:

Biarkan A dan B menjadi pohon pencarian biner. Kemudian A dan B setara secara linier jika dan hanya jika mereka dihubungkan oleh urutan rotasi pohon.

Saya perhatikan hasil ini ketika saya pertama kali belajar tentang struktur data sejak lama dan ingin memahami status khusus rotasi pohon lebih dalam.

Buktinya sederhana dan intuitif: Putar elemen terkecil ke posisi root di sepanjang tulang belakang kiri. Sesuai urutan pesanan, pohon yang disusun ulang ini tidak boleh memiliki subtree kiri. Sekarang ulangi pada subtree kanan. Hasilnya adalah bentuk normal untuk menguji kesetaraan linier.

Meskipun ini adalah teorema dasar, saya tidak pernah menemukan itu dalam literatur. Saya akan sangat menghargai referensi untuk waktu berikutnya saya perlu menggunakan hasil ini.

(Bonus asah otak: Apa algoritma terbaik untuk menemukan urutan rotasi pohon terpendek yang menghubungkan dua pohon pencarian biner yang setara secara linear?)

reference-request ds.data-structures Per Vognsen
sumber
Tempat lain untuk mencari mungkin untuk referensi bahwa modulo ekivalensi operator asosiatif dapat dipilih, karena jumlah ini sama dengan hal yang sama. Namun, semua referensi yang saya sadari menerima kenyataan ini begitu saja.
Rob Simmons

Jawaban:

10

Seperti yang ditunjukkan David Eppstein di sini , bahkan menemukan jalur terpendek untuk pohon biner tidak diketahui berada di P. Dalam komentar untuk jawaban itu ia terhubung ke batas terbaik saat ini

Suresh Venkat
sumber
Saya menerima jawaban ini karena saya belajar sesuatu darinya. Namun, saya masih suka mencari referensi untuk teorema struktur jika ada yang tahu.
Per Vognsen
11

Sebuah makalah awal yang membuat pengamatan ini secara eksplisit - bahwa rotasi menjaga traverse inorder - adalah (dalam Gambar 2 dari) Sleator dan Tarjan's 1983, pohon pencarian biner yang menyesuaikan diri . Heuristik pindah-ke-akar dipelajari dalam makalah Allen Binary Search Trees Allen and Munro tahun 1978 .

Lev Reyzin
sumber
Arah yang menarik dalam ekuivalen Per bukanlah rotasi yang dipertahankan secara berurutan, tetapi Anda dapat melakukan perjalanan di antara dua pohon yang memiliki urutan yang sama menggunakan rotasi.
Radu GRIGore
Ya - itu sebabnya saya menyertakan pemindahan ke root. Ada juga makalah lain oleh Sleator, Tarjan, & Thurston (Jarak Rotasi, Triangulasi, dan Geometri Hiperbolik) menghitung jarak antara dua pohon, yang tidak saya sertakan dalam jawaban saya. Saya tidak berpikir bahwa pengamatan Per muncul di salah satu kertas seperti apa adanya, tapi saya ingin terbukti salah.
Lev Reyzin
Benar, arah yang mudah adalah bagian penting dari bukti kebenaran untuk pohon AVL, 2-3 pohon, dll. Arah sebaliknya lebih dalam. Dikatakan bahwa Anda tidak memerlukan transformasi pelestarian struktur selain rotasi pohon untuk kelengkapan.
Per Vognsen
5

Karena Anda tertarik pada struktur rotasi pohon, saya pikir Anda mungkin juga tertarik dengan makalah berikut, yang menunjukkan bahwa grafik rotasi pohon biner dari sejumlah node memiliki siklus Hamilton . Faktanya Lucas menunjukkan bahwa siklus dapat dilalui dengan penundaan konstan per pohon. (Rotasi dapat dilakukan diHAI(1) waktu tentu saja, tetapi tidak jelas apriori bahwa kita harus dapat memutuskan rotasi yang akan dilakukan sepanjang siklus Hamiltonian di HAI(1) waktu.) Secara alami, Anda mungkin juga tertarik dengan referensi di dalamnya.

Joan M. Lucas, Grafik rotasi pohon biner adalah Hamiltonian, Jurnal Algoritma, Volume 8, Edisi 4, Desember 1987, Halaman 503-535, ISSN 0196-6774, DOI: 10.1016 / 0196-6774 (87) 90048-4 .

Bukti yang lebih sederhana, juga konstruktif, dari fakta yang lebih sederhana bahwa jalur Hamilton ada dalam grafik rotasi dapat ditemukan dalam makalah ini nanti yang ditulis bersama oleh Lucas dan kolaboratornya.

Lucas JM, DR Vanbaronaigien, Ruskey F., Tentang Rotasi dan Generasi Pohon Biner, Jurnal Algoritma, Volume 15, Edisi 3, November 1993, Halaman 343-366, ISSN 0196-6774, DOI: 10.1006 / jagm.1993.1045 .

Maverick Woo
sumber
-2

Bukti yang lebih sederhana, juga konstruktif, dari fakta yang lebih sederhana bahwa jalur Hamiltonian keluar dalam grafik rotasi dapat ditemukan dalam yang terakhir ini.

007singh
sumber
4
Jawaban Anda sepertinya tidak lengkap?
Jeremy