AVL木とは

AVL木とは、平衡二分探索木の一種で、どのノードでも左右の部分木の高さの差が1以下になるように保たれる二分探索木である。挿入や削除で差が2になったら回転操作で釣り合いを戻すため、探索・挿入・削除の計算量が常にO(log n)に抑えられる。