二叉搜索树并查集

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
  
   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
   
    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
    
     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）查询俩个元素是否是同一个组，就是查找俩个元素的根是否相同。相同：是一组；不同：不是一组代码实现：

#include 
  
   

using namespace std;
const int MAX = 100;
int par[MAX],rank[MAX];

void init(int n){
    for(int i=0;i

二叉搜索树 并查集

BST：二叉搜索树

（1）查找

（2）插入

（3）删除

并查集