AVL木の定義とバランスファクタ
AVL木の定義とバランスファクタは、各ノードで左右部分木の高さの差を高々1に保つ二分探索木である。
仕組み
バランスファクタBF(v)=height(left)-height(right)を用い、全ノードでBF∈{-1,0,1}を維持する。挿入・削除で外れた場合は単回転または二重回転で復元する。
計算量・性質
木の高さはO(log n)なので検索・挿入・削除はいずれもO(log n)である。
具体例
30,20,10の順に挿入すると30でBF=2となり、右回転して20を根にする。
限界と注意点
高さ更新や回転の向きを誤ると探索木順序または平衡条件を壊す。