樹與層次結構
平衡樹
平衡樹是一種會主動讓自己保持低矮、絕不退化成長藤的搜尋樹。它的動機正是普通二元搜尋樹的弱點：餵給它有序資料，它就會跌到 O(n)。平衡樹額外加上一條把樹高限制在約 log n 的規則，於是無論鍵以什麼順序到來，搜尋、插入和刪除都被鎖定在 O(log n)。
兩種著名的設計能說明這個思路。AVL 樹要求每個節點左右子樹的高度相差不超過一——很嚴格，所以它非常矮、搜尋很快。紅黑樹則給節點染上紅色或黑色，施加較寬鬆的規則，仍把樹高約束在 2·log n 左右——稍高一些，但維護更便宜，這也是許多標準函式庫的有序映射和集合都以它為底層的原因。兩者都在每個節點裡多存一點記帳資訊（高度或顏色）。
當一次插入或刪除使樹失去平衡時，就用旋轉來修復：這是一種小而局部的重排，讓某個節點與它的子節點互換支點，重新分配子樹、降低樹高，同時不破壞「左小右大」的排序。一次旋轉只動幾個指標，因此是 O(1)；而沿著回到根的路徑上你最多只需 O(log n) 次旋轉——整個結構正是這樣才能廉價地保持平衡。
// x y
// / \ / \
// y C --> A x
// / \ / \
// A B B C
Node* rotateRight(Node* x) {
Node* y = x->left;
x->left = y->right;
y->right = x;
return y; // y is the new subtree root
}一次單右旋——保持搜尋樹平衡的 O(1) 局部修復。
AVL 樹更矮（查找更快）；紅黑樹重平衡時旋轉更少（更新更快）——兩者都保證 O(log n)。
又稱
另見