AVL木

AVL木とは 各節点の左部分木と右部分木の高さの差が１以下になるようなソート木 木の高さはO(logn) これは、ソート木では最悪の場合にO(n)かかる、という短所を克服している。

AVL木の例 各節点に関して、左部分木と右部分木の高さとの差が１以下となっている。

AVL木の操作上の注意 木の探索については、ソート木と同じ操作でよい。

節点の追加 節点を追加する場所を探しに木を再帰的に下がっていき、節点を追加する。その後、木の上方に向かって、再帰的に呼び出された手続きから復帰していく。このとき、各節点でAVL木の特性が保たれているかをチェックする。 復帰していく過程で、部分木の高さの差が２であればバランスを保つ処理を行わなければならない。 復帰していく過程で節点を追加する前と後で部分木の高さが変化していないところに達したら、それより上の部分木については高さは変化していないため、これより上の部分木についてチェックする必要はない。 Eを追加する場合を考える。 木を最適的に下がっていき、Dの右部分木にEを追加する。 節点Dに関しては、左部分木の高さ0,右部分木の高さ1 であり、差が１なので、AVL木の特性は保たれている。 節点Cに関しては、左部分木の高さ0, 右部分木の高さ2であり、差が2なので、バランスを保つ処理が必要。 この処理で、Bの右部分木の高さは追加前と追加後で変化がないので、節点Dよりも上の節点ではバランスが保たれている。 D C A B E 追加 E D A B C

節点の追加 -４種類のパターン- X B A R LR RL L 節点の追加　-４種類のパターン- AVL木に節点を追加する場合、節点の追加位置によって、木がバランスを崩すパターンが４つ存在する。バランスを回復する処理もそれぞれで異なる。 そのパターンと処理方法は以下の表のとおり。（それぞれの処理方法については後述） 節点が追加された位置 バランスを回復する処理 R部分木 右回転 L部分木 左回転 LR部分木 左－右回転 RL部分木 右－左回転 X B A R LR RL L

節点の追加 -右回転- T1 T2 T3 A X ここに追加 T1 T2 T3 A X 節点の追加　-右回転- R部分木に追加して、バランスが崩れた場合の処理（下図） 追加後の高さに関する前提条件 部分木TAと部分木T3の高さの差はちょうど２ 部分木T1と部分木T２の高さの差は１以下 T1 T2 T3 A X ここに追加 T1 T2 T3 A X TA

節点の追加 -左回転- T3 T2 T1 B X ここに追加 T3 T2 T1 A B 節点の追加　-左回転- 右回転の場合と同様の考え方で左回転を行うことが出来る。 T3 T2 T1 B X ここに追加 T3 T2 T1 A B

節点の追加 -左－右回転- T1とT3は同じ深さにある T1 T2 T3 T4 A X C T1 T2 T3 T4 A X C 節点の追加　-左－右回転- LR部分木に追加して、バランスが崩れた場合の処理（下図） 追加後の高さに関する前提条件 TAとT4の高さの差は２ T2とT３の高さの差は１以下 　T1とT3は同じ深さにある T1 T2 T3 T4 A X C ここに追加 T1 T2 T3 T4 A X C ここでは、T2に追加しているが、T3に追加する場合も同じ TA

節点の追加 -右－左回転- T4 T3 T2 T1 B X D T4 T3 T2 T1 B X D 節点の追加　-右－左回転- 左－右回転と同じ考え方で右－左回転を行うことが出来る。 ここでは、T2に追加しているが、T3に追加する場合も同じ T4 T3 T2 T1 B X D ここに追加 T4 T3 T2 T1 B X D

節点の削除　-４種類のパターン- AVL木はソート木の一種であるため、ソート木の削除処理が必要である。しかし、これらの処理が終わったら、木を上向きに戻りつつ、バランスが保たれていることをチェックし、保たれていなければ、適切な回転操作を行い、バランスを回復する。 回転操作は節点の追加で使ったものと同じである。 しかし、回転操作をどの状況で利用するか、という点で若干異なる。 また、追加の場合と異なり、ある部分木に対してバランスを保つ処理を行うと、部分木の高さが小さくなる可能性があり、その場合はそれより上方にある部分木についてもチェックをしなければならない。 削除された位置 状況 バランスを回復する処理 左部分木 右部分木の右半分が左半分よりも高い、または同じ高さ 右回転 右部分木の左半分が右半分よりも高い 右－左回転 右部分木 左部分木の左半分が右半分よりも高い、または同じ高さ 左回転 左部分木の右半分が左半分名よりも高い 左－右回転

