データ構造学習ノート＜5＞二分探索木と平衡二分木

一、二分探索木#

1. 二分探索木とは#

二分探索木（BST、Binary Search Tree)、または二分ソート木または二分検索木は、空であることもできる二分木であり、空でない場合は以下の性質を満たします：

非空の左部分木のすべてのキー値はその根ノードのキー値より小さい
非空の右部分木のすべてのキー値はその根ノードのキー値より大きい
左、右部分木はすべて二分探索木である

2. 二分探索木の操作関数#

(1) 二分探索木の検索操作 Find#

検索する値は X

根ノードから検索を開始し、木が空であれば NULL を返す
検索木が空でない場合、X と根ノードのキー値を比較し、以下の処理を行う
1. X が根ノードのキー値より小さい場合、左部分木で検索
2. X が根ノードのキー値より大きい場合、右部分木で検索
3. X が根ノードのキー値と等しい場合、検索完了、そのノードを指すポインタを返す

尾再帰実装#

Position Find(ElementType X, BinTree BST) {
	if( !BST ) return NULL;//検索失敗
	if( X > BST->Data )
		return Find(X, BST->Right);//操作1
	else if (X < BST->Data) 
		return Find(X, BST->Left); //操作2
	else 
		return BST; //操作3 検索成功
}

反復関数実装#

Position Find(ElementType X, BinTree BST) {
	while(BST) {
		if (X > BST->Data)
			BST = BST->Right;//操作1
		else if (X < BST->Data)
			BST = BST->Left;//操作2
		else 
			return BST;//操作3 検索成功
	}
	return NULL;//検索失敗
}

(2) 最大要素と最小要素の検索#

最大要素は必ず木の最右分岐の端ノードにある
最小要素は必ず木の最左分岐の端ノードにある

最大要素の検索#

再帰関数

Position FindMin(BinTree BST) {
	if (!BST ) return NULL;//空木、NULLを返す
	else if ( !BST->Left )
		return BST;	//最左葉ノードを見つけた
	else 
		return FindMin(BST->Left);//左分岐を沿って検索を続ける
}

反復関数

Position FindMin(BinTree BST) {	
	if (BST) {
		while (BST->Left)	BST = BST->Left;
	}
	return BST;
}

最小要素の検索#

再帰関数

Position FindMax(BinTree BST) {
	if (!BST ) return NULL;//空木、NULLを返す
	else if ( !BST->Right )
		return BST;	//最左葉ノードを見つけた
	else 
		return FindMin(BST->Right);//右分岐を沿って検索を続ける
}

反復関数

Position FindMax(BinTree BST) {	
	if (BST) {
		while (BST->Right)	BST = BST->Right;
	}
	return BST;
}

(3) 二分探索木の挿入#

挿入後も二分探索木であることを保証するためには、要素を挿入すべき位置を見つけることが重要です。

BinTree Insert(ElementType X, BinTree BST) {
	if(!BST) {	//元の木が空であれば、1ノードの二分探索木を生成して返す
		BST = malloc(sizeof(struct TreeNode));
		BST->Data = X;
		BST->Left = BST->Right = NULL;
	} else {	//挿入する要素の位置を探し始める
		if (X < BST->Data)
			BST->Left = Insert(X, BST->Left);
		else if (X > BST->Data)
			BST->Right = Insert(X, BST->Right);
		else printf("この値はすでに存在します"); 
	}
	return BST;
}

(4) 二分探索木の削除#

三つのケースを考慮する

削除するのが葉ノードの場合：直接削除し、その親ノードのポインタを修正
削除するノードが子ノードを一つだけ持つ場合：その親ノードのポインタを削除するノードの子ノードに指す
削除するノードが左、右の二つの子木を持つ場合：削除するノードを別のノードで置き換える（右部分木の最小要素または左部分木の最大要素）

