二叉搜索树

树——二叉搜索树

Date:2023.1.14

定义

二叉搜索树是一棵二叉树，具有以下定义：

• 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。

• 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。

• 二叉搜索树的左右子树均为二叉搜索树。

一些操作

先看变量：

lc_x：x点的左儿子

rc_x：x点的右二子

val_x：x点的值

cnt_x：x点值的数量

siz_x：x点子树的数量

插入

向树中插入一个值

递归插入

1. 与当前节点比较，若权值小于它，加入左子树，反之加入右子树

2. 若当前点权值与插入值一样，当前点 cnt + +

3. 若当前节点为空，将节点设为当前节点

插入时注意更新变量

不要忘记更新父节点的儿子

删除

在树中删除一个值

1. 先在树中查找该值节点

2. 设改点为 x，分类讨论

   1. 若 cnt_x > 1，将 cnt_x − −

   2. 若 cnt_x = 1

      1. 若该点是叶子节点（没有儿子），删除该节点

      2. 若该点只有一个儿子，返回它的儿子

      3. 若该点有两个儿子，返回左子树的最大值或右子树的最小值

查找最大/最小值

查最小值一直往左儿子跳

查最大值一直往右儿子跳

查找排名为 k 的元素

设当前节点为 x，分类讨论

1. 若其左子树大小  ≥ k，查找其左子树

2. 若其左子树大小在 k − cnt_x到k − 1中，返回x

3. 若其左子树大小  < k − cnt，查找其右子树