このページでは「平衡２分探索木」の１つである「AVL 木」の解説およびその実装例をC言語で紹介をしていきたいと思います。
２分探索木では各ノードに対して下記の関係が成立するため、探索値とノードの値を比較しながら木を辿っていくだけで、簡単に探索値を見つけ出すことができます。
- 左の子ノードの値 ≦ ノードの値 ≦ 右の子ノードの値
２分探索木では、探索に必要な演算量の最悪値は木の高さに比例します。
しかし、単なる２分探索木ではデータの追加する順番によっては、下の図のようにノードが木の一方側に集まってしまい、木の高さが高くなってしまい、効率的に探索を行うことができません。
このページで紹介する「AVL 木」では、上の図のようにノードが一方側に偏ることを防ぎ、木の高さを小さくすることが可能です（したがって探索を効率的に行うことが可能です）。
２分探索木とC言語での実装例の解説については下記ページで行っており、下記ページを基にこのページの解説やC言語プログラムの紹介を行っていきますので、是非下記ページを読んでからこのページを読んでいただきたいと思います（もちろん読まなくても大丈夫、既に２分探索木について知っている方という方は飛ばしていただいても問題ありません）。
C言語で二分探索木（木構造・ツリー構造）をプログラミング
AVL 木とは
「AVL 木」とは下記の条件を満たす２分探索木となります。
- どのノードの左右部分木の高さの差も１以下
「AVL 木」では、ノードの追加・削除時に上記条件を満たさなくなると、後述する「回転」という操作を行って左右部分木の高さの調節を行い、上記条件を満たすように木の変形を行います。
例えば下記のようにノードが追加されると、「どのノードの左右部分木の高さの差も１以下」という条件が満たされなくなってしまいます。
この時に回転を行って「どのノードの左右部分木の高さの差も１以下」という条件を満たすように木を変形させます。
ノードの追加や削除時にコレを繰り返すことで「どのノードの左右部分木の高さの差も１以下」という条件を維持し続けます。これが AVL 木です。
この「AVL 木」のように、「木の高さを自動的にできるだけ小さく維持しようとする２分探索木」を平衡２分探索木と言います。
AVL 木の実現方法
では「AVL 木」はどのようにして実現することができるのか？ここについて解説していきたいと思います。
「AVL 木」は前述の通り２分探索木の１つであり、２分探索木を拡張することで実現することができます。
特に「AVL 木」は単なる２分探索木に対し、下記の条件を満たすという特徴を持ちます。
- どのノードの左右部分木の高さの差も１以下
また、２分探索木において、木の高さが変化するのは下記の処理を行った場合です。
- ノード追加時
- ノード削除時
これらの処理を行った際に、木の高さが変化する可能性があるのは、追加 or 削除したノードの「親ノード」から「木の根ノード」までの「経路に存在する全ノード」の左右部分木となります（削除に関しては後述するように注意事項があります）。
ですので、二分探索木のプログラムに対し、「ノード追加処理」と「ノード削除処理」実行後に下記を行うように拡張してやれば、AVL 木を実現することができます（ “追加” の例で書いていますが “削除” も同様です）。
- ノードの追加
- 追加したノードの親ノードまで辿る
- そのノードの左右部分木の高さの差が１以下かどうかを判断
- １よりも大きい場合：
- そのノードを根ノードとする部分木に対して回転を実行
- そのノードの親ノードを辿る（親ノードがなければ終了）
- 3. に戻る
ここからはポイントとなる 2. と 3. と 5. の処理について詳細を解説します。
ここでは基本的に “追加” に焦点を当てて解説を行いますが、”削除” においても同様の考え方で処理を実現することができます
スポンサーリンク
ノードを辿る
この処理は「AVL 木に必要な処理の 2. 」に当てはまる処理になります。
AVL 木を実現するにあたって、ノードの追加後に、その追加したノードの親ノードまで辿る処理を実現する必要があります。
２分探索木ではもともと、追加処理時には追加するノードのデータと木の各ノードのデータの大小関係を比較しながら、根ノードからノードを辿っていくことにより追加する場所を決定するようになっています。
ですので、追加時に辿った経路を覚えておき、追加後に再度その経路を辿ることで、追加したノードの親ノードまで辿ることが可能です。
前述の通り、ノードの追加により、この経路上のノードの左右部分木の高さが変化する可能性があります。
したがって、AVL 木を実現するためには、この経路上の全ノードに対し、ここから解説する「平衡係数を計算する」を行い、さらに必要に応じて「回転する」を行っていく必要があります。
必ずしも経路上の全ノードを辿って「平衡係数を計算する」を行う必要はないのですが、全ノード辿る方が説明やプログラムが簡単になるので、このページでは全ノード辿る前提で説明を記載しています
削除の時も基本的に上記で記載したものと同様の手順で目的のノードまで辿ることができます。
ただし、この目的のノードは「実際に削除した位置のノードの親ノード」であることに注意してください。
２分探索木の削除では、削除するノードが左右両方向に子ノードを持っている場合は、下記のように削除が行われます。
- 削除対象のノードの左の子孫ノードの中で最大値を持つノードを探索する
- その最大値を持つノードと削除対象のノードを置き換える
- 置き換え後、削除対象のノードを削除する
つまり、実際に削除されるノードは、もともと最大値を持つノードがあった位置のノードになります。
したがって、左右両方向に子ノードを持っているノードを削除した後は、この最大値を持つノードの親ノードまで辿る必要があります。
平衡係数を計算する
この処理は「AVL 木に必要な処理の 3. 」に当てはまる処理になります。
平衡係数とは、あるノードを根ノードとした部分木のバランスが取れているかどうかを測る指標になります。
この平衡係数は、あるノードの右部分木と左部分木それぞれの高さを用いて下記式で計算することができます（左右は逆でも良いです）。
平衡係数 = 右部分木の高さ - 左部分木の高さ
上式で計算した場合、平衡係数が正の値であれば右部分木の方が高く、負の値であれば左部分木の方が高いことになります。
例えば下の図だと、赤色のノードの平衡係数は “2” になります。青色のノードの平衡係数は ” -1″ になります。
この平衡係数の絶対値が “1” よりも大きい場合は、下記の条件を満たしていないことになります。
- どのノードの左右部分木の高さの差も１以下
AVL 木では、「追加したノードの親ノード」〜「根ノード」までの経路上に存在するノードに対し、この平衡係数を計算し、絶対値が “1” よりも大きいノードに対して次で説明する「回転する」を行います。
ちなみに、平衡係数の絶対値が１以下のノードはバランスが取れている（上記条件を満たしている）ので特に処理を行う必要はないです。
回転する
この処理は「AVL 木に必要な処理の 5. 」に当てはまる処理になります。
２分探索木における「回転」とは、下記の条件を崩さないように木の構造を変化させる操作になります。
- 左の子ノードの値 ≦ ノードの値 ≦ 右の子ノードの値
この「回転」を行うことで、一方の部分木の高さを増加させ、さらに他方の部分木の高さを減少させることができます。つまり、この「回転」を行うことで、平衡係数を増減させることができます。
AVL 木では、平衡係数の絶対値が “1” を超えた際には、この回転を行うことで平衡係数の絶対値を “1” 以下にし、常に下記の条件を満たすように木の状態を保ちます。
- どのノードの左右部分木の高さの差も１以下
AVL 木では下記の４種類の回転を使い分けることで、平衡係数の増減を行います。
- 左回転
- 右回転
- ２重回転（左→右）
- ２重回転（右→左）
基本的に、平衡係数が “-1” よりも小さい（左部分木の方が高い）場合は「左回転」、平衡係数が “1” よりも大きい（右部分木の方が高い）場合は「右回転」を行うことで平衡係数の調整を行っていきます。
ただし、特定の条件が成立した場合のみ２重回転を行う必要があります。これについては後述します。
それでは各回転をどのようにして行うかについて解説していきたいと思います。
左回転
あるノードを根ノードとした部分木を左方向に回転するのが「左回転」です。
左回転を行うことにより左部分木の高さが増加し、さらに右部分木の高さが減少します。
根ノードを node、根ノードの親ノードを parent、回転後に新たな根となるノードを pivot とすると、node を根とした部分木の左回転は下記のようにして行うことができます。
pivotにnodeの右の子ノードを設定
nodeの右の子ノードにpivotの左の子ノードを設定
pivotの左の子ノードにnodeを設定
parentのnodeを指している方の子ノードにpivotを設定
- 各ノードの配置を整理すと下記のように左部分木の高さが増加している
右回転
あるノードを根ノードとした部分木を右方向に回転するのが「右回転」です。
右回転を行うことにより右部分木の高さが増加し、さらに左部分木の高さが減少します。
右回転は左回転で示した手順の「左・右を逆」にした手順により実現することができます。
-
pivotにnodeの左の子ノードを設定nodeの左の子ノードにpivotの右の子ノードを設定pivotの右の子ノードにnodeを設定parentのnodeを指している方の子ノードにpivotを設定
２重回転（左→右）・２重回転（右→左）
まずは２重回転の必要性について説明します。
基本的に左回転もしくは右回転を行うことで平衡係数の絶対値は “1” 以下になります。
ですが、特定の条件の時のみ平衡係数の絶対値が “1” 以下にならないので、この時だけ２重回転を行うことで平衡係数の絶対値を “1” 以下にする必要があります。
特定の条件とは、下記の２つです。
- ノードの平衡係数が “-1” より小さい、かつ、そのノードの左の子ノードの平衡係数が “1” 以上
- ノードの平衡係数が “1” より大きい、かつ、そのノードの右の子ノードの平衡係数が “-1” 以下
例えば下の図では node が上記条件の 1. に当てはまります。
ノードの平衡係数は “-2” ですので、右部分木の高さを増加＆左部分木の高さを減少させるために、右回転を行ってみましょう。
右回転を行うことで、右部分木の高さが増加＆左部分木の高さが減少しましたが、”2″ ずつ増加＆減少してしまったため、平衡係数の絶対値が “1” 以下になりません（pivot の平衡係数は “2” になっています）。
こんな感じで「２重回転を行う条件 1. もしくは 2. 」に当てはまる場合、単に左回転 or 右回転を行うだけでは平衡係数の絶対値が “1” 以下になりません。
そこで、単に左回転 or 右回転を行うのではなく、２重回転を行うことでこれを解決します。
上記の「２重回転を行う条件 1. 」に当てはまる場合には、下記のように左回転→右回転を連続して行う２重回転を実行します。
- ノードの左の子ノードを根ノードとして左回転
- ノードを根ノードとして右回転
例えば上でも示した下記のノードの配置の場合を考えてみましょう。
この場合は、node の左の子ノードを根ノードとして左回転を行います。左回転を行った結果は下の図のようになります。
この状態だと平衡は保たれていませんが、さらに node 対して右回転を行うことで下の図のように各ノードの平衡係数の絶対値を “1” 以下にすることができます。
また上記の「２重回転を行う条件 2. 」に当てはまる場合には、下記のように右回転→左回転を連続して行う２重回転を実行します。
- ノードの右の子ノードを根ノードとして右回転
- ノードを根ノードとして左回転
このようにして、基本的には平衡係数の絶対値が “1” を超える場合には、平衡係数の値に応じて左回転と右回転を使い分け、さらに「２重回転を行う条件」に当てはまる場合に２重回転を行うことで、下記の条件を満たした木に保つことができます。
- どのノードの左右部分木の高さの差も１以下
スポンサーリンク
AVL 木のプログラムと解説
続いてここまで説明してきた AVL 木のC言語プログラムの紹介とプログラムの解説をしていきたいと思います。
プログラム
まず AVL 木をC言語で実装したプログラムは下記のようになります。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NAME_LEN 256
#define MAX_HEIGHT 100
#define TREE_LEFT 1
#define TREE_RIGHT 2
/* 二分探索木のノードを表す構造体 */
struct node_t {
int number;
char name[MAX_NAME_LEN];
struct node_t *left;
struct node_t *right;
};
/* getHeight:二分探索木のノード全てを削除する
引数１ node : 根ノードのアドレス
返却値 : nodeを根とした木の高さ */
int getHeight(struct node_t *node) {
int left_height;
int right_height;
int tree_height;
if (node == NULL) {
/* nodeが無いなら高さは0 */
return 0;
}
/* 左右の子を根とした木の高さを取得 */
left_height = getHeight(node->left);
right_height = getHeight(node->right);
/* 大きい方に+1したものを木の高さとして返却 */
if (left_height > right_height) {
tree_height = left_height;
} else {
tree_height = right_height;
}
return tree_height + 1;
}
/* leftRotate:nodeを根とする部分木を回転（左）
引数１ root : 根のノードを指すアドレス
引数２ node : 回転する部分木の根ノードを指すアドレス
引数３ parent : nodeの親ノードを指すアドレス
引数４ direction : parentから見たnodeのある方向
返却値 : 根のノードを指すアドレス */
struct node_t *leftRotate(struct node_t *root, struct node_t *node, struct node_t *parent, int direction) {
/* nodeを根として左回転を行う */
struct node_t *pivot;
struct node_t *new_root;
printf("left_rotate:%d\n", node->number);
/* 新しい根とするノードをpivotとして設定 */
pivot = node->right;
/* 左回転 */
if (pivot != NULL) {
node->right = pivot->left;
pivot->left = node;
}
/* parentもしくはrootに新しい根ノードを参照させる */
if (parent == NULL) {
new_root = pivot;
return new_root;
}
/* どちらの子に設定するかはdirectionから判断 */
if (direction == TREE_LEFT) {
parent->left = pivot;
} else {
parent->right = pivot;
}
return root;
}
/* rightRotate:nodeを根とする部分木を回転（右）
引数１ root : 根のノードを指すアドレス
引数２ node : 回転する部分木の根ノードを指すアドレス
引数３ parent : nodeの親ノードを指すアドレス
引数４ direction : parentから見たnodeのある方向
返却値 : 根のノードを指すアドレス */
struct node_t * rightRotate(struct node_t *root, struct node_t *node, struct node_t *parent, int direction) {
struct node_t *pivot;
struct node_t *new_root;
printf("right_rotate:%d\n", node->number);
/* 新しい根とするノードをpivotとして設定 */
pivot = node->left;
/* 右回転 */
if (pivot != NULL) {
node->left = pivot->right;
pivot->right = node;
}
/* parentもしくはrootに新しい根ノードを参照させる */
if (parent == NULL) {
new_root = pivot;
return new_root;
}
/* どちらの子に設定するかはdirectionから判断 */
if (direction == TREE_LEFT) {
parent->left = pivot;
} else {
parent->right = pivot;
}
return root;
}
/* leftRightRotate:nodeを根とする部分木を二重回転（右->左）
引数１ root : 根のノードを指すアドレス
引数２ node : 回転する部分木の根ノードを指すアドレス
引数３ parent : nodeの親ノードを指すアドレス
引数４ direction : parentから見たnodeのある方向
返却値 : 根のノードを指すアドレス */
struct node_t *rightLeftRotate(struct node_t *root, struct node_t *node, struct node_t *parent, int direction) {
/* ２重回転（Right Left Case）を行う */
struct node_t *new_root;
printf("right_left_rotate:%d\n", node->number);
/* nodeの右の子ノードを根として右回転 */
new_root = rightRotate(root, node->right, node, TREE_RIGHT);
/* nodeを根として左回転 */
return leftRotate(new_root, node, parent, direction);
}
/* leftRightRotate:nodeを根する部分木を二重回転（左->右）
引数１ root : 根のノードを指すアドレス
引数２ node : 回転する部分木の根ノードを指すアドレス
引数３ parent : nodeの親ノードを指すアドレス
引数４ direction : parentから見たnodeのある方向
返却値 : 根のノードを指すアドレス */
struct node_t * leftRightRotate(struct node_t *root, struct node_t *node, struct node_t *parent, int direction) {
/* ２重回転（Left Right Case）を行う */
struct node_t *new_root;
printf("left_right_rotate:%d\n", node->number);
/* nodeの左の子ノードを根として左回転 */
new_root = leftRotate(root, node->left, node, TREE_LEFT);
/* nodeを根として右回転 */
return rightRotate(new_root, node, parent, direction);
}
/* balancing:nodeからbranchで辿ったノードを平衡にする
引数１ root : 根のノードを指すアドレス
引数２ node : 平衡にするノードを指すアドレス
引数３ parent : nodeの親ノードを指すアドレス
引数４ direction : parentから見たnodeのある方向
引数５ branch : 平衡化を行うノードへの経路
引数６ num_branch : branchに格納された経路の数
返却値 : 根のノードを指すアドレス */
struct node_t * balancing(struct node_t *root, struct node_t *node, struct node_t *parent, int direction, int *branch, int num_branch) {
struct node_t *next;
struct node_t *new_root;
int left_height, right_height;
int balance;
if (node == NULL || root == NULL) {
return root;
}
if (num_branch > 0) {
/* 辿れる場合はまず目的のノードまで辿る */
/* 辿る子ノードを設定 */
if (branch[0] == TREE_LEFT) {
next = node->left;
} else {
next = node->right;
}
/* 子ノードを辿る */
new_root = balancing(root, next, node, branch[0], &branch[1], num_branch - 1);
}
/* 平衡係数を計算 */
left_height = getHeight(node->left);
right_height = getHeight(node->right);
balance = right_height - left_height;
if (balance > 1) {
/* 右の部分木が高くて並行状態でない場合 */
/* ２重回転が必要かどうかを判断 */
if (getHeight(node->right->left) > getHeight(node->right->right)) {
/* ２重回転（Right Left Case）*/
return rightLeftRotate(new_root, node, parent, direction);
} else {
/*１重回転（左回転）*/
return leftRotate(new_root, node, parent, direction);
}
} else if (balance < -1) {
/* 左の部分木が高くて並行状態でない場合 */
/* ２重回転が必要かどうかを判断 */
if (getHeight(node->left->right) > getHeight(node->left->left)) {
/* ２重回転（Left Right Case）*/
return leftRightRotate(new_root, node, parent, direction);
} else {
/* １重回転（右回転）*/
return rightRotate(new_root, node, parent, direction);
}
}
return root;
}
/* deleteTree:二分探索木のノード全てを削除する
引数１ root : 根ノードのアドレス
返却値 : なし */
void deleteTree(struct node_t *root){
if(root == NULL){
return;
}
if(root->left != NULL){
deleteTree(root->left);
}
if(root->right != NULL){
deleteTree(root->right);
}
printf("free:%d(%s)\n", root->number, root->name);
free(root);
}
/* mallocNode:ノードの構造体のメモリを確保し、データを設定
引数１ number : 追加する会員番号
引数２ name : 追加する会員の名前
返却値 : 追加したノードのアドレス */
struct node_t *mallocNode(int number, char *name){
struct node_t *add;
add = (struct node_t*)malloc(sizeof(struct node_t));
if(add == NULL){
return NULL;
}
add->left = NULL;
add->right = NULL;
add->number = number;
strcpy(add->name, name);
return add;
}
/* addNode:指定されたnumberとname持つノードを追加する
引数１ root : 根ノードのアドレス
引数２ number : 追加する会員番号
引数３ name : 追加する会員の名前
返却値 : 根ルートのアドレス */
struct node_t *addNode(struct node_t *root, int number, char *name){
struct node_t *node;
int branch[MAX_HEIGHT] = {0};
int num_branch = 0;
/* まだノードが一つもない場合 */
if(root == NULL){
/* 根ノードとしてノードを追加 */
root = mallocNode(number, name);
if(root == NULL){
printf("malloc error\n");
return NULL;
}
return root;
}
/* 根ノードから順に追加する場所を探索 */
node = root;
while(1) {
if(number < node->number){
/* 追加する値がノードの値よりも小さい場合 */
if(node->left == NULL){
/* そのノードの左の子が無い場合（もう辿るべきノードが無い場合）*/
/* その左の子の位置にノードを追加 */
node->left = mallocNode(number, name);
/* 追加完了したので処理終了 */
break;
}
/* 左ノードを辿ったことを覚えておく */
branch[num_branch] = TREE_LEFT;
num_branch++;
/* 左の子がある場合は左の子を新たな注目ノードに設定 */
node = node->left;
} else if(number > node->number){
/* 追加する値がノードの値よりも大きい場合 */
if(node->right == NULL){
/* そのノードの右の子が無い場合（もう辿るべきノードが無い場合）*/
/* その右の子の位置にノードを追加 */
node->right = mallocNode(number, name);
/* 追加完了したので処理終了 */
break;
}
/* 右ノードを辿ったことを覚えておく */
branch[num_branch] = TREE_RIGHT;
num_branch++;
/* 右の子がある場合は右の子を新たな注目ノードに設定 */
node = node->right;
} else {
/* 追加する値とノードの値が同じ場合 */
printf("%d already exist\n", number);
break;
}
}
return balancing(root, root, NULL, 0, branch, num_branch);
}
/* searchNode:指定されたnumberを持つノードを探索する
引数１ root : 探索を開始するノードのアドレス
引数２ number : 探索する会員番号
返却値 : number を持つノードのアドレス（存在しない場合は NULL）*/
struct node_t *searchNode(struct node_t *root, int number){
struct node_t *node;
node = root;
/* 探索を行うループ（注目ノードがNULLになったら終了 */
while(node){
if(number < node->number){
/* 探索値がノードの値よりも小さい場合 */
/* 注目ノードを左の子ノードに設定 */
node = node->left;
} else if(number > node->number){
/* 探索値がノードの値よりも大きい場合 */
/* 注目ノードを右の子ノードに設定 */
node = node->right;
} else {
/* 探索値 = ノードの値の場合 */
return node;
}
}
/* 探索値を持つノードが見つからなかった場合 */
return NULL;
}
/* deleteNoChildeNode:指定された子の無いノードを削除する
引数１ root : 木の根ノードのアドレス
引数２ node : 削除するノードのアドレス
引数３ parent：削除するノードの親ノードのアドレス
返却値 : 根ノードのアドレス */
struct node_t *deleteNoChildNode(struct node_t *root, struct node_t *node, struct node_t *parent){
if(parent != NULL){
/* 親がいる場合（根ノード以外の場合）は
削除対象ノードを指すポインタをNULLに設定 */
if(parent->left == node){
/* 削除対象ノードが親ノードから見て左の子の場合 */
parent->left = NULL;
} else {
/* 削除対象ノードが親ノードから見て右の子の場合 */
parent->right = NULL;
}
free(node);
} else {
/* 削除対象ノードが根ノードの場合 */
free(node);
/* 根ノードを指すポインタをNULLに設定 */
root = NULL;
}
return root;
}
/* deleteOneChildeNode:指定された子が一つのノードを削除する
引数１ root : 木の根ノードのアドレス
引数２ node : 削除するノードのアドレス
引数３ child : 削除するノードの子ノードのアドレス
返却値 : 根ノードのアドレス */
struct node_t *deleteOneChildNode(struct node_t *root, struct node_t *node, struct node_t * child){
/* 削除対象ノードにその子ノードのデータとポインタをコピー */
node->number = child->number;
strcpy(node->name, child->name);
node->left = child->left;
node->right = child->right;
/* コピー元のノードを削除 */
free(child);
return root;
}
/* deleteTwoChildeNode:指定された子が二つのノードを削除する
引数１ root : 木の根ノードのアドレス
引数２ node : 削除するノードのアドレス
返却値 : 根ノードのアドレス */
struct node_t *deleteTwoChildNode(struct node_t *root, struct node_t *node, int *branch, int *num_branch){
struct node_t *max;
struct node_t *maxParent;
/* 左の子から一番大きい値を持つノードを探索 */
max = node->left;
maxParent = node;
/* 左の子ノードを辿ったことを覚えておく */
branch[*num_branch] = TREE_LEFT;
(*num_branch)++;
while(max->right != NULL){
maxParent = max;
max = max->right;
/* 右の子ノードを辿ったことを覚えておく */
branch[*num_branch] = TREE_RIGHT;
(*num_branch)++;
}
printf("max number is %d\n", max->number);
/* 最大ノードのデータのみ削除対象ノードにコピー */
node->number = max->number;
strcpy(node->name, max->name);
/* 最大ノードを削除 */
/* maxは最大ノードなので必ずmax->rightはNULLになる */
if(max->left == NULL){
/* 最大ノードに子がいない場合 */
root = deleteNoChildNode(root, max, maxParent);
} else {
/* 最大ノードに子供が一ついる場合 */
root = deleteOneChildNode(root, max, max->left);
}
return root;
}
/* deleteNode:指定されたnumberを持つノードを削除する
引数１ root : 木の根ノードのアドレス
引数２ number : 削除する会員番号
返却値 : 根ノードのアドレス */
struct node_t *deleteNode(struct node_t *root, int number){
struct node_t *node;
struct node_t *parent;
int branch[MAX_HEIGHT] = {0};
int num_branch = 0;
if(root == NULL){
return NULL;
}
/* 削除対象ノードを指すノードを探索 */
node = root;
parent = NULL;
while(node != NULL){
if(number < node->number){
parent = node;
node = node->left;
/* 左の子ノードを辿ったことを覚えておく */
branch[num_branch] = TREE_LEFT;
num_branch++;
} else if(number > node->number){
parent = node;
node = node->right;
/* 右の子ノードを辿ったことを覚えておく */
branch[num_branch] = TREE_RIGHT;
num_branch++;
} else {
break;
}
}
/* 指定されたnumberを値として持つノードが存在しない場合は何もせず終了 */
if(node == NULL){
printf("%d を持つノードが存在しません\n", number);
return root;
}
printf("Delete %d(%s) node\n", node->number, node->name);
if(node->left == NULL && node->right == NULL){
/* 子がいないノードの削除 */
root = deleteNoChildNode(root, node, parent);
} else if((node->left != NULL && node->right == NULL) ||
(node->right != NULL && node->left == NULL)){
/* 子が一つしかない場合 */
if(node->left != NULL){
root = deleteOneChildNode(root, node, node->left);
} else {
root = deleteOneChildNode(root, node, node->right);
}
} else {
/* 左の子と右の子両方がいるノードの削除 */
root = deleteTwoChildNode(root, node, branch, &num_branch);
}
return balancing(root, root, NULL, 0, branch, num_branch);
}
/* printTree:rootを根ノードとする二分探索木をの全ノードを表示する
引数１ root : 木の根ノードのアドレス
引数２ depth: 関数呼び出しの深さ
返却値 : なし */
void printTree(struct node_t *root, int depth){
int i;
if(root == NULL){
return ;
}
/* 右の子孫ノードを表示 */
printTree(root->right, depth+1);
/* 深さをスペースで表現 */
for(i = 0; i < depth; i++){
printf(" ");
}
/* ノードのデータを表示 */
printf("+%3d(%s)\n", root->number, root->name);
/* 左の子孫ノードを表示 */
printTree(root->left, depth+1);
depth++;
}
int main(void){
struct node_t *root, *node;
int input;
int number;
char name[MAX_NAME_LEN];
int loop;
/* まだ木がないのでrootをNULLにセット */
root = NULL;
/* 最初にてきとうにノードを追加しておく */
root = addNode(root, 100, "100");
root = addNode(root, 200, "200");
root = addNode(root, 300, "300");
root = addNode(root, 50, "50");
root = addNode(root, 150, "150");
root = addNode(root, 250, "250");
root = addNode(root, 10, "1");
root = addNode(root, 125, "125");
root = addNode(root, 5, "5");
root = addNode(root, 25, "25");
root = addNode(root, 500, "500");
root = addNode(root, 175, "175");
root = addNode(root, 501, "501");
root = addNode(root, 502, "502");
root = addNode(root, 503, "503");
root = addNode(root, 504, "504");
root = addNode(root, 505, "505");
root = addNode(root, 506, "506");
root = addNode(root, 507, "507");
root = addNode(root, 508, "508");
root = addNode(root, 509, "509");
root = addNode(root, 510, "510");
loop = 1;
while(loop){
printf("処理を選択(1:add, 2:delete, 3:search, 4:exit)");
scanf("%d", &input);
switch(input){
case 1:
printf("会員番号(1 - 999):");
scanf("%d", &number);
if(number < 1 || number > 999){
printf("値が範囲外です\n");
continue;
}
printf("名前:");
scanf("%s", name);
root = addNode(root, number, name);
break;
case 2:
printf("会員番号(1 - 999):");
scanf("%d", &number);
if(number < 1 || number > 999){
printf("値が範囲外です\n");
continue;
}
root = deleteNode(root, number);
break;
case 3:
printf("会員番号(1 - 999):");
scanf("%d", &number);
if(number < 1 || number > 999){
printf("値が範囲外です\n");
continue;
}
node = searchNode(root, number);
if(node == NULL){
printf("number %d is not found\n", number);
} else {
printf("number %d : %s\n", number, node->name);
}
break;
default:
loop = 0;
break;
}
printTree(root, 0);
}
deleteTree(root);
return 0;
}プログラムの解説
基本は下記ページで紹介した２分探索木と同じものになっており、それを AVL 木向けに拡張しています。
C言語で二分探索木（木構造・ツリー構造）をプログラミング
ここでは上記ページの２分探索木のプログラムからの差分について解説していきます。
ノードの追加・削除
ノードを辿るで解説した通り、AVL 木ではノードの追加 / 削除の後に、その追加 / 削除したノードの親ノードまで辿れるようにしておく必要があります。
このためノードの追加・削除を行う addNode 関数と deleteNode 関数では、下記のように左ノードと右ノードのどちらを辿ってノードの追加位置・ノードの削除位置まで行き着いたかを配列 branch に記録するようにしています。
if(number < node->number){
/* 〜略〜 */
/* 左ノードを辿ったことを覚えておく */
branch[num_branch] = TREE_LEFT;
num_branch++;
/* 左の子がある場合は左の子を新たな注目ノードに設定 */
node = node->left;
} else if(number > node->number){
/* 追加する値がノードの値よりも大きい場合 */
/* 〜略〜 */
/* 右ノードを辿ったことを覚えておく */
branch[num_branch] = TREE_RIGHT;
num_branch++;
/* 右の子がある場合は右の子を新たな注目ノードに設定 */
node = node->right;
}また、これもノードを辿るで解説した通り、左右両方向に子ノードを持つノードの削除時には、実際に削除するノードの位置まで辿れるようにする必要があるため、deleteTwoChildNode 関数でも配列 branch に経路を記録するように変更しています。
木の高さの取得
平衡係数を計算する等で解説したように AVL 木で木を平衡に保つためには平衡係数が重要です。
さらにこの平衡係数を計算するためには、木の高さを計算する関数があると便利です。そのため getHeight 関数を用意し、引数 node で指定したノードを根ノードとした木の高さを取得できるようにしています。
平衡化処理
また balance 関数を追加し、この関数で下記の３つの処理を行っています。
- ノードを辿る
- 平衡係数を計算する
- 回転する
「ノードを辿る」はノードの追加・削除で作成した配列 branch に基づき、子ノードを辿っていく（balance 関数を再帰呼び出しする）ことで実現しています。
if (num_branch > 0) {
/* 辿れる場合はまず目的のノードまで辿る */
/* 辿る子ノードを設定 */
if (branch[0] == TREE_LEFT) {
next = node->left;
} else {
next = node->right;
}
/* 子ノードを辿る */
new_root = balancing(root, next, node, branch[0], &branch[1], num_branch - 1);
}「平衡係数を計算する」では木の高さの取得で用意した getHeight 関数を利用して平衡係数の計算を行っています。
/* 平衡係数を計算 */
left_height = getHeight(node->left);
right_height = getHeight(node->right);
balance = right_height - left_height;さらにこの平衡係数の値をチェックし、必要に応じて回転を行います。
この回転は、回転するで解説したように、平衡係数の値と２重回転を行う条件に当てはまるかどうかに応じて、左回転（leftRotate）・右回転（rightRotate）・２重回転（rightLeftRotate or leftRightRotate）の呼び分けを行います。
if (balance > 1) {
/* 右の部分木が高くて並行状態でない場合 */
/* ２重回転が必要かどうかを判断 */
if (getHeight(node->right->left) > getHeight(node->right->right)) {
/* ２重回転（Right Left Case）*/
return rightLeftRotate(new_root, node, parent, direction);
} else {
/*１重回転（左回転）*/
return leftRotate(new_root, node, parent, direction);
}
} else if (balance < -1) {
/* 左の部分木が高くて並行状態でない場合 */
/* ２重回転が必要かどうかを判断 */
if (getHeight(node->left->right) > getHeight(node->left->left)) {
/* ２重回転（Left Right Case）*/
return leftRightRotate(new_root, node, parent, direction);
} else {
/* １重回転（右回転）*/
return rightRotate(new_root, node, parent, direction);
}
}スポンサーリンク
まとめ
このページでは平衡２分探索木の１つである「AVL 木」の解説および「AVL 木」のC言語でのプログラム例の紹介・解説を行いました。
この「AVL 木」は２分探索木に下記の処理を行うように拡張することで実現することが可能です。
- ノードを辿る
- 平衡係数を計算する
- 回転する
AVL 木などの平衡２分探索木はデータ探索を効率的に行うのに適したデータ構造であり実用的です。また実際にプログラミングを行うことでポインタや再起処理の理解や実装力を高めることもできます。
是非この機会に AVL 木を含む平衡２分探索木の理解を深め、プログラミングにも挑戦してみてください！