BinTree Delete(ElementType X, BinTree BST) {
	Position Tmp;
	if(!BST) printf("削除する要素が見つかりませんでした");
	else if (X < BST->Data) 
		BST->Left = Delete(X,BST->Left);
	else if (X > BST->Data) 
		BST->Right = Delete(X,BST->Right);
	else {	//削除するノードを見つけた
		if (BST->Left && BST->Right) {	//削除するノードが左右二つの子を持つ
			Tmp = FindMin(BST->Right);	//右部分木で最小の要素を見つけて削除ノードを埋める
			BST->Data = Tmp->Data;
			BST->Right = Delete(BST->Data,BST->Right);//埋めた後、右部分木でその最小要素を削除
		}
		else {	//削除するノードが1つまたは子ノードを持たない
			Tmp = BST;
			if (!BST->Left) //子ノードが1つまたは持たない
				BST = BST->Right;
			else if (!BST->Right)
				BST = BST->Left;
			free(Tmp);
		}
	}
	return BST;
}

二、平衡二分木#

1. 平衡二分木とは#

平衡二分木（AVL 木、Banlanced Binary Tree）は、空であることもできるが、空でない場合は以下の性質を満たします：

任意のノードの左、右部分木の高さの差の絶対値は 1 を超えない
与えられたノード数 nの AVL 木の ** 最大高さは O (log~2~n)** である！

平衡因子（BF,Banlanced Factor）：BF (T) = h~L~-h~R~、h~L~ と h~R~ はそれぞれ T の左、右部分木の高さ

2. 平衡二分木の調整#

RR 挿入 ——RR 回転【右単回転】#

破壊ノード（問題のノード）は、破壊ノード（発見者）の右部分木の右部分木に位置します
ここに画像の説明を挿入

LL 挿入 ——LL 回転【左単回転】#

破壊ノード（問題のノード）は、破壊ノード（発見者）の左部分木の左部分木に位置します
ここに画像の説明を挿入

LR 挿入 ——LR 回転#

破壊ノード（問題のノード）は、破壊ノード（発見者）の左部分木の右部分木に位置します
ここに画像の説明を挿入

RL 挿入 ——RL 回転#

破壊ノード（問題のノード）は、破壊ノード（発見者）の右部分木の左部分木に位置します
ここに画像の説明を挿入

ps：時には要素を挿入する際に構造を調整する必要がなくても、いくつかの平衡因子を再計算する必要があることがあります#

3. 平衡二分木の実装#

定義部分#

typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode {
	ElementType Data;
	AVLTree Left, Right;
	int Height;
};
int Max(int a, int b) {
	return a>b?a:b;
}

左単回転#

psは必ず左子ノード B を持ち、A と B を左単回転し、A と B の高さを更新して新しい根ノード B を返します

AVLTree SingleLeftRotation(AVLTree A) {
	AVLTree B = A->Left;
	A->Left = B->Right;
	B->Right = A;
	A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
	B->Height = Max( GetHeight(B->Left),A->Height ) + 1;
	return B;
}

右単回転#

psは必ず右子ノード B を持ち、A と B を右単回転し、A と B の高さを更新して新しい根ノード B を返します

AVLTree SingleRightRotation(AVLTree A) {
	AVLTree B = A->Right;
	A->Right = B->Left;
	B->Left = A;
	A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
	B->Height = Max( A->Height, GetHeight(B->Right) ) + 1;
	return B;
}

LR 回転#

psは必ず左子ノード B を持ち、B は必ず右子ノード C を持ちます
まず B と C を右単回転し、C を返します
次に A と C を左単回転し、C を返します

AVLTree DoubleLeftRightRotation(AVLTree A) {
	A->Left = SingleRightRotation(A->Left);
	return SingleLeftRotation(A);
}

RL 回転#

psは必ず右子ノード B を持ち、B は必ず左子ノード C を持ちます
まず B と C を左単回転し、C を返します
次に A と C を右単回転し、C を返します

AVLTree DoubleRightLeftRotation(AVLTree A) {
	A->Right = SingleLeftRotation(A->Right);
	return SingleRightRotation(A);
}

