树——二叉搜索树

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\),查找其右子树