樹與層次結構
二元搜尋樹
二元搜尋樹是一棵多出一條承諾、從而變得可搜尋的二元樹：對每個節點而言，它左子樹中的所有鍵都比該節點的鍵小，右子樹中的所有鍵都比它大。這條排序不變式在每個節點、一直到底都成立。它就是有序陣列在樹形上的表親。
僅憑這一條規則，你就能像玩「猜大小」遊戲一樣找鍵。從根出發；如果目標更小就往左，更大就往右，直到命中或走到底端為止。每一步都丟掉整整一棵子樹，所以當樹平衡時，你每次都把候選範圍減半，於是搜尋、插入或刪除的開銷都是 O(log n)。按「左、自身、右」的順序走訪這棵樹，甚至能免費地把鍵按升序讀出來。
問題在於：這種速度完全依賴於樹保持枝繁葉茂。如果你把已經排好序的資料插入一棵普通的二元搜尋樹，每個新鍵都比上一個大，樹就會長成一條又長又細的單枝——也就是退化樹——搜尋隨即跌回 O(n)，並不比掃一遍串列更快。正是這種脆弱催生了平衡搜尋樹：它們在插入時多做一些工作，無論資料以什麼順序到來，都把樹高維持在接近 log n。
Node* find(Node* root, int key) {
while (root != nullptr) {
if (key == root->value) return root;
root = (key < root->value) ? root->left
: root->right;
}
return nullptr; // not found
}迭代式二元搜尋樹搜尋——樹平衡時為 O(log n)。
平衡的二元搜尋樹搜尋為 O(log n)；退化成藤蔓狀的二元搜尋樹則跌到 O(n)——不變式只保證順序，不保證形狀。
又稱
另見