挿入#

X を AVL 木 T に挿入し、調整された AVL 木を返します

AVLTree Insert(AVLTree T,ElementType X) {
	if (!T) {	//挿入する木が空であれば、ノードXを含む新しい木を作成
		T = (AVLTree) malloc(sizeof(struct AVLNode));
		T->Data = X;
		T->Height = 0;
		T->Left = T->Right = NULL;
	} else if( X < T->Data) {
		T->Left = Insert(T->Left, X);
		if (GetHeight(T->Left)-GetHeight(T->Right) == 2) {//左回転が必要
			if (X < T->Left->Data)
				T = SingleLeftRotation(T);	//左単回転が必要
			else 
				T = DoubleLeftRightRotation(T);//左-右二重回転
		}
	} else if (X > T->Data) {
		T->Right = Insert(T->Right, X);
		if (GetHeight(T->Left)-GetHeight(T->Right) == -2) {//右回転が必要
			if (X > T->Right->Data)
				T = SingleRightRotation(T);	//右単回転が必要
			else 
				T = DoubleRightLeftRotation(T);//右-左二重回転
		}
	}
	//木の高さを更新
	T->Height =  Max( GetHeight(T->Left),GetHeight(T->Right) ) + 1;
	return T;
}

完全なコードデモ#

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode {
	ElementType Data;
	AVLTree Left, Right;
	int Height;
};
int Max(int a, int b) {
	return a>b?a:b;
}
int GetHeight(AVLTree A) {
    if (A)
        return A->Height;
    else 
        return 0;
}
AVLTree SingleLeftRotation(AVLTree A) {//左単回転
	AVLTree B = A->Left;
	A->Left = B->Right;
	B->Right = A;
	A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
	B->Height = Max( GetHeight(B->Left),A->Height )+ 1;
	return B;
}
AVLTree SingleRightRotation(AVLTree A) {//右単回転
	AVLTree B = A->Right;
	A->Right = B->Left;
	B->Left = A;
	A->Height = Max( GetHeight(A->Left),GetHeight(A->Right) ) + 1;
	B->Height = Max( A->Height, GetHeight(B->Right) ) + 1;
	return B;
}
AVLTree DoubleLeftRightRotation(AVLTree A) {//左-右二重回転
	A->Left = SingleRightRotation(A->Left);
	return SingleLeftRotation(A);
}
AVLTree DoubleRightLeftRotation(AVLTree A) {//右-左二重回転
	A->Right = SingleLeftRotation(A->Right);
	return SingleRightRotation(A);
}
AVLTree Insert(AVLTree T,ElementType X) {//XをAVL木Tに挿入
	
	if (!T) {	//挿入する木が空であれば、ノードXを含む新しい木を作成
		T = (AVLTree) malloc(sizeof(struct AVLNode));
		T->Data = X;
		T->Height = 0;
		T->Left = T->Right = NULL;
        
	} else if( X < T->Data) {
		T->Left = Insert(T->Left, X);
		if (GetHeight(T->Left)-GetHeight(T->Right) == 2) {//左回転が必要
			if (X < T->Left->Data)
				T = SingleLeftRotation(T);	//左単回転が必要
			else 
				T = DoubleLeftRightRotation(T);//左-右二重回転
		}
	} else if (X > T->Data) {
		T->Right = Insert(T->Right, X);
		if (GetHeight(T->Left)-GetHeight(T->Right) == -2) {//右回転が必要
			if (X > T->Right->Data)
				T = SingleRightRotation(T);	//右単回転が必要
			else 
				T = DoubleRightLeftRotation(T);//右-左二重回転
		}
	}
	//木の高さを更新
	T->Height =  Max( GetHeight(T->Left),GetHeight(T->Right) ) + 1;
    return T;
}
void PreOrderTraversal(AVLTree T) {
	if(T) {
		printf("%d", T->Data);
		PreOrderTraversal( T->Left);
		PreOrderTraversal( T->Right);
	}
}
void InOrderTraversal(AVLTree T) {
	if(T) {
		InOrderTraversal( T->Left);
		printf("%d", T->Data);
		InOrderTraversal( T->Right);
	}
}
int main() {
    AVLTree T = NULL;
    int i;
    for (i = 1; i < 10; i++) {
        T = Insert(T,i);
    }
    PreOrderTraversal(T);//前順遍歴
    printf("\n");
    InOrderTraversal(T);//中順遍歴
    return 0;
}

