Part 1 准备工作(2022/7/30更新)
Part 2 BST的检索与插入 将于2022/7/31更新
第一部分 BST的定义(来自于AcWing3595)
二叉排序树,也称为二叉查找树。
可以是一颗空树,也可以是一颗具有如下特性的非空二叉树:
- 若左子树非空,则左子树上所有节点关键字值均不大于根节点的关键字值;
- 若右子树非空,则右子树上所有节点关键字值均不小于根节点的关键字值;
- 左、右子树本身也是一颗二叉排序树。
说白了,就是这样:
但在竞赛中,为了方便,假设BST中没有相同元素
第二部分 BST的建立
明白了BST长啥样,那怎么来建立呢?
为了减少对边界的判断,可以先插入一个无穷大,和一个无穷小
这也就是BST的初始化
建立这两个节点的代码如下
struct BST
{
int l,r; //左、右孩子的编号
int val; //节点保存的数据
}a[N];
int tot,root,INF=1<<30; //tot:节点个数;root:树根;INF:无穷大
int New(int val) //建立新节点
{
a[++tot].val=val; //赋值
return tot; //返回节点编号,方便父节点访问
}
void Build() //初始化两个节点
{
root=New(-INF); //根节点为负无穷大
a[root].r=New(INF); //根节点的右孩子为正无穷大
}