什麼是二叉搜索樹?
一棵二叉樹的節點x，如果y是x左子樹中的一個節點，那麼y.key<x.key.如果y是x右子樹中的一個節點，那麼y.key>x.key
二叉樹的數據結構
[cpp]
typedef int data_t;
typedef struct BST
{
data_t data;
struct BST *left;
struct BST *right;
struct BST *parent;
}BST;
typedef int data_t;
typedef struct BST
{
data_t data;
struct BST *left;
struct BST *right;
struct BST *parent;
}BST;
二叉搜索樹的遍歷
我們可以通過一個簡單的遞歸算法按序輸出二叉搜索樹中的所有關鍵字，這種算法稱為中序遍歷，類似的，先序遍歷輸出的根的關鍵字在其左右子樹的關鍵字之間，後續遍歷輸出根的值在其左右子樹的值之後
以下為二叉樹的中序遍歷的遞歸算法與非遞歸算法
[cpp]
void bst_nonrecur_inorder(BST *root)//use stack to store tree's node
{
stack<BST *> s_bst;
while(s_bst.size() || root!=NULL)
{
if(root!=NULL)
{
s_bst.push(root);
root = root->left;
}
else
{
root = s_bst.top();
s_bst.pop();
cout << root->data << " ";
root = root->right;
}
}
}
void bst_inorder(BST *root)
{
if(root==NULL)
return ;
else
{
bst_inorder(root->left);
cout << root->data << " ";
bst_inorder(root->right);
}
}
void bst_nonrecur_inorder(BST *root)//use stack to store tree's node
{
stack<BST *> s_bst;
while(s_bst.size() || root!=NULL)
{
if(root!=NULL)
{
s_bst.push(root);
root = root->left;
}
else
{
root = s_bst.top();
s_bst.pop();
cout << root->data << " ";
root = root->right;
}
}
}
void bst_inorder(BST *root)
{
if(root==NULL)
return ;
else
{
bst_inorder(root->left);
cout << root->data << " ";
bst_inorder(root->right);
}
}
注意：如果x是一棵n個結點字樹的根，那麼遍歷該樹需要O(n)時間
二叉樹的查詢
我們經常需要查找一個存儲在二叉搜索樹中的關鍵字。除了search操作之外，還支持諸如minnum,maxinum,successor(求後繼節點),predecessor(前驅結點)的查詢操作
樹的查找
輸入指向樹根節點的指針和一個關鍵字k，如果這個檢點存在，bst_search返回一個指向關鍵字k的節點的指針，否則返回NULL
下面為樹查找的遞歸實現與迭代實現
[cpp]
//search a node in the binary-search-tree
BST *bst_search(BST *root, data_t data)
{
if(root==NULL || root->data== data)
return root;
if(data<root->data)
return bst_search(root->left, data);
else
return bst_search(root->right, data);
}
BST *bst_iterative_search(BST *root, data_t data)
{
if(root==NULL || root->data == data)
return root;
while(root!=NULL && data!=root->data)
{
if(data<root->data)
root = root->left;
else if(data>root->data)
root = root->right;
}
return root;
}
//search a node in the binary-search-tree
BST *bst_search(BST *root, data_t data)
{
if(root==NULL || root->data== data)
return root;
if(data<root->data)
return bst_search(root->left, data);
else
return bst_search(root->right, data);
}
BST *bst_iterative_search(BST *root, data_t data)
{
if(root==NULL || root->data == data)
return root;
while(root!=NULL && data!=root->data)
{
if(data<root->data)
root = root->left;
else if(data>root->data)
root = root->right;
}
return root;
}
最大關鍵字元素和最小關鍵字元素
從樹根開始沿著left孩子指針，直到遇到一個一個節點的left指針為NULL，那麼該節點的值就是該二叉搜索樹的最小關鍵字。同理，從樹根沿著right孩子指針，直到遇到一個節點的right指針為NULL為止，那麼該節點的值就是該二叉搜索樹的最大關鍵字
以下為實現代碼
[cpp]
//return the minnest node of tree
BST *bst_mininum(BST *root)
{
if(root == NULL)
return NULL;
while(root->left!=NULL)
root = root->left;
return root;
}
//return the maxest node of tree
BST *bst_maxinum(BST *root)
{
if(root == NULL)
return NULL;
while(root->right!=NULL)
root = root->right;
return root;
}
//return the minnest node of tree
BST *bst_mininum(BST *root)
{
if(root == NULL)
return NULL;
while(root->left!=NULL)
root = root->left;
return root;
}
//return the maxest node of tree
BST *bst_maxinum(BST *root)
{
if(root == NULL)
return NULL;
while(root->right!=NULL)
root = root->right;
return root;
}
注，以上兩個算法的時間復雜度都是O(logn) (n為輸得節點的個數)
節點的前驅和後繼
給定一棵二叉搜索樹的一個節點，有時候需要按中序遍歷的次序查找它的後繼。如果所有的關鍵字互不相同，則一個節點x的後繼是大於x.key的最小關鍵字的節點。
查找前驅過程分為兩部分：1. 如果x的右子樹非空，那麼x的後繼則是x右子樹的最左節點；2. 如果x的右子樹為空且有一個後繼節點y，那麼y就是最底層祖先並且其左孩子也是一個祖先。為了找到y，只需從x開始沿樹而上知道遇到一個其雙親有左孩子的節點
查找節點的前驅則先判斷x節點的左子樹是否為空，非空則前驅就是左子樹的最右節點，空則從x沿樹而上直到遇到一個其雙親都有右孩子的節點，那麼該節點就是x的前驅結點
下面為實現代碼
[cpp]
BST *bst_successor(BST *node)
{
if(node == NULL)
return NULL;
if(node->right!=NULL) //find successor in the leftest of the right subtree
return bst_mininum(node->right);
//else find it a node leftSubTree from his parent
BST *y = node->parent;
while(y!=NULL && node==y->right)
{
node = y;
y = y->parent;
}
return y;
}
BST *bst_predecessor(BST *node)
{
if(node == NULL)
return NULL;
if(node->left!=NULL)
return bst_maxinum(node->left);
BST *y = node->parent;
while(y!=NULL && node==y->left)
{
node = y;
y = y->parent;
}
return y;
}
BST *bst_successor(BST *node)
{
if(node == NULL)
return NULL;
if(node->right!=NULL) //find successor in the leftest of the right subtree
return bst_mininum(node->right);
//else find it a node leftSubTree from his parent
BST *y = node->parent;
while(y!=NULL && node==y->right)
{
node = y;
y = y->parent;
}
return y;
}
BST *bst_predecessor(BST *node)
{
if(node == NULL)
return NULL;
if(node->left!=NULL)
return bst_maxinum(node->left);
BST *y = node->parent;
while(y!=NULL && node==y->left)
{
node = y;
y = y->parent;
}
return y;
}
樹的插入與刪除
樹的插入與刪除操作會引起二叉搜索樹表示的動態集合的變化，一定要修改數據結構來反映這個變化，但修改要保持二叉樹搜索樹的性質的成立
插入
要將一個新值插入到一棵二叉搜索樹T中，需要調用bst_insert。該函數以關鍵字v作為輸入，在函數構造節點node，並將node->left=NULL,node->right=NULL
插入過程為：從樹根開始，指針node記錄一條向下的簡單路錦，並查找要替換新節點insert的NULL，該遍歷保持tmo作為node的雙親
[cpp]
//insert a node into a binary-search-tree
BST *bst_insert(BST *root, data_t data)
{
BST *insert = NULL, *node = NULL, *tmp = NULL;
insert = bst_newnode(data); //make a node to insert
node = root;
while(node) //find pos to insert
{
tmp = node;
if(data < node->data)
node = node->left;
else
node = node->right;
}
insert->parent = tmp;
if(tmp==NULL) //tree root is empty
root = insert;
else
{
if(data < tmp->data)
tmp->left = insert;
else
tmp->right = insert;
}
return root;
}
//insert a node into a binary-search-tree
BST *bst_insert(BST *root, data_t data)
{
BST *insert = NULL, *node = NULL, *tmp = NULL;
insert = bst_newnode(data); //make a node to insert
node = root;
while(node) //find pos to insert
{
tmp = node;
if(data < node->data)
node = node->left;
else
node = node->right;
}
insert->parent = tmp;
if(tmp==NULL) //tree root is empty
root = insert;
else
{
if(data < tmp->data)
tmp->left = insert;
else
tmp->right = insert;
}
return root;
}
樹的刪除
從一個二叉搜索樹T中刪除一個節點z，這個過程取決與指向root和待刪除節點node，以下為該過程的四種情況
1. 如果node沒有左孩子，那麼有其右孩子來替換node，這個右孩子可以是NULL，也可以不是
2. 如果node僅有一個節點且該節點是左孩子，那麼用其左孩子來替換node
3. 否則node既有一個左孩子又有一個右孩子，我們要查找node的後繼y，這個後繼位於node的右子樹中並且沒有左孩子，現在需要將y移除原來的位置進行拼接，並替換樹中的node
3.1. 如果y是z的node的右孩子，那麼用y替換node
3.2 否則，y位於z的右子樹中但並不是z的右孩子，這種情況下，先用y的右孩子替換y，然後用y替換node(最後步驟同3.1)
為了在二叉搜索樹內移動子樹，定義一個函數bst_transplant,它用涼意可子樹替換一棵字數並成為雙親的孩子節點。以下實現為用一棵以v為根的子樹來替換一棵以u為根的子樹，節點u的雙親就變為節點v的雙親，並且最後v成為u的雙親的相應孩子
[cpp]
<PRE class=cpp name="code">//replace subtree of u with subtree of v
BST *bst_transplant(BST *root, BST *u, BST *v)
{
if(u->parent==NULL) //u is root
root = v;
else if(u->parent->right == u) // u is his parent's right subtree
u->parent->right = v;
else u->parent->left = v; //u is his parent's left subtree
if(v!=NULL) //set v's parent
v->parent = u->parent;
return root;
}</PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
[cpp]
//replace subtree of u with subtree of v BST *bst_transplant(BST *root, BST *u, BST *v) { if(u->parent==NULL) //u is root root = v; else if(u->parent->right == u) // u is his parent's right subtree u->parent->right = v; else u->parent->left = v; //u is his parent's left subtree if(v!=NULL) //set v's parent v->parent = u->parent; return root; } //replace subtree of u with subtree of v
BST *bst_transplant(BST *root, BST *u, BST *v)
{
if(u->parent==NULL) //u is root
root = v;
else if(u->parent->right == u) // u is his parent's right subtree
u->parent->right = v;
else u->parent->left = v; //u is his parent's left subtree
if(v!=NULL) //set v's parent
v->parent = u->parent;
return root;
}
樹的刪除代碼如下
[cpp]
BST *bst_delete(BST *root, data_t data)
{
BST *node = NULL, *y = NULL;
node = bst_search(root, data); //find the deleted node
if(node==NULL)
return NULL;
if(node->left == NULL) //case 1
root = bst_transplant(root, node, node->right);
else if(node->right == NULL) //case 2
root = bst_transplant(root, node, node->left);
else
{
y = bst_mininum(node->right); //find node's successor
if(y->parent!=node) //case 3 follow make y's parent to node
{
root = bst_transplant(root, y, y->right);
y->right = node->right;
node->right->parent = y;
}
//case 3 y->parent == node
root = bst_transplant(root, node, y);
y->left = node->left;
y->left->parent = y;
}
return root;
}
BST *bst_delete(BST *root, data_t data)
{
BST *node = NULL, *y = NULL;
node = bst_search(root, data); //find the deleted node
if(node==NULL)
return NULL;
if(node->left == NULL) //case 1
root = bst_transplant(root, node, node->right);
else if(node->right == NULL) //case 2
root = bst_transplant(root, node, node->left);
else
{
y = bst_mininum(node->right); //find node's successor
if(y->parent!=node) //case 3 follow make y's parent to node
{
root = bst_transplant(root, y, y->right);
y->right = node->right;
node->right->parent = y;
}
//case 3 y->parent == node
root = bst_transplant(root, node, y);
y->left = node->left;
y->left->parent = y;
}
return root;
}
