使用旋轉的二叉樹轉換

當我在中期研究二叉樹時，發現任何任意的n節點二叉樹可以轉換成任何其他n節點二叉樹，最多2 * n-2個旋轉。有沒有證據呢？我發現了一些有漸近符號的證明，但它並不那麼清楚。我的意思是有人可以解釋/說明它爲什麼是真的？如果它說n節點二叉樹，它是否包含根？使用旋轉的二叉樹轉換

來源

2013-10-28 user1722022

這聽起來不對，因爲旋轉不會改變節點的順序。你確定沒有其他限制嗎？ – Beta

http://repository.cmu.edu/cgi/viewcontent.cgi?article=2663&context=compsci也許你想參考這篇論文。 –

本答案來自CLRS第3版教材13.2-4。

讓

左=整個左鏈表二叉樹

RIGHT =整個右鏈表二叉樹。

在（n-1）旋轉中，您可以輕鬆地將左旋轉至右旋。

 
e.g: n = 3 
    3    2    1 
    2  to  1 3 to  2 
1         3

證明：由於根據定義，各右旋轉將增加的最右邊的路徑長度由至少1。因此，從與長度爲1（最差情況）最右邊的路徑開始，則需要最多（n-1）旋轉以使其進入右側。因此，你可以很容易得出結論，任何具有n個節點的二叉樹的任意形狀都可以在（n-1）個旋轉內旋轉爲RIGHT。設T_1爲您開始的節點設T_2爲您結束的節點。

您可以在（n-1）次旋轉內將T_1旋轉到右側。同樣，您可以在（n-1）次旋轉中將T_2旋轉到RIGHT。

因此，要將T_1旋轉到T_2，只需將T_1旋轉到RIGHT，然後執行反轉從RIGHT旋轉到T_2。因此，你可以在（n-1）+（n-1）= 2n-2的上限旋轉中做到這一點。

 
Hope this helps!=) 
Soon Chee Loong, 
University of Toronto

來源

2014-11-02 08:55:29

如果語句引用二叉樹而不是BST樹，我認爲該語句是有效的，因爲沒有對節點順序的限制。一個簡單的數學歸納應該證明這個說法。

來源

2013-11-18 14:57:22 Pandrei

使用旋轉的二叉樹轉換

回答

相關問題