平衡木とは？へいこうぎ
平衡木とは、挿入や削除のたびに木の形を整え直し、左右の高さの差が一定以内に保たれるようにした探索木（データを値の大小で左右に振り分けて置き、値を比べながらたどって探す木）。代表がAVL木で、どの節（データを置く点）でも、その下に左右に伸びる枝の部分（部分木）の高さの差を1以内に保つ。木の高さがlog n程度（データ数nに対し、2を何回掛けるとnになるかという回数程度）に抑えられるため、データが増えても探索の手間はゆっくりしか増えない。最悪でもO(log n)（探索の手間が木の高さ程度で済むこと）の探索性能が保証される。赤黒木も代表的な平衡木である。
最終更新：2026-10-09
基本情報を最短で暗記・合格する →具体例
AVL木で挿入により左右の高さの差が2になったら、節を回転させて平衡を回復する。例えば右へ一直線に3つ伸びた形は、真ん中の節を新しい根（木のいちばん上の節）に持ち上げる回転で、左右に1つずつ子を持つ高さ1の均等な形に直せる。この回転は定数時間（データ数に関係なく一定の手間）で終わる。
試験での引っ掛け
平衡化のぶん挿入・削除の手間は増えるので、更新が非常に多い用途では必ずしも得ではない。また「平衡＝完全二分木（最下段を除くすべての段が埋まった2分木）」ではなく、AVL木は左右の高さ差1まで許す点が異なる。B木も平衡を保つ木の一種。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。