二分木

派生には、二分探索木(BST、整列順を保つ)、ヒープ(親が子の最大値または最小値)、平衡木(AVL、赤黒木。高さが保証される)、トライ木、セグメント木、フェニック木などがある。走査は、通りがけ順・行きがけ順・帰りがけ順・幅優先(BFS)。

平衡していない BST は連結リストに退化し、操作が O(n) になりうる。本番では平衡木を使うこと(各言語の TreeMap は赤黒木である)。