平衡二分探索木とは
平衡二分探索木とは、データを効率よく検索するための「ツリー構造（木構造）」の一種で、左右の枝のバランス（高さ）が常にほぼ均等に保たれるように自動的に調整されるデータ構造です。「AVL木」や「赤黒木」などが有名です。
通常の二分探索木は、データを追加していく順番によっては、枝が片側だけに偏って長く伸びてしまい、データを検索する効率が著しく低下して単なるリストのようになってしまう欠点があります。平衡二分探索木では、データを追加・削除するたびに、ツリーの左右のバランスが崩れていないかをチェックし、崩れそうになったら構造を回転（ローテーション）させて高さを均等に保ちます。これにより、データ量が膨大になっても常に高速な検索性能（O(log N)）を維持できます。
具体例
「1, 2, 3, 4, 5」という順番でデータを追加する場合、通常の二分探索木だと右側に一本道で繋がってしまいますが、平衡二分探索木では、3を追加した時点で真ん中の「2」を親（根）にし、4や5を追加した際にも自動的にツリーのバランスを組み替えて、ピラミッドのような左右対称に近い形を維持します。
もう少し詳しく
平衡二分探索木のバランス維持メカニズムの中で、特に重要なのが「ローテーション（回転）」操作です。ローテーションには、左回転（左単回転）、右回転（右単回転）、およびそれらを組み合わせた複回転（左右回転、右左回転）があります。代表的な平衡二分探索木である「AVL木」では、各ノードの「左右のサブツリーの高さの差（平衡係数）」が常に1以下になるよう厳密に管理します。データが追加・削除されて高さの差が2になった瞬間、ローテーションを行って親子の関係をパズルのように架け替えます。もう一つの代表格である「赤黒木（レッドブラックツリー）」は、ノードを赤または黒のルールで着色し、AVL木よりもやや緩やかにバランスを保ちます。これにより、検索速度はAVL木に一歩譲るものの、データの追加や削除時の回転コストを低く抑えられるため、実用的なライブラリ（C++のstd::mapやJavaのTreeMapなど）で広く使われています。
試験でのポイント
試験では、平衡二分探索木を維持するための「ノードの回転（ローテーション）」の手順が具体的に出題されます。特に、特定の二分探索木に新しいノードを追加した際に、どのノードを中心に右または左へ回転させるかを視覚的に選ばせる問題が頻出します。各ノードの左側にはそのノードより小さい値、右側には大きい値が配置されるという「二分探索木」の基本ルールを維持したまま、高さを低くするために親と子の位置関係を入れ替える操作ロジックをマスターしておきましょう。また、バランスが崩れた最悪の二分探索木の計算量が「O(N)」に劣化するのに対し、平衡二分探索木では常に「O(log N)」が保証される性能上の利点についても問われます。
関連する用語
平衡二分探索木に関連するデータ構造としては、左右の高さの差を厳密に管理する「AVL木」や、挿入・削除の負荷が低い「赤黒木」があります。また、ノードの回転を行う「ローテーション」操作や、データベースのインデックスなどに使われ、ノードが3つ以上の子を持けるように拡張された「B木（B-Tree）」や「B+木（B+ Tree）」も、高度なデータ構造として密接に関連しています。