當元素按順序插入時保持二叉樹平衡

Question

我想知道是否有合適的算法來維持二叉樹的平衡，當知道元素總是按照順序插入。

對此的一種選擇是使用標準方法從排序後的數組或鏈接列表中創建平衡樹，如this問題中討論的，還有this其他問題。但是，我希望有一種方法可以將少量元素插入樹中，然後對其執行查找，然後再添加其他元素，而不必將樹分解爲列表並重新制作整個事物。

另一種選擇是使用許多自平衡樹實現之一，AVL，AA，紅黑等等。但是，所有這些都在插入過程中施加了某種開銷，並且我想知道是否有一種方法可以避免這種情況，因爲限制因素是總是以增加的順序插入。因此，爲了清楚起見，我想知道是否有一種方法可以維護平衡的二叉樹，這樣我就可以在任何點插入一個任意的新元素並保持樹的平衡，假定樹的排序中的新元素大於全部元素已存在於樹中。

舉個例子，假設我有以下三種：

 4 
    /\ 
    / \ 
    2  6 
/\ /\ 
    1 3 5 7 

有沒有一種簡單的方法插入一個新的元素時保持平衡，如果我知道元素將是大於7？

Answer 1

如果你在使用BST（我想這是不是最好的選擇，因爲你可以在我的其他復讀）做這件事真的很感興趣，你可以做這樣的：

有正常的BST 。這意味着查找是O（log N），如果我們設法在插入期間保持深度。

在做插入操作時（假設我們有一個比以前所有元素大的元素），你從根節點走到最右邊的元素。當你遇到一個節點，其子樹是一個完美的二叉樹（所有內部節點有2個子節點，並且所有節點都處於相同的深度）時，可以插入新節點作爲此節點的父節點。

如果您到達樹中最右側的節點，並且您沒有應用先前的規則，那意味着它有一個左孩子，但它沒有正確的孩子。所以，新節點成爲當前節點的正確子節點。

例如，在下面的第一棵樹中，4的子樹並不完美，但5的子樹是（只有一個節點的樹是完美的定義）。所以，我們添加6作爲5的父親，這意味着4是6的父親，5是6的左孩子。

如果我們嘗試添加另一個節點，那麼4的子樹仍然不完美，既不是6和6之一是最右邊的節點，所以我們加7的6

 4    4    4 
    /\   /\   /\ 
/ \  / \  / \ 
    2  5 --> 2  6 --> 2  6 
/\   /\ / /\ /\ 
1 3   1 3 5  1 3 5 7 

右孩子。如果我們使用這種算法，根的左子的子樹將永遠是完美的，正確的孩子的子樹將永遠不會比左側的高。因此，整棵樹的高度將始終爲O（log N），查找時間也是如此。插入也將花費O（log N）時間。

與自平衡BSTs相比，時間複雜性是相同的。但是這個算法應該更容易實現，可能實際上比他們更快。

與我的其他答案的基於陣列的解決方案相比，查找的時間複雜度是相同的，但是這個BST插入時間更差。

Answer 2

我假設你知道先驗元素是按照遞增的順序出現的。此外，我想你想要一棵樹來快速搜索一個特定的元素。

我不確定二進制樹是否最適合快速插入，就像您描述的一樣。但是可能有其他的數據結構可以很好地處理你描述的用例：Allthough我從來沒有用過它，我想起了一個skip-list。既然你總是插入大於已經在集合中的所有元素的元素，應該很容易更新指針。

Answer 3

對於您描述的要求，根本不需要樹。有排序的dynamic array是你所需要的。

插入時，總是在末尾插入（O（1）攤銷）。

搜索時，使用正常的binary search（O（log N））。

這假設你不需要任何其他操作，或者你不介意他們將是O（N）。