JavaでAVL木クラス作成
新年一発目の記事です。ことよろ（・ω・）ノ
あ、ちょっと都合によりHN変えました。
のでよろしく。
さて、二分探索木シリーズ第三弾。自分の中で「平衡二分木と言ったらコレ！」なイメージがあるAVL木です。多分一番最初に知ったのがこれだったからだと思います。
平衡を保つための平衡条件は
「部分木の高さが左右で2以上崩れたら調整する」
コレだけです。正直、ここまでわかりやすい平衡条件も無いですね。
実現には、各ノードにそこから生える部分木の高さを持たせることも考えたのですが、自分の知ってる「バランス値」管理の方法を採用。
よって各ノードに持たせるデータとコンストラクタは次の通り。
あ、クラス名はAVLTree
public int key; public T value; public AVLTree<T> left; public AVLTree<T> right; public AVLTree<T> parent; public int balance; //コンストラクタ：木を作成 AVLTree(){ this.value = null; this.key = 0; this.left = null; this.right = null; this.parent = null; this.balance = 0; } //コンストラクタ：ノードを作成 AVLTree(int key,T value,AVLTree<T> p){ this.value = value; this.key = key; this.left = null; this.right = null; this.parent = p; this.balance = 0; }
| データ型 | 要素名 | 意味 |
|---|---|---|
| int | key | キー値 |
| T | value | データ |
| BinarySearchTree |
left | 左の子（キー値小） |
| BinarySearchTree |
right | 右の子（キー値大） |
| BinarySearchTree |
parent | 親 |
| int | balance | バランス値 |
バランス値balanceは、右に傾くと+1され、左に傾くと-1されます。ここで「傾く(biased)」とは、右（左）の部分木の高さが増えることを言っています。
このバランス値の絶対値が２より大きければ、次の「再構成」操作を呼ぶ。
//一重回転操作 public void Rotation(){ //キー・データのスワップ int temp_key = this.key; T temp_value = this.value; this.key = this.parent.key; this.value = this.parent.value; this.parent.key = temp_key; this.parent.value = temp_value; //回転 if(this.parent.left == this){ this.parent.left = this.left; if(this.left != null){ this.left.parent = this.parent; } this.left = this.right; this.right = this.parent.right; if(this.right != null){ this.right.parent = this; } this.parent.right = this; }else{ this.parent.right = this.right; if(this.right != null){ this.right.parent = this.parent; } this.right = this.left; this.left = this.parent.left; if(this.left != null){ this.left.parent = this; } this.parent.left = this; } return; } //二重回転操作 public void DoubleRotation(){ //キー・データのスワップ int temp_key = this.key; T temp_value = this.value; this.key = this.parent.parent.key; this.value = this.parent.parent.value; this.parent.parent.key = temp_key; this.parent.parent.value = temp_value; //回転 if(this.parent.right == this){ this.parent.right = this.left; if(this.parent.right != null){ this.parent.right.parent = this.parent; } this.left = this.right; this.right = this.parent.parent.right; if(this.right != null){ this.right.parent = this; } this.parent.parent.right = this; this.parent = this.parent.parent; }else{ this.parent.left = this.right; if(this.parent.left != null){ this.parent.left.parent = this.parent; } this.right = this.left; this.left = this.parent.parent.left; if(this.left != null){ this.left.parent = this; } this.parent.parent.left = this; this.parent = this.parent.parent; } return; } //回転により平衡が保たれるように再構成 public void reconstruct(){ AVLTree<T> cur; AVLTree<T> prev; //平衡が崩れたら回転 if(this.balance < -1){ //左回転 if(this.left.balance < 0){ this.balance = 0; this.left.balance = 0; this.left.Rotation(); //先祖のバランス値を調整 cur = this.parent; prev = this; while(cur != null){ if(cur.left == prev){ cur.balance++; if(cur.balance > 0)break; }else{ cur.balance--; if(cur.balance < 0)break; } prev = cur; cur = cur.parent; } }else if(this.left.balance > 0){ if(this.left.right.balance == 0){ this.left.right.balance = 0; this.left.balance = 0; }else if(this.left.right.balance < 0){ this.left.right.balance = 1; this.left.balance = 0; }else{ this.left.right.balance = 0; this.left.balance = -1; } this.balance = 0; this.left.right.DoubleRotation(); //先祖のバランス値を調整 cur = this.parent; prev = this; while(cur != null){ if(cur.left == prev){ cur.balance++; if(cur.balance > 0)break; }else{ cur.balance--; if(cur.balance < 0)break; } prev = cur; cur = cur.parent; } }else{ this.left.balance = -1; this.left.right.balance = 0; this.balance = -1; this.left.right.DoubleRotation(); } }else if(this.balance > 1){ //右回転 if(this.right.balance > 0){ this.balance = 0; this.right.balance = 0; this.right.Rotation(); //先祖のバランス値を調整 cur = this.parent; prev = this; while(cur != null){ if(cur.left == prev){ cur.balance++; if(cur.balance > 0)break; }else{ cur.balance--; if(cur.balance < 0)break; } prev = cur; cur = cur.parent; } }else if(this.right.balance < 0){ if(this.right.left.balance == 0){ this.right.left.balance = 0; this.right.balance = 0; }else if(this.right.left.balance < 0){ this.right.left.balance = 0; this.right.balance = 1; }else{ this.right.left.balance = -1; this.right.balance = 0; } this.balance = 0; this.right.left.DoubleRotation(); //先祖のバランス値を調整 cur = this.parent; prev = this; while(cur != null){ if(cur.left == prev){ cur.balance++; if(cur.balance > 0)break; }else{ cur.balance--; if(cur.balance < 0)break; } prev = cur; cur = cur.parent; } }else{ this.right.balance = 1; this.right.left.balance = 0; this.balance = 1; this.left.right.DoubleRotation(); } } //根までボトムアップ式に再帰 if(this.parent != null)this.parent.reconstruct(); return; }
一重回転・二重回転は、実は前記事「スプレイ木」のzig操作、zig-zag操作と同じです。詳しくはめんどいので割愛（あとで解説追加するかも）
reconstructは、それらを適切な場所（バランス値が修正されるような場所）に適用することで、バランスをとる。ボトムアップ式に再帰するので、例えば一つのノードの挿入で一気にバランスが崩れてもすべて調整してくれます。
「バランス値を調整」は下に説明があります。
この「再構成」は、挿入・削除の最後に実行し、挿入、削除そのものによるバランス値の調整は各操作で別々に行います。
と、言うわけで、以下基本操作３種類。
//木に挿入 public void insert(int key,T value){ AVLTree<T> cur,prev; if(this.parent == null && this.value == null){ //根が空の場合 this.value = value; this.key = key; return; }else if(this.key > key){ //左に挿入 if(this.left == null){ //左に子がない this.left = new AVLTree<T>(key,value,this); if(this.right == null){ //先祖のバランス値を調整 prev = this.left; cur = this; while(cur != null){ if(cur.left == prev){ cur.balance--; }else{ cur.balance++; } if(cur.balance == 0)break; prev = cur; cur = cur.parent; } }else{ this.balance = 0; } }else { //左に部分木あり this.left.insert(key,value); } }else if(this.key < key){ //右に挿入 if(this.right == null){ //右に子がない this.right = new AVLTree<T>(key,value,this); if(this.left == null){ //先祖のバランス値を調整 prev = this.right; cur = this; while(cur != null){ if(cur.left == prev){ cur.balance--; }else{ cur.balance++; } if(cur.balance == 0)break; prev = cur; cur = cur.parent; } }else{ this.balance = 0; } }else { //右に部分木あり this.right.insert(key,value); } }else{ //既存のキーの場合：上書きする this.value = value; } //木を再構成し平衡条件を回復 this.reconstruct(); return; } //キーを指定して検索 public AVLTree<T> search(int key){ if(this.key == key && this.value != null)return this; if(this.key > key)return this.left.search(key); if(this.key < key)return this.right.search(key); return null; } //最小の値を削除 //木から切り取るだけなので、この関数から返ったノードへのアドレスを呼び出し側で受けることで削除したノードへのアクセスが可能 //なお、削除操作での使用を想定しているため、削除ノードが根だった場合を考慮していない public AVLTree<T> extractMin(){ AVLTree<T> cur,prev; if(this.left == null){ //左に子を持たない場合：これが最小ノードなので、削除 //先祖のバランス値を調整 prev = this; cur = this.parent; while(cur != null){ if(cur.left == prev){ cur.balance++; if(cur.balance > 0)break; }else{ cur.balance--; if(cur.balance < 0)break; } prev = cur; cur = cur.parent; } if(this.right == null){ //孤立した（子がない）場合：削除ノードを切り離す if(this.parent.left == this){ this.parent.left = null; }else { this.parent.right = null; } }else{ //右に子を持つ場合：このノードの代わりに右の子を親の子とする if(this.parent.left == this){ this.parent.left = this.right; }else { this.parent.right = this.right; } this.right.parent = this.parent; } return this; }else{ //左に子を持つ場合：左の部分木の最小ノードを取り除く return this.left.extractMin(); } } //キーを指定して削除 public boolean delete(int key){ AVLTree<T> del = this.search(key); AVLTree<T> cur,prev; //削除するノードが見つからなかった場合 if(del == null)return false; //削除 if(del.left == null && del.right == null){ if(del.parent != null){ //先祖のバランス値を調整 prev = del; cur = del.parent; while(cur != null){ if(cur.left == prev){ cur.balance++; if(cur.balance > 0)break; }else{ cur.balance--; if(cur.balance < 0)break; } prev = cur; cur = cur.parent; } //子が根ではなく、両方とも子がない場合：削除ノードを切り離す if(del.parent.left == del){ del.parent.left = null; }else { del.parent.right = null; } //木を再構成し平衡条件を回復 del.parent.reconstruct(); }else{ //子が根であり、両方とも子がない場合：キーと値を削除する del.key = 0; del.value = null; } }else if(del.left == null){ //先祖のバランス値を調整 prev = del; cur = del.parent; while(cur != null){ if(cur.left == prev){ cur.balance++; if(cur.balance > 0)break; }else{ cur.balance--; if(cur.balance < 0)break; } prev = cur; cur = cur.parent; } if(del.parent != null){ //子が根ではなく、左にのみ子がない場合：このノードの代わりに右の子を親の子とする if(del.parent.left == del){ del.parent.left = del.right; }else { del.parent.right = del.right; } del.right.parent = del.parent; //木を再構成し平衡条件を回復 del.parent.reconstruct(); }else{ //子が根であり、左にのみ子がない場合：平衡条件より右には一つしかノードが無いので、データを継承して切り離す del.key = del.right.key; del.value = del.right.value; del.right = null; //バランス値更新 this.balance = 0; } }else if(del.right == null){ //先祖のバランス値を調整 prev = del; cur = del.parent; while(cur != null){ if(cur.left == prev){ cur.balance++; if(cur.balance > 0)break; }else{ cur.balance--; if(cur.balance < 0)break; } prev = cur; cur = cur.parent; } if(del.parent != null){ //子が根ではなく、右にのみ子がない場合：このノードの代わりに左の子を親の子とする if(del.parent.left == del){ del.parent.left = del.left; }else { del.parent.right = del.left; } del.left.parent = del.parent; //木を再構成し平衡条件を回復 del.parent.reconstruct(); }else{ //子が根であり、右にのみ子がない場合：平衡条件より左には一つしかノードが無いので、データを継承して切り離す del.key = del.left.key; del.value = del.left.value; del.left = null; //バランス値更新 this.balance = 0; } }else{ //両方に子を持つ場合：右の最小の子とデータを入れ替え、右の最小の子を切り離す AVLTree<T> min = del.right.extractMin(); del.key = min.key; del.value = min.value; //木を再構成し平衡条件を回復 if(min.parent != null)min.parent.reconstruct(); } return true; }
挿入におけるバランス値の調整は、以下のように行う。
[挿入]
(1)再帰呼び出しで、最終的に挿入ノードを子とするノードまで行く。
(2)右（左）に挿入したとき、左（右）に子が無ければ、その挿入によってそのノードを根とする部分木の高さが１高くなってしまうので、以下の[a]〜[c]のループを根までボトムアップで適用し、バランス値の更新を行う。
初期値は
prev = 挿入ノード
cur = 挿入ノードの親
[a]prevを根とする部分木は高さが１増えたので、
prevがあるほうにcurのバランスを１つ傾ける。
（右ならbalanceを+1、左ならbalanceを-1）
[b]今のバランスの更新によってバランス値が０、すなわち平衡が保たれた時、ループを抜ける。
[c]prev=cur、cur=「curの親」
↑の操作で何故バランスが保たれるのかというと、ループ内では常に「curがバランス値を更新するノードで、prevを根とする部分木の高さは１増えている」という条件が保たれているから。
部分木のバランスは挿入する前は「１．右に１つ傾いている」「２．左に１つ傾いている」「３．平衡が保たれている」のどれかで、挿入後は「１．右に２つ傾いている」「２．左に２つ傾いている」「３．右に１つ傾いている」「４．左に１つ傾いている」「５．平衡が保たれている」のどれかですが、１．２．の場合は部分木の高さが明らかに増えてますし、３．４．は「もともと平衡が保たれた状態で、右（或いは左）に挿入されたことによって傾いた」ことによってしか起こり得ない状況なので、これもやはり平衡していた状態からは高さが増えています。
[b]で「５．平衡が保たれている」でループを抜けたのは、５．の場合はもともと右（左）に傾いていた部分木のバランスが取れたときに起こりうる状況で、このときその部分木の高さは変わらないからです。
次に削除におけるバランス値の調整。
ただ、根を削除する場合とかは割愛して書いてます。やってることが見えにくくなるので。
[削除]
(1)再帰呼び出しで、削除するノードまで行く。
(2)両方とも子を持たない場合はextractMin操作で最終的に切り取るノードのところまで行く。
(3)右（左）のノードを削除したとき、左（右）にも子が無ければ、その挿入によってそのノードを根とする部分木の高さが１低くなってしまうので、以下の[a]〜[c]のループを根までボトムアップで適用し、バランス値の更新を行う。
初期値は
prev = 削除ノード
cur = 削除ノードの親
[a]prevを根とする部分木は高さが１減ったので、
prevがあるのとは逆側にcurのバランスを１つ傾ける。
（右ならbalanceを-1、左ならbalanceを+1）
[b]右（左）にバランスを傾けた場合、それによって部分木全体が右（左）よりに傾いたなら、ループから抜ける。
[c]prev=cur、cur=「curの親」
これも基本的に挿入と同じ。
ループ内条件は「curがバランス値を更新するノードで、prevを根とする部分木の高さは１減っている」
[b]でループから抜けている状況も、その状況になった場合は部分木全体の高さに変化が生じないから抜けているということです。詳しくは説明しませんが暇な人は確認してみると面白いかも。
再構成操作におけるバランス値調整もこれと同じで、回転によって木の高さそのものが１減った場合、[削除]と同じようなアルゴリズムでバランス値を調整しています。つまりループ内条件：「curがバランス値を更新するノードで、prevを根とする部分木の高さは１減っている」を保ち、[b]でループから抜ける条件も同じです。
まあ、だいぶ端折りましたがこんな感じです。
後はコレをAVLTree
ちなみに、試みにGIFアニメで動作の様子を掲載しようと思ったのですが、削除を作る前に力尽きました。挿入だけ載せときます。
……って、よく見たら二重回転が一度も生じてないね。
まあ、こんな風に自動的に自動的に枝別れの多い理想的な木を生成してくれるわけです。
さて、新年一発目からこんなあちらこちら端折った記事を書いてるようじゃ先が思いやられますね。
まあ、これからよこれから。
次は何書くか未定。
それじゃ（・ω・）ﾉｼ