節点の削除 -左回転- T3 T1 B X T2 T3 T2 T1 B X 左部分木から節点を削除して、バランスが崩れた場合の処理（下図） 条件：T2の高さはT3の高さと等しいか、低い。 　　　の部分があれば、部分木の高さは変わらないので、これより上の部分木についてはチェックする必要はない。　　　の部分がなければ、部分木の高さが１減るので、Bより上の部分木でもバランスが崩れている可能性があり、チェックを続ける。 T3 T1 B X ここの節点を削除 T2 T3 T2 T1 B X 　　　の部分はあってもなくてもよい

節点の削除 -右－左回転- T4 T3 T2 T1 B X D X TD B D T1 T2 T4 T3 節点の削除　-右－左回転- 左部分木から節点を削除して、バランスが崩れた場合の処理（下図） 条件：部分木TDは部分木T4よりも高い。 回転によって木の高さが１低くなるため、節点Xよりも上方の部分木でバランスが崩れている可能性がある。よって、上方の部分木についてもバランスをチェックする必要がある。 T4 T3 T2 T1 B X D X TD B D T1 T2 T4 T3 ここから削除

節点の削除　-右回転, 左－右回転- 右回転、左－右回転については、左回転、右－左回転と同様の考えで、削除される節点が節点Xの右部分木にあることを考慮するだけでよい。

