隨機插入二叉搜索樹vs紅黑樹

Question

我已經閱讀了紅黑樹，我明白他們試圖解決樹變得不平衡的問題。但是，如果您要使用隨機插入。例如：

考慮以下是需要插入排序號：

1,2,3,4,5,6,7,8,9,10

如果我們天真地插入一個BST樹將如下所示： ..

在這種情況下，樹將是超級不平衡，並且搜索將是線性O（N）

然而，如果瓦特e隨機插入，它可能看起來更平衡（但在平均情況下可能不平衡爲紅黑樹）。如果我們使用紅色的黑色樹木，它將保證接近均衡的BST，但會帶來一些開銷。什麼時候一個平局希望這種額外的開銷效率的線Vs使用除了用於「在線算法」（self balancing binary search trees）

Answer 1

使用AVL樹平衡隨機插入BST .. AVL樹是一個平衡樹，這是第一個被髮明的數據結構。 1在AVL樹中，任意節點的兩個子子樹的高度最多相差一個;如果在任何時候它們相差多於一個，則重新平衡以恢復這個屬性。在平均和最差情況下，查找，插入和刪除都需要O（log n）時間，其中n是操作之前樹中節點的數量。插入和刪除可能需要通過一個或多個樹輪旋轉來重新平衡樹。

維基百科有一篇文章here。

Answer 2

有這樣的路線。你一直記得使用任何類型的動態數據結構（如BST和紅黑樹）的動機。動機非常簡單 - 保持數據的某種形式（在BST的情況下命令）。所以，如果你不想保持它可能會使用類似排序的數組。數組排序可以在O(n log n)上完成。你可以在固定時間內使用排序數據（如min/max/nth）做任何事情！這是極快的！但是，如果您計劃將新值添加到已排序的數組中，該怎麼辦？這是事情變得有趣的地方。所以，你必須轉移你的數組，並在適當的位置插入一個新的值。它需要O(n)。這聽起來不像一個正確的方法。但是，好消息。在O(log n)時間有樹可以處理插入和刪除。

那麼線怎麼樣。我會說。如果您計劃只將新元素插入樹中。輸入值是隨機的。所以，BST完全可以完成這項任務。但是，如果您打算做一些移除操作，那麼您應該使用新的自平衡樹，如RBTree，因爲BST由於移除而不平衡（BST上的移除操作是非對稱的，並生成高度爲sqrt(n)的樹）。

還有第三種情況。您可以嘗試找到BST的對稱刪除算法（stil未解決50年），併成爲計算機科學的搖滾明星。與這些東西的Goog運氣！