Binary Search Tree 二元搜尋樹

參考: http://squall.cs.ntou.edu.tw/cpp/103spring/labtest/test1/BinarySearchTree.html

介紹

(一)定義

為一種Binary Tree，若不為空則滿足 :

1. 左子樹所有Nodes之值均小於Root。
2. 柚子樹所有Nodes之值均大於Root。
3. 左右子樹亦是Binary Search Tree。

(二)利用B.S.T.進行有小到大之排序

Step1:
將input data建成B.S.T.
Step2:
對B.S.T.進行Inorder traversal即得出小$\rightarrow$大排序

相關函式及其程式碼

在Binary Search Tree的Struct已建構完畢之下，我們來介紹以下函式。

Search (搜尋資料)

此操作是藉由Binary Search Tree的特徵Data(L)<Data(V)<Data(R)，來判斷該向右走還是向左走。

程式碼

BST_Node* FindNode(BST_Node* root, int value){
	while(root!=NULL){
		if (root->data==value){
			return root;           /*若找到目標，則回傳此節點*/
		}
		else if (root->data>value){
			root = root->left;  /*若目標比此節點之data小，則向左移動*/
		}
		else{
			root = root->right; /*若目標比此節點之data大，則向右移動*/
		}
	}
	return NULL;     /*找不到*/

Insert (新增資料)

此函數的操作可以視為Search( )的延伸，先利用 Data(L)<Data(V)<Data(R) 的性質找到新增的節點適合的位置，在將新的節點接上Binary Search Tree。在尋找「適合的位置」時，會多假設一個節點(parent)來記錄目前所在位置(current)的父節點的位置，而在找到「適合的位置」後，在從父節點的位置接上新的節點。

程式碼

BST_Node* InsertNode(BST_Node* root, int val){
	BST_Node* newnode;
	BST_Node* current;
	BST_Node* parent;
	
	newnode = (BST_Node*)malloc(sizeof(BST_Node));
	newnode->data = val;
	newnode->left = NULL;
	newnode->right = NULL;
	if (root==NULL){
		return newnode;/*若為空，則回傳newnode當作Binary Search Tree的root*/
	}
	else{
		current = root;
		while(current!=NULL){/*藉由判斷val的大小，將current移動到適當的位置*/
			parent = current;
			if (current->data>val){
				current = current->left;
			}
			else{
				current = current->right;
			}
		}
               /*while()迴圈結束後，parent是在leaf的位置*/
		if (parent->data>val){
			parent->left = newnode;/*若val值較小，則將newnode接在parent的左子點*/
		}
		else{
			parent->right = newnode;/*若val值較大，則將newnode接在parent的右子點*/
		}
	}
	return root;
}

Delete (刪除資料)

此為Binary Search Tree的函式中最難的部分。
在Binary Search Tree上刪除資料，必須在刪除後依然符合 Data(L)<Data(V)<Data(R) 的性質，因此所有指向「欲刪除之節點」的pointer必須修改指向新的記憶體位置。另外，我們還需要再利用一個函式來找出「欲刪除之節點」的parent，而這個函式與尋找節點的函式非常相像，差別在於回傳其父節點。
以下根據「欲刪除之節點」的child pointer 個數分成三類：

• Case1. 沒有child pointer
• Case2. 只有一個child pointer
• Case3. 有兩個child pointer

Case1：沒有child pointer

只需要考慮原本指向此節點的父點parent，將其 left child/right child 指向NULL即可。

Case2：只有一個child pointer

假如「欲刪除之節點」有一個left child，則需要將其父點 parent 的 left child/right child 重新指向「欲刪除之節點」的 left child。

Case3：有兩個child pointer

須先從「欲刪除之節點」的左子樹中尋找最大值或是右子樹中尋找最小值作為取代點(假設此節點為X)，來取代「欲刪除之節點」的data，再來對於X進行刪除的動作。

• 左子樹尋找最大值的方法：不斷地向右移動，直到碰到NULL為止。

/*尋找欲刪除節點之父節點*/
BST_Node* FindParent(BST_Node* root, int value, int* pos){
	BST_Node *parent;
	parent = root;
	*pos = 0;           /*pos用來標記是向左移動還是向右移動*/
	while(root!=NULL){
		if (root->data == value){
			return parent;      /*找到目標，回傳此節點之父節點*/
		}
		else{
			parent = root;
			if (root->data > value){
				root = root->left;
				*pos=-1;     /*向左移動，並以*pos=-1表示*/
			}
			else{
				root = root->right;
				*pos =1;     /*向右移動，並以*pos=1表示*/
			}
		}
	}
	return NULL;         /*找不到，回傳NULL*/
}
/*刪除節點*/
BST_Node* DeleteNode(BST_Node* root, int value){
	BST_Node *parent;
	BST_Node *ptr;
	BST_Node *next;
	int pos;
	
	parent = FindParent(root, value, &pos);/*利用函式找出父節點*/
	if (parent!=NULL){
		switch(pos)                    /*判斷節點在父節點的哪裡*/
		{
			case -1:
				ptr = parent->left;
				break;
			case 1:
				ptr = parent->right;
				break;
			case 0:
				ptr = parent;
				break;
		}
		if (ptr->left==NULL){    /*若節點之左子節點為NULL*/
			if (parent == ptr){    /*父節點即為節點本身，即節點為root*/    
				root = root->right;     /*將root移向其右子節點*/
			}
			else{
				if (pos == 1){   
                                    /*欲刪除的節點在父節點右方,所以將父節點的右節點*/
                                    /*指向欲刪除節點的右節點*/
					parent->right = ptr->right;
				}
				else{
                                    /*欲刪除的節點在父節點左方,所以將父節點的左節點*/
                                    /*指向欲刪除節點的左節點*/
					parent->left = ptr->right;
				}
			}
			free(ptr);
		}
		else if (ptr->right==NULL){
			if (parent == ptr){
				root = root->left;
			}
			else{
				if (pos==1){
                                    /*欲刪除的節點在父節點右方,所以將父節點的右節點*/
                                    /*指向欲刪除節點的左節點*/
					parent->right = ptr->left;
				}
				else{
                                    /*欲刪除的節點在父節點左方,所以將父節點的左節點*/
                                    /*指向欲刪除節點的左節點*/
					parent->left =ptr->left; 
				}
			}
			free(ptr);
		}
		else{/*欲刪除節點有左右子樹*/
			parent = ptr;
			next = ptr->left;/*從欲刪除節點之左子樹中尋找最大值之取代點*/
			while(next->right!=NULL){
				parent = next;
				next = next->right;
			}
			ptr->data = next->data;/*取代!*/
			if (parent == ptr){/*取代點之父節點即為欲刪除點，表示取代點無右子樹*/
				ptr->left = next->left;
			}
			else{
				parent->right = next->left;/*將取代點之左子樹接上其父節點的右方*/
			}
			free(next);
		}
	}
	return root;
} 

Sort (排序資料)

由於Binary Search Tree具有Data(L)<Data(V)<Data(R) 之特性，只要利用Inorder Traversal的方式，即可得到由小到大的排序。

void inorder_traversal(BST_Node* root){
	if (root != NULL){
		inorder_traversal(root->left);
		printf(" %d",root->data);
		inorder_traversal(root->right);
	}
}

範例

最後，將以上所有函式利用下面的範例來做總結：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//建構Binary Search Tree的Structure
struct binary_search_tree{
	int data;
	struct binary_search_tree *left;
	struct binary_search_tree *right; 
}; 
typedef struct binary_search_tree BST_Node;

void inorder_traversal(BST_Node* root){
	if (root != NULL){
		inorder_traversal(root->left);
		printf(" %d",root->data);
		inorder_traversal(root->right);
	}
}

BST_Node* InsertNode(BST_Node* root, int val){
	/*略*/
}

BST_Node* FindParent(BST_Node* root, int value, int* pos){
	/*略*/
}

BST_Node* DeleteNode(BST_Node* root, int value){
	/*略*/
} 

int main(){
    int i;
    int data[] = {10, 20, 5, 8, 30, 15, 3, 18, 2, 1};
    int ndata = sizeof(data)/sizeof(int);
    BST_Node *head = NULL;

    for (i=0; i<ndata; i++)          /*建立Binary Search Tree*/
        head = InsertNode(head, data[i]);

    printf("In order listing:\n");   /*輸出Inorder Traversal之排序*/
    inorder_traversal(head);
    printf("\n");
    assert(FindNode(head, 15));      /*assert判斷是否有錯誤，如果有錯，立即中止程式*/
    assert(!FindNode(head, 11));
    head = DeleteNode(head,5);       /*刪除節點5*/
    printf("After delete the node 5:\n");
    inorder_traversal(head);         /*輸出Inorder Traversal之排序*/
    return 0;
}

結果如下：