證明的最大轉數爲兩棵樹成爲等於

在書中算法導論 - 創造性的方法，問題4.24：證明的最大轉數爲兩棵樹成爲等於

設T1和T2是兩個任意的樹，每個都具有n個節點。證明對T1應用至多2n的旋轉是足夠的，以便它等於T2。

對於二叉搜索樹，我想通了一個算法：

查找等於T2的根元素，讓我們把它定位根。
使用AVL旋轉策略，旋轉target-root使其成爲T1的新根。
在此過程中，可能會執行多次旋轉。
對於T1和T2的左子樹，按照上面的方式遞歸處理它們。
對於T1和T2的右子樹，按遞歸方式處理它們。

該算法在最壞的情況下以O（N^2）運行。

我不太明白「任意樹」這個詞，我不知道如何讓T1等於T2。

任何人都可以幫助解決這個問題嗎？

來源

2013-11-24 Guocheng

我不知道有沒有簡單的答案。我認爲這篇論文是一個很好的起點。 Daniel Sleator，Robert Tarjan和William Thurston指出，任何兩棵n節點樹（n≥11）之間的旋轉距離至多爲2n-6，並且無限多對樹相距甚遠。 http://www.ams.org/journals/jams/1988-01-03/S0894-0347-1988-0928904-4/home.html – amald

@amald謝謝，我將閱讀文件 – Guocheng

無論從什麼我有，我可以建議可以在O解決這一問題的算法（N）旋轉，但無法得到確切的上限，但認爲你可以建立在此： -

這裏是僞代碼用於算法： -

//Method to make T1 equivalent to T2 

    alignTree(T1,T2) { 

    if(length(T1)==1) 
     return 

    else { 

     Node k = FindRoot(T1,T2) 
     rotateAbout(k) 
     align(T1.left,T2.left) 
     align(T1.right,T2.right) 
    } 


    }

FindRoot假設發現這被認爲是新的樹的根這相當於樹T1的節點。假設rotateAbout(K)對根進行適當的旋轉以獲得新樹的左右子樹上的等價節點。然後我們可以遞歸地求解較小子樹上的較小子問題。

無旋轉：正如你在僞代碼中看到的沒有旋轉相當於pre-order遍歷樹是O(N)

注：您可以隨時擴展爲一般的樹上面的僞代碼並仍然具有相同的複雜性。

來源

2013-11-24 15:31:25

我不認爲rotateAbout （K）需要一段時間。假設T1是通過插入10,9,8,7,6,5,4,3,2,1生成的樹，T2是通過插入1,2,3,4,5， 6,7,8,9,10。然後首先我們旋轉關於（1），如果我們使用單次旋轉（AVL單次旋轉），則需要9個步驟。 – Guocheng

@ Guocheng在對齊兩棵樹時，我們不匹配樹的鍵，但只有兩棵樹的結構必須相同，所以根始終是左右兩側具有相同節點的節點。此外，我們不用計算算法的時間複雜度，而只需要對齊樹的旋轉數。 –

那麼我們如何決定T1的新根節點以及如何旋轉以確保子樹具有相同數量的節點？ – Guocheng

證明的最大轉數爲兩棵樹成爲等於

回答

相關問題