APアルゴリズムとプログラミング · データ構造

AVL木

AVL Tree

えーぶいえるき

各ノードの左右部分木の高さの差が1以下に保たれる平衡2分探索木。挿入・削除時に回転操作（単回転・二重回転）でバランスを維持し、最悪ケースでもO(log n)の探索時間を保証する。

共有:

他の資格での定義

任意のノードにおいて左右の部分木の高さの差が1以下であることを保証する自己平衡2分探索木。挿入・削除時に回転操作でバランスを保つため、最悪でもO(log n)の探索性能を維持する。

どの節でも左右の部分木の高さの差が1以下になるように保つ2分探索木。挿入や削除で条件が崩れると、回転と呼ぶ操作で形を直すため、探索、挿入、削除をO(log n)で行える。

Past Exams

過去問で 1 回出題（応用情報技術者試験 1）。うち 1 回は用語そのものを問う問題です。

出典: 独立行政法人情報処理推進機構（IPA）の過去問題。問題文は IPA のサイトの PDF で確認できます。「用語を問う問題」は、この用語の説明や特徴そのものを問う問題です。用語名で照合しているため、関係の薄い問題が含まれることがあります。

各ノードが最大2つの子ノードを持つ木構造。完全2分木は最下段以外の全階層が埋まった構造。2分探索木は左の子が親より小さく右の子が親より大きい性質を持ち、探索・挿入・削除をO(log n)で実行可能。

1ノードに複数のキーと子ポインタを持つ多分木構造の平衡探索木。ディスクアクセスの回数を最小化するよう設計され、データベースのインデックスやファイルシステムで広く使用される。全葉が同じ深さにある。

親ノードの値が子ノードの値以上（最大ヒープ）または以下（最小ヒープ）の条件を満たす完全2分木。優先度付きキューの実装に使われ、ヒープソートの基盤となる。挿入・削除はO(log n)で実行可能。

左の子ノードの値が親より小さく、右の子ノードの値が親より大きいという条件を満たす2分木。探索・挿入・削除の平均計算量がO(log n)で効率的。バランスが崩れるとO(n)に悪化する。

根から下の階層まで隙間なく節が詰まり、最下層だけ左詰めになっている2分木。高さがlog nに抑えられるので処理が効率的で、配列だけで親子関係を表現できる。ヒープはこの形を利用している。

どの葉までの深さもほぼ等しくなるように保たれた木。木が一方に偏ると探索が遅くなるため、挿入・削除のたびに形を整え直す。AVL木やB木が代表例で、探索時間をO(log n)に保てる。