テクノロジ
AVL木とは
読み方：エーブイエルぎ
ひとことで言うと：左右部分木の高さ差を調整し、自動的に平衡を保つ二分探索木。
意味をわかりやすく解説
AVL木は、各ノードで左部分木と右部分木の高さの差を一定範囲に保つ、自己平衡型の二分探索木です。
挿入や削除でバランスが崩れると回転操作で木を組み替えます。高さをO(log n)に保ちやすいため、探索・挿入・削除の性能を安定させられます。
具体例
昇順に値を挿入して右へ偏った場合、部分木を左回転して高さ差を小さくします。
似た用語との違い
覚え方
AVL＝偏ったら回転してバランスを戻す二分探索木。
基本情報技術者試験の試験ポイント
平衡係数と回転の目的、木の高さを抑えることでO(log n)の探索性能を保つ点を押さえます。
CHECK QUESTION
AVL木で挿入後に回転操作を行う目的は何ですか。
答えを見る
左右部分木の高さの偏りを修正し、木の高さを低く保って探索効率を維持するためです。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。