テクノロジ系 / アルゴリズムとプログラミング
AVL 木
AVL木は、左右の部分木の高さの差を一定範囲に保つ自己平衡2分探索木です。
もう少し詳しく
挿入や削除で木の高さが偏った場合、回転操作によってバランスを取り戻します。通常の2分探索木が偏ると探索効率が悪化するため、それを防ぐための構造です。
試験での見方
例：昇順に1,2,3を挿入して右に偏った場合、回転により2を根にして高さを整えます。
テクノロジ系 / アルゴリズムとプログラミング
AVL木は、左右の部分木の高さの差を一定範囲に保つ自己平衡2分探索木です。
挿入や削除で木の高さが偏った場合、回転操作によってバランスを取り戻します。通常の2分探索木が偏ると探索効率が悪化するため、それを防ぐための構造です。
例：昇順に1,2,3を挿入して右に偏った場合、回転により2を根にして高さを整えます。
AVL木では、探索木の大小関係に加えて、高さの差を調整する点を押さえます。問題で「回転」「平衡」「高さ差」が出たらAVL木を意識しましょう。