出力結果：

421365879
123456789

前順遍歴と中順遍歴から、次のような平衡二分木を再構築できます

ここに画像の説明を挿入

三、同じ二分探索木かどうかの判断#

問題意：挿入シーケンスが与えられた場合、唯一の二分探索木を決定し、入力されたさまざまな挿入シーケンスが同じ二分探索木を生成できるかどうかを判断します

二つのシーケンスが同じ検索木に対応しているかどうかを判断する方法は？
木を構築し、他のシーケンスがその木と一致するかどうかを判別します！
例えば、入力 3 1 4 2 で一つの二分探索木を決定し、3 4 1 2 と 3 2 4 1 が同じ木に対応しているかどうかを判断します

1. 検索木の表現#

typedef struct TreeNode *Tree;
struct TreeNode {
	int v;
	Tree Left,Right;
	int flag;	//このノードがすでに検索されたかどうかを示すためのフラグ、1であれば検索済み
};

2. 検索木 T の構築#

Tree MakeTree(int N) {
	Tree T;
	int i, V;
	scanf("%d", &V);
	T = NewNode(V);
	for(i = 1; i < N; i++) {
		scanf("%d",&V);
		T = Insert(T,V);//残りのノードを二分木に挿入
	}
	return T;
}

Tree NewNode(int V) {
	Tree T = (Tree)malloc(sizeof(struct TreeNode));
	T->v = V;
	T->Left = T->Right = NULL;
	T->flag = 0;
	return T;
}

Tree Insert(Tree T, int V) {
	if(!T) T = NewNode(V);
	else {
		if (V > T->v) 
			T->Right = Insert(T->Right, V);
		else 
			T->Left = Insert(T->Left,V);
	}
	return T;
}

3. 一つのシーケンスが検索木 T と一致するかどうかを判別#

方法：木 T の中で順番にシーケンス 3 2 4 1 の各数を検索します

検索中に通過したノードがすべて前に検索済みであれば、一致します
そうでなければ（ある検索中に前に出会ったことのないノードに遭遇した場合）、一致しません

int check(Tree T,int V) {
	if(T->flag) {//この点はすでに検索済み、左部分木または右部分木を検索するかどうかを判断
		if(V < T->v) return check(T->Left,V);
		else if(V > T->v) return check(T->Right,V);
		else return 0;
	}
	else {	//検索するのがちょうどこの点で、マークを付ける
		if(V == T->v) {
			T->flag = 1;
			return 1;
		}
		else return 0; //以前に見たことのない点に遭遇した
	}
}

長さ N の挿入シーケンスが生成する木が検索木と一致するかどうかを判断

int Judge(Tree T,int N) {
	int i, V, flag = 0;//flag=0は現在一致していることを示し、1であればすでに一致していないことを示す
	scanf("%d",&V);
	if (V != T->v) flag = 1;
	else T->flag = 1;
	for(i = 1; i < N; i++) {
		scanf("%d", &V);
		if( (!flag) && (!check(T,V)) ) flag = 1;
	}
	if(flag) return 0;
	else return 1;
}

T の各ノードのフラグマークを 0 にリセット

void ResetT(Tree T) {
	if(T->Left) ResetT(T->Left);
	if(T->Right) ResetT(T->Right);
	T->flag = 0;
}

T のメモリを解放

void FreeTree(Tree T) {
	if(T->Left) FreeTree(T->Left);
	if(T->Right) FreeTree(T->Right);
	free(T);
}