二叉搜索树

二叉搜索树的结构

• 插入一个数值
• 查询是否包含某个数值
• 删除某个数值

储存方式

二叉搜索树的例子

所有节点都满足，左子树上的所有节点都比自己小，而右子树上的所有节点都比自己大。
eg.可以通过如下方法在上图的二叉搜索树中查询是否存在10

• 根节点的数值是7，比10小，向右儿子节点走。
• 走到的节点数值为15，比10大，向左儿子节点走。
• 然后就到10啦
   

插入新值

插入6

 

删除数值

删除15

一般来说，需要根据下面几种情况分别进行处理

• 需要删除的节点没有左儿子，那么就把右儿子提上去
• 需要删除的节点没有右儿子，那么就把左儿子提上去
• 以上两种情况都不满足的话，就把左儿子的子孙中最大的节点但提到需要删除的节点上。
   

二叉搜索树的复杂度

不论哪一种操作，所花的时间都和树的高度成正比。因此，如果共有n个元素，那么平均每次操作需要的时间为O(logn)的时间
 

二叉搜索树的实现

下面是二叉搜索树的一种实现方法

node *root=NULL;
root=insert(root,1);
find(root,1);

像代码中一样，我们使用函数的返回值进行操作。需要注意的是insert。delete但会的是node结构体的指针

struct node{
    int val;
    node *lch,*rch;
};

//插入数值x
node *insert(node *p,int x){
    if(p==NULL){
        node*q=new node;//新建
        q->val=x;
        q->lch=q->rch=NULL;
        return q; 
    }else{
        if(x<p->val)
            p->lch=insert(p->lch,x);
        else
            p->rch=insert(p->rch,x);
        return p;
    }
}

//查找数值x
bool find(node*p,int x){
    if(p==NULL)
        return false;
    else if(x==p->val)
        return true;
    else if(x<p->val)
        return find(p->lch,x);
    else
        return find(p->rch,x); 
} 

//删除数值
node *remove(node *p,int x){
    if(p==NULL)
        return NULL;
    else if(x<p->val)
        p->lch=remove(p->lch,x);
    else if(x>p->val)
        p->rch=remove(p->rch,x);
    else if(p->lch==NULL){
        node *q=p->rch;
        delete p;
        return q;
    }
    else if(p->lch->rch==NULL){
        node *q=p->lch;
        q->rch=p->rch;
        delete p;
        return q;
    }
    else{
        node *q;
        for(q=p->lch;q->rch->rch!=NULL;q=q->rch);
        node *r=q->rch;
        q->rch=r->lch;
        r->lch=p->lch;
        r->rch=p->rch;
        delete p;
        return r;
    }
    return p;
} 

 
 

编程语言的标准库

和堆一样，实际上在许多情况下都不需要自己实现二叉搜索树。许多编程语言都子啊标准库里实现了简单易用的二叉搜索树。例如在C++中，STL里有set和map容器。set是像前面所说的一样使用二叉搜索树维护集合的容器，而map则是维护键和键对应的值的容器。
下面是一些使用set和map的例子。
set容器

• begin()返回指向第一个元素的迭代器
• clear()--清除所有元素
• count()--返回某个值元素的个数
• empty()--如果集合为空，返回true
• end()--返回指向最后一个元素的迭代器
• equal_range()--返回集合中与给定值相等的上下限的两个迭代器
• erase()--删除集合中的元素
• find()--返回一个指向被查找到元素的迭代器
• get_allocator()--返回集合的分配器
• insert()--在集合中插入元素
• lower_bound()--返回指向小于（或等于）某值的第一个元素的迭代器
• upper_bound()--返回大于某个值元素的迭代器
• key_comp()--返回一个用于元素间值比较的函数
• max_size()--返回集合能容纳的元素的最大限值
• rbegin()--返回指向集合中最后一个元素的反向迭代器
• rend()--返回指向集合中第一个元素的反向迭代器
• size()--集合中元素的数目
• swap()--交换两个集合变量
• value_comp()--返回一个用于比较元素间的值的函数

#include<cstdio>
#include<set>
using namespace std;

int main(){
    //声明；
    set<int> s;
    
    //插入元素；
    s.insert(1);
    s.insert(3);
    s.insert(5);
    
    //查找元素
    set<int>::iterator ite;
    ite=s.find(1);
    if(ite==s.end())
        puts("not found");
    else
        puts("found");
        
    ite=s.find(2);
    if(ite==s.end())
        puts("not found");
    else
        puts("found");
        
    //删除元素
    s.erase(3);
    if(s.count(3)!=0)
        puts("found");
    else
        puts("not found");
    
    //遍历所有元素
    for(ite=s.begin();ite!=s.end();ite++){
        printf("%d\n",*ite);
    } 
    return 0;
}

 
 
map容器

#include<cstdio>
#include<map>
#include<cstring>
using namespace std;

int main(){
    //声明（int为键，const char*为值）
    map<int,const char*> m;
    
    //插入元素
    m.insert(make_pair(1,"ONE"));
    m.insert(make_pair(10,"TEN"));
    m[100]="HUNDRED";
    
    //查找元素
    map<int,const char*>::iterator ite;
    ite=m.find(1);
    puts(ite->second);//输出ONE；
    
    ite=m.find(2);
    if(ite==m.end())
        puts("not found");
    else
        puts(ite->second);
        
    puts(m[10]);
    
    //删除元素
    m.erase(10);
    
    //遍历一遍所有元素
    for(ite=m.begin();ite!=m.end();ite++){
        printf("%d:%s\n",ite->first,ite->second);
    } 
    return 0;
}