二分探索木 の記事

二分探索木と平衡二分探索木 入門 - AVL木・赤黒木がなぜ必要かを実装で理解する

二分探索木（BST）と、その平衡版であるAVL木・赤黒木を解説します。左部分木は小さく右部分木は大きいという不変条件、探索・挿入・削除（子なし/子1つ/子2つの3ケース）の実装、中順走査でソート順に取り出せる性質、昇順データを入れると高さが n-1 まで退化する最悪ケースの実測、左回転と右回転、AVL木の平衡因子とLL/LR/RR/RLの4ケース、赤黒木の5つの性質と高さの上界、C++のstd::mapやJavaのTreeMap・Linuxカーネルのrbtreeといった実務での使われ方まで、実際に動かして確認したPythonコードで整理します。