二叉查找树BST

Binary Search Tree

· BST是一棵数据域有序的树,其左子树上的所有结点的数据域均小于或等于根结点的数据域,右子树上所有结点的数据域均大于根结点的数据域,即其中序遍历是有序的。

二叉查找树的基本操作

1.查找操作

和普通二叉树的查找不同,二叉查找树可根据数据域的比较对左右子树选择递归

1
2
3
4
5
6
7
8
9
10
11
void search(node* root,int x){
if(root==NULL){
printf("search failed\n");
return;
}
if(x==root->data){
printf("%d\n",root->data);
}else if(x<root->data){
search(root->lchild);
}else search(root->rchild);
}

2.插入操作

查找失败的地方一定是结点需要插入的地方,在上述代码中修改:root==NULL条件下建立以带插入值为数据域的新结点。
注意:因为要插入结点而非单纯读取数据,所以要用引用。

1
2
3
4
5
6
7
8
9
10
11
12
void insert(node* &root,int x){
if(root==NULL){
node* root=new node;
root->data=x;
root->lchild=root->rchild=NULL;
return;
}
if(x==root->data) return;
else if(x<root->data){
insert(root->lchild,x);
}else insert(root->rchild,x);
}

3.二叉查找树的建立

即为插入n个结点的过程
注:即便是同一组数字,插入他们的顺序不同,最后生成的二叉查找树也不同。

1
2
3
4
5
6
node* create(int data[],int n){
node* root=NULL;
for(int i=0;i<n;i++)
insert(root,data[i]);
return root;
}

4.二叉查找树的删除

· BST中比结点权值小的最大结点称为该结点的前驱,前驱是该结点左子树中的最右结点
· BST中比结点权值大的最小结点称为该结点的后继,后继是该结点右子树中的最左结点

1
2
3
4
5
6
7
8
9
10
11
12
//寻找以root为根结点的树中的最大权值结点
node* findMax(node* root){
while(root->rchild!=NULL)
root=root->rchild;
return root;
}
//寻找以root为根结点的树中的最小权值结点
node* findMin(node* root){
while(root->lchild!=NULL)
root=root->lchild;
return root;
}

删除操作的基本思路:
1)如果当前结点root值为空,则不存在权值为给定权值的结点,直接返回
2)如果当前结点root的权值恰为给定权值x,则进入删除处理:
a)如果当前结点root不存在左右子树,说明是叶子节点,直接删除
b)如果当前结点root存在左子树,那么在左子树中寻找前驱pre,然后让pre的数据覆盖root,接着在左子树中删除结点pre
c)如果当前结点root存在右子树,那么在右子树中寻找后继next,然后让next的数据覆盖root,接着在右子树中删除next
3)如果当前root的权值大于给定x,则在左子树中递归删除权值为x的结点
4)如果当前root的权值小于给定x,则在右子树中递归删除权值为x的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//删除以root为根结点的树中权值为x的结点
void deleteNode(node* &root,int x){
if(root==NULL) return;
if(root->data==x){
if(root->lchild==NULL&&root->rchild==NULL){
root=NULL;
}else if(root->lchild!=NULL){
node* pre=findMax(root->lchild);
root->data=pre->data;
deleteNode(root->lchild,pre->data);
}else{
node* next=findMin(root->rchild);
root->data=next->data;
deleteNode(root->rchild,next->data);
}
}else if(root->data>x){
deleteNode(root->lchild,x);
}else deleteNode(root->rchild,x);
}

注意:总是优先删除前驱(或者后继)容易导致树的左右子树高度极不平衡,使得二叉树退化成一条链。两种解决办法:每次交替删除前驱或后继;记录子树高度,总是优先在高度较高的一棵子树里删除结点。

【笔记,摘自胡凡《算法笔记》】