二叉搜索树并查集

时间：2014-10-31 20:42:25 收藏：0 阅读：250

BST：二叉搜索树

二叉搜索树的特点：左孩子<根节点<右孩子

二叉搜索树可以有效的管理数的集合

（1）查找

查找数值，大于根节点向右查找，小于根节点向做查找，递归直到找到或者找不到为止。

（2）插入

类似于查找，找到相应的位置之后，将那个位置插入新的节点即可。

（3）删除

删除就稍微的复杂一点：

需要删除的点没有左孩子，直接将右孩子提上去

需要删除的点的左孩子没有右孩子，直接将左孩子提上去

除此之外，将左孩子的子孙的最大节点提上去。

代码实现：

struct node{
    int data;
    node* lch,*rch;
};
node* insert(node* p,int x){
    if(p==NULL){
        node* q = new node;
        q->data = x;
        q->lch = q->rch = NULL;
        return q;
    }else{
        if(x<p-data) p->lch = (p->lch,x);
        else p->rch = insert(p->rch,x);
        return p;
    }
}
bool find(node* p,int x){
    if(p==NULL) return false;
    if(x<p->data) return find(p->lch,x);
    else if(x==p->data) return true;
    else return find(p->rch,x);
}
node* remove(node* p,int x){
    //分三种情况考虑
    if(p==NULL) return NULL;
    else if(x<p->data) p->lch = remove(p->lch,x);
    else if(x>p->data) 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;
    }
}

并查集

并查集是一种高效管理元素分组的一种数据结构，并查集可以进行合并操作，但是不能进行分割操作。并查集的每一组代表着一棵树。

进行的操作：

查询元素是否是同一个组；

合并不同组的元素。

（1）初始化:

最开始的时候，准备n个点表示n个元素，一开始不存在边。

（2）从一组的根向另一个组的根连边，合并一起（记录树的高度（rank），rank小的向大的连边）

（3）查询俩个元素是否是同一个组，就是查找俩个元素的根是否相同。相同：是一组；不同：不是一组