BST
二叉搜索树(BST),也可以叫做二叉排序树
BST树始终满足四个要求
- 左结点的值小于父结点
- 右结点的值大于右结点
- 没有权值相同的结点
- 每一个结点的左右子树也满足二叉排序树
BST暴力搜索最坏的情况时间复杂度是O(n ^ 2)
接下来讲的主要是最普遍的二叉搜索树
初始化
先定义一个全局遍历nnum
代表每一个结点的下标
在开始之前我们需要为每一个结点定义属性
每一个结点需要值(val)
左孩子(ls)
右孩子(rs)
重复情况使用记录出现次数(cnt)
用来记录排名(siz)
struct node{ int ls;int rs;int val;int cnt;int siz; };
|
插入结点
参数部分
我们既然想要插入一定需要将跟结点传入
从根结点出发去查找合适的位置
接着传入插入的值
判断
三种情况
插入的结点等于当前结点
插入结点大于当前结点
插入结点小于当前结点
完整代码
void add(int now,int v) { t[now].siz++; if(t[now].val == v) { t[now].cnt++; return; } if(t[now].val < v) { if(t[now].rs == 0) { nnum++; t[nnum].cnt = 1;t[nnum].siz = 1; t[nnum].val = v; t[now].rs = nnum; }else { add(t[now].rs,v); }
}else { if(t[now].ls == 0) { nnum++; t[nnum].val = v; t[nnum].cnt = 1;t[nnum].siz = 1; t[now].ls = nnum; }else { add(t[now].ls,v); } } }
|
查找元素的前驱结点的值
int findPre(int now,int val,int ans) { if(t[now].val >= val) { if(t[now].ls == 0) return ans; else return findPre(t[now].ls,val,ans); }else { if(t[now].rs == 0) { if(ans == -INF) return t[now].val; else return ans; }
return findPre(t[now].rs,val,t[now].val); }
}
|
查找元素的后继结点的值
int findLast(int now,int val,int ans) { if(t[now].val <= val) { if(t[now].rs == 0) return ans; else return findLast(t[now].rs,val,ans); }else { if(t[now].ls == 0) { if(ans == INF) return t[now].val; else return ans; }
return findLast(t[now].ls,val,t[now].val); } }
|
按值查排名
int frank(int now,int x) { if(x == 0) return 0; if(t[now].val == x) return t[t[now].ls].siz;
if(x < t[now].val) return frank(t[now].ls,x); return frank(t[now].rs,x) + t[t[now].ls].val + t[now].cnt; }
|
按排名查值
int fval(int now,int rank) { if(now == 0) return INF; if(t[t[now].ls].siz >= rank) { return fval(t[now].ls,rank); }
if(t[t[now].ls].siz + t[now].cnt >= rank) { return t[now].val; }
return fval(t[now].rs,rank - t[t[now].ls].siz - t[now].cnt); }
|