AVL木
参考ページ
特徴
二分探索木の一種である
強平衡二分木の一種である
値の挿入・削除・検索をすべて$ O(logN)で行う
ただし、定数部分は重め（らしい）
クエリ処理後に木を回転させることで、木の平衡を維持する AVL木とヒープの使い分け例
値の検索が必要：AVL木を使う
値の検索が不要：
最大値（最小値）の取得が必要：ヒープを使う
最大値（最小値）の取得が不要：（どちらかというと）ヒープを使う
定義
各頂点$ vがキーと呼ばれる値$ key\lbrack v \rbrackをもつ
強平衡二分木である
木の高さを$ hとしたとき、木の深さ$ h-1の部分については、完全二分木を形成している
二分探索木である
任意の頂点$ vの値が$ vの左子孫の最大値以上で、$ vの右子孫の最小値以下である
$ vの左部分木に含まれるすべての頂点$ v'に対して$ key \lbrack v \rbrack \geq key \lbrack v' \rbrackが成り立つ
$ vの右部分木に含まれるすべての頂点$ v'に対して$ key \lbrack v \rbrack \leq key \lbrack v' \rbrackが成り立つ
構造
クエリ処理時の具体的な挙動
AVL木の構築について