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

1.插入一个数值

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

3.删除某个数值

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

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

实现：

1 #include
      
        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     else19     {20         if(x
       
        val) p->lch=insert(p->lch,x);21         else p->rch=insert(p->rch,x);22         return p;23     }24 }25 //查找数值x26 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
        
         val) return find(p->lch,x);31     else return find(p->rch,x);32 }33 //删除数值x34 node *remove(node *p,int x)35 {36     if(p==NULL) return NULL;37     else if(x
         
          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     else56     {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<
          
           <
          
         
        
       
      

 

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

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

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

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