連接/合併/連接兩棵AVL樹

假設我有兩棵AVL樹，第一棵樹的每個元素都小於第二棵樹的任何元素。將它們連接成一個AVL樹最有效的方法是什麼？我到處搜索，但沒有發現任何有用的東西。連接/合併/連接兩棵AVL樹

來源

2010-01-10 liviucmg

謝謝篦問題的高度，但我認爲它更適合：https：//開頭CS .stackexchange.com/ – ChaosPredictor 2018-02-12 18:19:12

假設你可能會破壞輸入樹：

刪除最右邊的元素左樹，並用它來建立一個新的根節點，它的左子是左樹，其右孩子右邊的樹：O（log n）
確定並設置該節點的平衡因子：O（log n）。在（臨時）違反不變量的情況下，平衡因子可能會超出範圍{O，O，O，}旋轉：O（log n）旋轉以使平衡因子回到範圍內：{-1,0,1}
旋轉：

因此，整個操作可以在O（log n）中執行。

編輯：關於第二個想法，在以下算法中更容易推理旋轉。它也很可能更快：

確定兩棵樹的高度：O（log n）。
假設右邊的樹較高（另一種情況是對稱的）：
從left樹中移除最右邊的元素（如果需要，旋轉並調整其計算的高度）。讓n是那個元素。 O（log n）
在右側樹中，向左導航，直到到達子樹最多比left高1的節點。假設r是該節點。 O（log n）
將該節點替換爲值爲n的新節點，以及子樹left和r。 O（1）
通過構建，新節點是AVL平衡的，其子樹1高於r。
相應地增加其父母的餘額。 O（1）
和重新平衡就像插入後一樣。 O（log n）的

來源

2010-01-10 14:50:20 meriton

你確定嗎？（你可能很容易就是正確的，但我只是好奇而已。）假設左邊的樹比右邊的樹要小得多，也就是淺得多。爲什麼O（log n）旋轉恢復AVL屬性？你如何決定在哪裏旋轉？ – 2010-01-10 14:57:45

Dale說道：通常選擇AVL樹的旋轉角度，可以用O（log n）旋轉將尺寸2的不平衡糾正回範圍[-1,1]。你需要一個新的方案來選擇旋轉以糾正任意的不平衡。由於這是AVL樹的一部分，我永遠不會記住，並且每次都必須查看，所以我期望即使旋轉的選擇很明顯，對我來說也不是顯而易見的:-) – 2010-01-10 15:21:50

好點。我發現更容易證明另一種算法（參見我的編輯答案）。 – meriton 2010-01-10 16:36:08

我懷疑你只需要走一棵樹（希望是較小的），並將其中的每個元素分別添加到其他樹中。 AVL插入/刪除操作並不旨在處理一次添加整個子樹。

來源

2010-01-10 14:12:53

我有一種感覺，它可以線性完成。使用天真的方法需要O（n log n）時間。 – avakar 2010-01-10 14:27:06

這需要O（n log n） - >遠遠低於meriton的解決方案 – inspectorG4dget 2010-02-12 15:45:57

@ meriton的解決方案確實非常好，但它假設（a）一棵樹中的每個節點嚴格小於另一棵樹中的每個節點，（b ）您可以訪問原始的avl樹數據結構，並且（c）可以直接在樹節點上執行旋轉。如果（a）不成立，或者低級樹操作不可用（最有可能是因爲您正在使用avl庫），那麼您可能不得不簡單地將小樹中的每個節點插入更大。 – 2010-02-13 04:15:07

一個超簡單的解決方案（即沒有在樹與樹之間的關係做任何假設的作品）是這樣的：

做一個合併排序兩棵樹到一個合併陣列（兼迭代兩棵樹）。
從數組中構建AVL樹 - 以中間元素爲根，並遞歸應用於左右兩半。

這兩個步驟都是O（n）。它的主要問題是需要O（n）個額外的空間。

來源

2011-01-17 21:15:01 ripper234

是不是第一步O（n log（n））？ – stendarr 2017-12-09 17:38:11

我讀到這個問題的最佳解決方案可以找到here。

在算法的第三一步導航離開，直到達到其子樹具有相同的高度，左樹節點：如果你解決這個問題是非常接近meriton的答案。這並非總是可行，（請參閱反例圖片）。做到這一步正確的方法是二找到與高度h或h+1子樹，其中h是左樹

來源

2014-10-29 18:29:12 agarwaen

連接/合併/連接兩棵AVL樹

回答

相關問題