作成したプログラム 作成したクラス AVL木の機能のうち、節点の追加、その中でも、左回転、右－左回転を行うプログラムを作成した。 main関数で、節点を追加し、左回転、右回転を実行してみて、正しく動いていることを確認する。 作成したクラス AVL木クラス class CAvlTree{ public: CAvlTree(); //コンストラクタ CAvlTree(CAvlTreeNode *node); //コンストラクタ（引数あり） CAvlTreeNode *AddNode(int new_number, bool &grew); void PrintTree();// ノードの要素を表示(中央順で表示) private: CAvlTreeNode *root; //木のルートへのポインタ 　CAvlTreeNode *RebalanceRightGrew();//左回転、右-左回転を行なう class CAvlTreeNode{ friend class CAvlTree; public: CAvlTreeNode(int new_number); // コンストラクタ private: int number; // ノードの要素 EnumBalance Balance; // バランス CAvlTreeNode *LeftChild; // 左の子 CAvlTreeNode *RightChild; // 右の子 }; ノードクラス

節点の追加、左回転、右－左回転のプログラム説明 節点を追加するAddNode,左回転、右－左回転を行うRebalanceRightGrewの返り値を処理を行った部分木のルートノードのアドレスを返すようにしている。この返り値を親の子へのポインタとする。 また、各ノードで、左右どちらのノードが高くなっているかを記憶するために、変数Balanceを用いている。 Balance = LeftHeavy : 左部分木のほうが１高い Balance = Balanced : 左右の部分木の高さが等しい Balance = RightHeavy : 右部分木のほうが１高い また、節点を追加した後に木の高さが増えたかどうかを記憶するために、変数grewを用いている。 grew = TRUE : 木の高さが増えた grew = FALSE : 木の高さに変化はない

節点の追加 //高さが変わった場合 if(root->Balance == RightHeavy){ //節点挿入前は右部分木のほうが高く、今回左部分木に挿入されたことで、高さが等しくなった。 root->Balance = Balanced; grew = FALSE; return root; }else if(root->Balance == Balanced){ //節点挿入前は左右の部分木の高さは等しかったが、左部分木に挿入されたことで、左部分木の高さが１高くなった root->Balance = LeftHeavy; grew = TRUE; }else{ //節点挿入前は左部分木のほうが高く、今回左部分木に挿入されたことで、回転操作（右回転または左－右回転）を行わなければならない。 // RebalanceLeftGrew(parent); //作成していない } 節点の追加 CAvlTreeNode *CAvlTree::AddNode(int new_number, bool &grew) { if(root == NULL){// 木の一番下になっている場合新しい接点を追加 root = new CAvlTreeNode(new_number); grew = TRUE; return root; } CAvlTree LeftTree(root->LeftChild); CAvlTree RightTree(root->RightChild); if(new_number <= root->number){ //左部分木に挿入する場合 root->LeftChild = LeftTree.AddNode(new_number, grew); if(!grew) //左部分木に挿入した結果、高さが変わってない場合 grew = TRUE; return root; } else{ root = RebalanceRightGrew(); grew = FALSE; }

} else{ //もともと右部分木の方が高く、右部分木に挿入されたことで、回転操作（左回転または右－左回転）を行わなければならない root = RebalanceRightGrew(); grew = FALSE; return root; } }else{ //右部分木に挿入する場合 root->RightChild = RightTree.AddNode(new_number, grew); if(!grew)　//右部分木に挿入したが、高さが変わらなかった場合 return root; if(root->Balance == LeftHeavy){ //もともと左部分木のほうが高く、右部分木に挿入したことで左右の部分木の高さが等しくなった。 root->Balance = Balanced; grew = FALSE; } else if(root->Balance == Balanced){ //もともと左右の部分木の高さは等しく、右部分木に挿入したことで右部分木の高さが１高くなった root->Balance = RightHeavy; grew = TRUE;

左回転、右ー左回転 root->RightChild = grandchild->LeftChild; grandchild->LeftChild = root; if(grandchild->Balance = RightHeavy){ root->Balance = LeftHeavy; }else{ root->Balance = Balanced; } if(grandchild->Balance = LeftHeavy){ child->Balance = RightHeavy; child->Balance = Balanced; root = grandchild; } //右－左回転の終わり return root; CAvlTreeNode *CAvlTree::RebalanceRightGrew() { CAvlTreeNode *child, *grandchild; child = root->RightChild; if(child->Balance == RightHeavy){ // 左回転 root->RightChild = child->LeftChild; child->LeftChild = root; root->Balance = Balanced; root = child; //左回転の終わり }else{ // 右-左回転 grandchild = child->LeftChild; child->LeftChild = grandchild->RightChild; grandchild->RightChild = child;

メイン関数（テストプログラム） #include <stdio.h> #define TRUE 1 #define FALSE 0 enum EnumBalance { LeftHeavy, Balanced, RightHeavy}; // メイン関数 int main(){ bool grew = FALSE; CAvlTree tree; tree.AddNode(2, grew); tree.AddNode(1, grew); tree.AddNode(3, grew); //次の追加操作までは回転処理は行なわれない tree.AddNode(4, grew); tree.PrintTree(); printf("\n"); // 次の追加操作で左回転が処理される tree.AddNode(6, grew); tree.PrintTree(); printf("\n"); // 次の操作で右回転が処理される tree.AddNode(5, grew); tree.PrintTree(); printf("\n"); return 0; }

実行結果 木を、（中身 左部分木 右部分木）で表示することで、 木がどのような構造になっているかを確認した。 2 4 6 1 3 2 3 4 木を、（中身　左部分木　右部分木）で表示することで、 木がどのような構造になっているかを確認した。 tree.AddNode(2, grew); tree.AddNode(1, grew); tree.AddNode(3, grew); 　tree.AddNode(4, grew);　実行後 (2 (1 () () ) (3 () (4 () () ) ) ) (2 (1 () () ) (4 (3 () () ) (6 () () ) ) ) (4 (2 (1 () () ) (3 () () ) ) (6 (5 () () ) () ) ) tree.AddNode(6, grew);　実行後 tree.AddNode(5, grew);　実行後 2 4 6 1 3 2 3 4 1 4 6 5 2 3 1 AddNode(6, grew)実行後 AddNode(5, grew)実行後 AddNode(4, grew)実行後