紅黑樹和平衡二元樹的區別 紅黑樹和平衡二元樹的區別是什麼

紅黑樹和平衡二元樹的區別：

紅黑樹放棄了追求完全平衡，追求大致平衡，在與平衡二元樹的時間複雜度相差不大的情況下，保證每次插入最多隻需要三次旋轉就能達到平衡，實現起來也更為簡單。平衡二元樹追求絕對平衡，條件比較苛刻，實現起來比較麻煩，每次插入新節點之後需要旋轉的次數不能預知。

紅黑樹

紅黑樹是一種特定型別的二元樹，是在電腦科學中用到的一種資料結構，典型的用途是實現關聯陣列。它是在1972年由RudolfBayer發明的，他稱之為"對稱二叉B樹"，它現代的名字是在as和RobertSedgewick於1978年寫的一篇論文中獲得的。它是複雜的，但它的操作有著良好的最壞情況執行時間，並且在實踐中是高效的，它可以在O(logn)時間內做查詢，插入和刪除，這裡的n是樹中元素的數目。

平衡二元樹

平衡二叉搜尋樹（Self-balancing binary search tree）又被稱為AVL樹（有別於AVL演算法），且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二元樹。平衡二元樹的常用實現方法有紅黑樹、AVL、替罪羊樹、Treap、伸展樹等。最小二叉平衡樹的節點總數的公式如下F(n)=F(n-1)+F(n-2)+1這個類似於一個遞迴的數列，可以參考Fibonacci(斐波那契)數列，1是根節點，F(n-1)是左子樹的節點數量，F(n-2)是右子樹的節點數量。