平衡木とは？

平衡木とは、挿入や削除のたびに木の形を整え直し、左右の高さの差が一定以内に保たれるようにした探索木。代表がAVL木で、左右の部分木の高さの差を1以内に保つ。高さがlog n程度に抑えられるため、最悪でもO(log n)の探索性能が保証される。

へいこうぎ

基本情報技術者試験の頻出用語／テクノロジ系

平衡木の意味

挿入や削除のたびに木の形を整え直し、左右の高さの差が一定以内に保たれるようにした探索木。代表がAVL木で、左右の部分木の高さの差を1以内に保つ。高さがlog n程度に抑えられるため、最悪でもO(log n)の探索性能が保証される。

AVL木で挿入により左右の高さの差が2になったら、節を回転させて平衡を回復する。例えば右へ一直線に3つ伸びた形は、真ん中の節を新しい根に持ち上げる回転で高さ1の均等な形に直せる。この回転は定数時間で終わる。

平衡化のぶん挿入・削除の手間は増えるので、更新が非常に多い用途では必ずしも得ではない。また「平衡＝完全二分木」ではなく、AVL木は左右の高さ差1まで許す点が異なる。B木も平衡を保つ木の一種。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。