算法
紅黑樹
紅黑樹是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。它是在1972年由Rudolf Bayer發明的，他稱之為"對稱二叉B樹"，它現代的名字是在 Leo J.Guibas 和 Robert Sedgewick 于1978年寫的一篇論文中獲得的。它是複雜的，但它的操作有着良好的最壞情況運行時間，并且在實踐中是高效的: 它可以在O(log n)時間内做查找，插入和删除，這裡的n是樹中元素的數目。
AVL
AVL是最先發明的自平衡二叉查找樹算法。在AVL中任何節點的兩個兒子子樹的高度最大差别為一，所以它也被稱為高度平衡樹，n個結點的AVL樹最大深度約1.44log2n。查找、插入和删除在平均和最壞情況下都是O（log n）。增加和删除可能需要通過一次或多次樹旋轉來重新平衡這個樹。
Treap
Treap是一棵二叉排序樹，它的左子樹和右子樹分别是一個Treap，和一般的二叉排序樹不同的是，Treap紀錄一個額外的數據，就是優先級。Treap在以關鍵碼構成二叉排序樹的同時，還滿足堆的性質(在這裡我們假設節點的優先級大于該節點的孩子的優先級)。但是這裡要注意的是Treap和二叉堆有一點不同，就是二叉堆必須是完全二叉樹，而Treap并不一定是。
伸展樹
伸展樹（Splay Tree）是一種二叉排序樹，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan創造。它的優勢在于不需要記錄用于平衡樹的冗餘信息。在伸展樹上的一般操作都基于伸展操作。
SBT
Size Balanced Tree（簡稱SBT）是一自平衡二叉查找樹，是在計算機科學中用到的一種數據結構。它是由中國廣東中山紀念中學的陳啟峰發明的。陳啟峰于2006年底完成論文《Size Balanced Tree》，并在2007年的全國青少年信息學奧林匹克競賽冬令營中發表。由于SBT的拼寫很容易找到中文諧音，它常被中國的信息學競賽選手和ACM/ICPC選手們戲稱為“傻B樹”、“Super BT”等。相比紅黑樹、AVL樹等自平衡二叉查找樹，SBT更易于實現。
據陳啟峰在論文中稱，SBT是“目前為止速度最快的高級二叉搜索樹”。SBT能在O(log n)的時間内完成所有二叉搜索樹（BST）的相關操作，而與普通二叉搜索樹相比，SBT僅僅加入了簡潔的核心操作Maintain。由于SBT賴以保持平衡的是size域而不是其他“無用”的域，它可以很方便地實現動态順序統計中的select和rank操作。
作用
對于一般的二叉搜索樹（Binary Search Tree），其期望高度（即為一棵平衡樹時）為log2n，其各操作的時間複雜度（O(log2n)）同時也由此而決定。但是，在某些極端的情況下（如在插入的序列是有序的時），二叉搜索樹将退化成近似鍊或鍊，此時，其操作的時間複雜度将退化成線性的，即O(n)。
可以通過随機化建立二叉搜索樹來盡量的避免這種情況，但是在進行了多次的操作之後，由于在删除時，我們總是選擇将待删除節點的後繼代替它本身，這樣就會造成總是右邊的節點數目減少，以至于樹向左偏沉。這同時也會造成樹的平衡性受到破壞，提高它的操作的時間複雜度。
平衡二叉搜索樹（Balanced Binary Tree）具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。常用算法有紅黑樹、AVL、Treap、伸展樹等。在平衡二叉搜索樹中，我們可以看到，其高度一般都良好地維持在O（log（n）），大大降低了操作的時間複雜度。
