AVL Treeとは？

AVL木のすべてのノードは、自身の高さ（葉までの最長パスにあるエッジの数）を保持します。葉の高さは 1 であり、空のサブツリーの高さは 0 とカウントされます。ノードの2つの子の高さから、そのノードの平衡係数（height(left) - height(right)）を計算できます。

平衡係数が -1、0、または 1 のとき、そのノードは平衡状態です。AVL木のルールは単純です。すべてのノードが常に平衡状態を保たなければなりません。挿入や削除によってノードの平衡係数が 2 または -2 になると、木は回転を実行します。これは、探索木の順序を壊すことなく、定数時間で平衡を回復させるための、いくつかのポインタの局所的な再配置です。

回転には4つのケース（左-左、右-右、左-右、右-左）がありますが、それらはすべて、単一の左回転と単一の右回転という2つの構成要素に集約されます。これからの数回のレッスンで、これら両方をゼロから構築していきます。