是否總是有可能使用樹輪旋轉將一個BST變成另一個BST？

給定一組值，可能有許多不同的可能的二叉搜索樹，可以從這些值形成。例如，對於值1，2，3，有五個BSTS我們可以從這些值使：是否總是有可能使用樹輪旋轉將一個BST變成另一個BST？

1  1  2  3  3 
\  \ /\ / /
    2  3 1 3 1  2 
    \ /   \ /
    3 2    2 1

許多數據結構是基於平衡二叉搜索樹使用tree rotations作爲一種原始的在不破壞所需的二分查找樹不變式的情況下重塑BST。樹旋轉可用於拉節點向上其父以上，如下所示：

   rotate 
     u  right   v 
     /\  ----->  /\ 
     v C     A u 
    /\  <-----   /\ 
    A B  rotate   B C 
       left

給出一個包含有一組值的BST，是它總是可能的是BST轉換成任意其它BST對於相同一組值？例如，我們是否可以通過使用樹輪轉換將上述五個BST中的任何一個轉換爲任何其他BST？

來源

2012-12-25 templatetypedef

您的問題的答案取決於您是否被允許在BST中具有相同的值，這些值可能會相互不同。例如，如果您的BST存儲了鍵/值對，那麼對於相同的鍵/值對，將這些鍵/值對的一個BST轉換爲不同的BST並不總是可能的。

原因是無論執行多少樹循環，BST中節點的次序遍歷都保持不變。因此，如果節點的次序遍歷不同，則不可能從一個BST轉換到另一個BST。作爲一個非常簡單的例子，假設你有一個BST持有兩個數字1的副本，每個副本都用不同的值（比如A或B）註釋。在這種情況下，有沒有辦法把這兩棵樹到彼此用樹旋轉：

 1:a   1:b 
     \    \ 
     1:b   1:a

您可以通過暴力破解的（！非常小）組可能的樹，你可以用做檢查這旋轉。然而，足以注意到，第一棵樹的次序遍歷給出1：a，1：b，並且第二棵樹的次序遍歷給出1：b，1：a。因此，沒有足夠的轉數足以在樹之間轉換。另一方面，如果所有的值都不同，那麼總是可以通過應用正確數量的樹旋轉來在兩個BST之間進行轉換。我將使用關於節點數量的歸納論證來證明這一點。

作爲一個簡單的基本情況，如果樹中沒有節點，那麼只有一個可能的BST持有這些節點：空樹。因此，始終可以在兩棵樹之間進行轉換，因爲開始和結束樹必須始終相同。

對於感應步驟中，讓我們假設，對於任何兩個BSTS 0，1，2，...，n，其中相同的值的節點，即它總是可以從一個BST轉換爲另一種使用旋轉。我們將證明給定任意兩個由相同n + 1值構成的BST，總能將第一棵樹轉換爲第二棵樹。

要做到這一點，我們首先做一個關鍵的觀察。給定BST中的任何節點，始終可以應用樹輪旋轉將該節點拉到樹的根部。要做到這一點，我們可以把這個算法：

while (target node is not the root) { 
    if (node is a left child) { 
     apply a right rotation to the node and its parent; 
    } else { 
     apply a left rotation to the node and its parent; 
    } 
}

，這是工作的原因，每一個節點都與其父，通過一個其高度增加旋轉時間。因此，在應用了上述形式的足夠多的旋轉之後，我們可以將根到達樹的頂部。

這現在給我們一個非常簡單的遞歸算法，我們可以使用它來將任何一個BST重塑爲另一個使用旋轉的BST。這個想法如下。首先，查看第二個樹的根節點。在第一棵樹中找到該節點（這很容易，因爲它是BST！），然後使用上述算法將其拉到樹的根部。在這一點上，我們已經把第一棵樹成樹具有以下屬性：

第一樹的根節點是第二樹的根節點。
第一棵樹的右側子樹包含與第二棵樹的右側子樹相同的節點，但可能具有不同的形狀。
第一棵樹的左子樹包含與第二棵樹的左子樹相同的節點，但可能具有不同的形狀。

因此，我們可以遞歸地應用相同的算法，使左子樹與第二棵樹的左子樹具有相同的形狀，並使右子樹具有與第二棵樹的右子樹相同的形狀樹。由於這些左右子樹必須每個嚴格不超過n個節點，所以通過我們的歸納假設，我們知道始終可以這樣做，所以算法將按預期工作。

總之，該算法的工作原理如下：

如果兩棵樹是空的，我們正在這樣做。
找到第一棵樹中第二棵樹的根節點。
應用旋轉將該節點置於根。
遞歸地重塑第一棵樹的左側子樹，使其具有與第二棵樹的左側子樹相同的形狀。
遞歸地重塑第一棵樹的右側子樹，使其具有與第二棵樹的右側子樹相同的形狀。

要分析此算法的運行時間，請注意，應用步驟1 - 3最多需要O（h）個步驟，其中h是第一個樹的高度。每個節點都會一次被帶到某個子樹的根部，所以我們總共執行O（n）次。由於n節點樹的高度永遠不會大於O（n），這意味着該算法最多需要花費O（n ）時間才能完成。它可能會做得更好（例如，如果這兩棵樹已經具有相同的形狀，那麼這在時間O（n）中運行），但是這給出了很好的最壞情況界限。

希望這會有所幫助！

來源

2012-12-25 04:37:17 templatetypedef

考慮刪除「你」的主義。 – 2012-12-25 04:45:40

你可以在線性時間內做到這一點......見https://stackoverflow.com/questions/19625325/binary-tree-transformation-using-rotations。 –

對於二叉搜索樹，這實際上可以在O（n）中完成。

任何樹都可以「理順」，即放入一種形式，其中所有節點都是根或者左邊的孩子。

這種形式是唯一的（從根讀下來給人的元素的順序）

樹是理順如下：

對於任何權利的孩子，進行約本身就是一個左旋轉。這減少了的右邊兒童的數量，所以樹在O（n）旋轉中被理順。

如果A可以理順成S個在爲O（n）旋轉，和B爲S在爲O（n）旋轉，則由於旋轉是可逆一個可以把A - >的S - > B在O（n）旋轉。

來源

2018-01-30 23:00:15

是否總是有可能使用樹輪旋轉將一個BST變成另一個BST？

回答

相關問題