二叉搜索树

二叉搜索树是能够高效地进行如下操作的数据结构

1.插入一个数值

2.查询是否包含某个数值

3.删除某个数值

所有的节点，都满足左子树上的所有节点都比自己的小，而右子树上的所有节点都比自己大这一条件

如果有n个元素，平均每次操作需要O(log n)的时间

实现：

 1 #include<bits/stdc++.h>
 2 #define INF 10000000
 3 using namespace std;
 4 struct node{
 5     int val;
 6     node *lch,*rch;
 7 };
 8 //插入数值x
 9 node *insert(node *p,int x)
10 {
11     if(p==NULL)
12     {
13         node *q=new node;
14         q->val=x;
15         q->lch=q->rch=NULL;
16         return q;
17     }
18     else
19     {
20         if(x<p->val) p->lch=insert(p->lch,x);
21         else p->rch=insert(p->rch,x);
22         return p;
23     }
24 }
25 //查找数值x
26 bool find(node *p,int x)
27 {
28     if(p==NULL) return false;
29     else if(x==p->val) return true;
30     else if(x<p->val) return find(p->lch,x);
31     else return find(p->rch,x);
32 }
33 //删除数值x
34 node *remove(node *p,int x)
35 {
36     if(p==NULL) return NULL;
37     else if(x<p->val) p->lch=remove(p->lch,x);
38     else if(x>p->val) p->rch=remove(p->rch,x);
39     //需要删除的节点没有左儿子，把右儿子提上去
40     else if(p->lch==NULL)
41     {
42         node *q=p->rch;
43         delete p;
44         return q;
45     }
46     //需要删除的节点的左儿子没有右儿子，把左儿子提上去
47     else if(p->lch->rch==NULL)
48     {
49         node *q=p->lch;
50         q->rch=p->rch;
51         delete p;
52         return q;
53     }
54     //以上两种情况都不满足，把左儿子的子孙中最大的节点提到需要删除的节点上
55     else
56     {
57         node *q;
58         for(q=p->lch;q->rch->rch!=NULL;q=q->rch);
59         node *r=q->rch;
60         q->rch=r->lch;
61         r->lch=p->lch;
62         r->rch=p->rch;
63         delete p;
64         return r;
65     }
66     return p;
67 }
68 int main()
69 {
70     node *root=NULL;
71     root=insert(root,2);
72     insert(root,1);
73     insert(root,3);
74     insert(root,7);
75     cout<<find(root,5)<<endl;
76     return 0;
77 }

View Code

c++中的STL里有set和map容器，实现了二叉搜索树。set是使用二叉搜索树维护集合的容器，map是维护键和键对应的值的容器。

在向二叉树插入节点时，如果以1，2，3，4，5.。。的顺序插入的话二叉树会变得如同一条链表一样（退化的二叉树）。

如果按照这个顺序插入，树的高度就会变成n。则操作由O(log n)变为O(n)。

而平衡二叉树通过旋转操作来保持树的平衡以避免退化情况的发生。编程语言标准中的二叉搜索树都很好地实现了平衡二叉树。