首页 > 代码库 > 二叉搜索树 并查集
二叉搜索树 并查集
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 = http://www.mamicode.com/x;>
并查集
并查集是一种高效管理元素分组的一种数据结构，并查集可以进行合并操作，但是不能进行分割操作。并查集的每一组代表着一棵树。
进行的操作：
查询元素是否是同一个组；
合并不同组的元素。
（1）初始化:
最开始的时候，准备n个点表示n个元素，一开始不存在边。
（2）从一组的根向另一个组的根连边，合并一起（记录树的高度（rank），rank小的向大的连边）
（3）查询俩个元素是否是同一个组，就是查找俩个元素的根是否相同。相同：是一组； 不同：不是一组
代码实现：
#include <iostream>
using namespace std;
const int MAX = 100;
int par[MAX],rank[MAX];
void init(int n){
for(int i=0;i<n;i++){
par[i] = i;//没有边
rank[i] = 0;
}
}
int find(int x){
if(par[x]==x)
return x;
else
return par[x] = find(par[x]);
}
void unite(int x,int y){
x = find(x);
y = find(y);
if(x==y) return;
if(rank[x]<rank[y]){
par[x] = y;
}else{
par[y] = x;
if(rank[x]==rank[y]){
rank[x]++;
}
}
}
bool same(int x,int y){
return find(x) == find(y);
}
二叉搜索树 并查集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。