二叉搜索树

· · 个人记录

省流：上午学 whk 去了啥也没干。

学笛卡尔树发现看不懂，又回来学平衡树了，发现还是看不懂，然后被迫学习这个没啥用的东西/kk

二叉搜索树

简介

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

  1. 空树是二叉搜索树。

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

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

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

以上摘自 OI Wiki。

性质

一共有两个：

  1. 全局最小值一定在左链的顶点，最大值一定在右链顶线。

    证明最小值在左链顶点：感性理解一下就好了，如果不在左链，那么至少走一次右子树，走到右子树显然不可能成为全局最优。

    证毕。证明最大值在右链顶点同理。

  2. 中序遍历是权值单调不降的序列。

    证明：中序遍历是 左->根->右，我们发现左子树中所有的数都比根节点小，右子树中所有的数都比根节点大，所以递归下去显然最后得到单调不降的序列。

操作

  1. insert(o,v)：在以 o 为根节点的二叉搜索树中插入一个值为 v 的新节点。

    操作方法：

    若 o 的权值和 v 相等，那么 o 出现的次数加一。

    若 o 的权值小于 v，那么往右子树扔。

    否则往左子树扔。

    时间复杂度 O(h)。

  2. delete(o,v)：在以 o 为根节点的二叉搜索树中删除一个值为 v 的节点。

    操作方法：

    首先找到这个 v 在哪里。

    如果是叶子结点直接删掉就好了。如果不是叶子结点就要拿其他的节点替代。如果有一个儿子，我们换成它的儿子即可，对答案没啥影响。同理如果有两个儿子，那么换成左子树最大/右子树最小即可，对答案也没啥影响。时间复杂度 O(h)。

  3. 求元素的排名

    元素的排名取决于它左子树大小。所以每次如果往右跳就加上左子树大小。最后加上终点左子树大小就是答案。时间复杂度 O(h)。

  4. 求排名为 k 的元素

    和线段树树上二分一毛一样。每次假设 f(o,k) 是在以 o 为根的子树中找排名为 k 的，那么看一下左子树大小（假设是 sze_l，同时假设值和 o 相同的有 c_o 个），如果 sze_l \geq k，那么往左子树找，即 f(ls_o,k)。否则，如果不在这个点上（即 k-sze_l-cnt_o>0），那么就往右子树找，即 f(rs_o,k-sze_l-cnt_o)。时间复杂度 O(h)。

这种数据结构除了给平衡树做铺垫，真的有意义学习吗/yiw