關於平衡二叉搜索樹的比較

Question

我讀過一些Q &關於自平衡二叉樹，但我並不十分熟悉它們。

我知道的第一個是AVL，第二個是紅黑樹。

有些東西我不太明白：根據一些書籍和文章，AVL可以執行比紅黑樹快一點的搜索，好吧，這是可以理解的。

1. 那麼什麼是紅黑樹對AVL的優勢？

2. 在AVL中，可能在每次插入之後，我們必須檢查平衡，但在紅黑樹中我們不必經常這樣做，對吧？

PS： 我搜索了類似的東西，但我沒有得到滿意的答案。 希望有些朋友可以給我一個自平衡樹木的詳細比較。

Answer 1

AVL樹具有以下性質：從每個節點，在左側的高度和差的右子樹是至多2

在紅黑樹，在另一方面，該高度的任何節點的左邊或右邊的子樹最多是兩倍另一棵樹的高度。也就是說，它們最多相差2倍。

這直觀地表明，在AVL樹中平均查找確實更快。但是，在插入或刪除一個節點時，我們必須更經常地重新平衡AVL樹，以保持更嚴格的高度不變（另一方面，紅黑樹中的重新平衡在算法上更復雜）。這意味着在實踐中，紅黑樹可能比AVL樹更好，特別是當它經常變化時。