树——二叉搜索树

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. 若其左子树大小 \(\ge k\)，查找其左子树

  2. 若其左子树大小在 \(k-cnt_x到k-1\)中，返回\(x\)

  3. 若其左子树大小 \(<k-cnt\)，查找其右子树