1,AVL樹
在計算機科學中,AVL樹是最早的自平衡二叉查找樹。在AVL樹中,任意節點對應的兩個子樹之間的最大高度差為1,因此也稱為高度平衡樹。
查找、插入和刪除的時間復雜度處於平均水平和最壞情況。添加和刪除元素可能需要壹次或多次樹旋轉來重新平衡樹。
節點的平衡因子是其左側子樹的高度減去其右側子樹的高度(有時相反)。平衡系數為1、0或-1的節點被視為平衡節點。平衡因子為-2或2的節點被認為是不平衡的,需要重新平衡樹。平衡因子可以直接存儲在每個節點中,或者根據可能存儲在節點中的子樹高度來計算。?
2.紅色和黑色的樹
紅黑樹(英文:Red-black tree)是壹種自平衡二叉查找樹,是計算機科學中使用的數據結構,其典型用途是實現關聯數組。它是由魯道夫·貝爾在1972年發明的,他稱之為“對稱二元B樹”。
3、治療
樹堆(英文:Treap)是壹個具有滿足堆屬性的隨機附加字段的二叉查找樹,其結構相當於壹個插入隨機數據的二叉查找樹。與其他平衡二分搜索法樹相比,Treap的特點是實現簡單,基本上可以實現隨機平衡的結構。
4.節點大小平衡樹
節點大小平衡樹(SBT)是陳奇峰發明的自平衡二叉查找樹,是計算機科學中使用的數據結構。