二叉搜索树(BST)

二叉搜索树-邓俊辉

线性结构的优劣

• 线性结构：元素之间都有一个自然的线性次序

  • 基于数组的实现

    • 优点：常数时间内查找
    • 缺点：线性时间内移动(插入，删除)

  • 基于链表的实现

    • 有点：常数时间内移动
    • 缺点：线性时间内查找

• 如何中和两种的优缺点 ——> 树结构(半线性结构)

---

树结构的特点和解决的问题

• 半线性结构(semi-linear structure)

  • 非线性性质在于：并不直接存在天然的直接后继和直接前驱关系

    譬如说：某个节点的前面是什么，后面是什么这个并不是唯一确定的。

    而是取决于遍历方式：前序遍历、中序遍历、后序这些。

  • 线性性质在于：附加某种约束(遍历)，也可以在树中的元素之间确定某种线性次序，譬如前面说的几种遍历。

• 分层结构：树的层次化特征蕴含于所有事物及其联系中，成为本质属性之一。

• 树解决的问题：希望以一种“折中”的方式来同时满足一定效率下的动态****增删和静态改查。

‍

---

搜索树家族概览

搜索树家族要解决的问题

搜索树家族主要用于在不同的场景下解决如下问题：

• 高效率的动态增删
• 高效率的静态改查

总结：增删改查实际上是“增删”和“改查”。是两个不是四个。

这个是从结构上的破坏性上来讲。

搜索树家族的成员

于是下面就是具体的数据结构。

• • 树家族

    • 其他树

    • 二叉树(BinTree)

      • 普通二叉树

      • 二叉搜索树(BST)

        • 普通二叉搜索树

        • 平衡的二叉搜索树

          • AVL树
          • 伸展树(Splay)
          • 红黑树(RedBlack)

    • 多路树

      • 普通多路树

      • 平衡的多路树

        • 普通B树
        • B+树
        • Kd-Tree

• 书这里有一个简单的图可以看：

  ​​

• 总结：这边的重点都是放在​平衡****上。原因在下面的板子上：

  平衡的树是N点节点所能组成的高度最低的树。

  总结： {: parent-style=”background-color: var(–b3-font-background7);”}一层只搜一个节点，因此：效率<=>树高。

---

查找的概念

• 关键词：查找、搜索，是一回事儿 —— search

• 查找的单元：

  • 数据对象 —— 词条(entry)，譬如商品销售记录

    • 词条包括：

      • 关键码 (Key)

        • 譬如商品的扫描码

      • 值 (值)

        • 譬如商品的单价、库存量

      • 所以，关键码和值之间并没有很强的逻辑关系，只是人为地建立起来的一种对应。

• 循关键码访问：

  • 特点：这种访问方式，与数据对象的物理位置或逻辑次序均无关系。只比对关键码。

    其实，按照我的理解，物理位置和逻辑次序也是一种关键码。但是，既然这里专门提到了关键码，那么按照我的理解就是专门在上一层的抽象中提到了这个问题。

  • 循：遵循

  • 关键码：一种可以比较的对象，譬如编号，常见的各种类型的编号，一般具有唯一标识的特点。

  • 同类概念：

    • 循秩访问
    • 循位置访问

• 可查找的隐含假定：

  • 所有的词条entry构成一个全序关系，可以相互比对和比较。

总结：循关键码查找，逻辑位置无关，物理位置无关。所以才能用树这种数据结构。

---

二叉搜索树

注意：二叉搜索树满足顺序性，不满足平衡性。但是光顺序性也已经是很重要的性质了。

在对节点的增删中已经需要额外的注意了。

• 二叉搜索树和其他的树比较起来有很强的顺序性约束。

  • 正因为有顺序，所以才能搜索。
  • 如果是无规则，那么直接暴力遍历即可，搞什么搜索？

• 基本概念和定理：

  • 任一节点r的左（右）子树中，所有节点（若存在）均不大于（不小于）r。—— 包含等值的边界条件。
  • 任何一棵二叉树是二叉搜索树，当且仅当其中序遍历序列单调非降。

总结：二叉搜素树强调顺序性，中序单调非降。

‍

一个小困惑：

在其模板类定义中，如何理解这里面的connect34​：

​​

‍

二叉搜索树查找算法的思想

• 查找算法的思路和策略是：

  • 减而治之

  • 从树根出发，逐步地缩小查找范围，直到发现目标(成功)或缩小至空树(失败)。

  • 因此，在查找过程中，一旦发现当前节点为NULL​，即说明查找范围已缩小至空。也就是查找失败。

    • 这个算是查找的一个边界条件，从这个角度来理解是很不错的。
    • **当前节点可以看作是当前查找范围**的一个入口。

• 查找算法是插入和删除算法的前置步骤。

• 在查找算法中一个常见的思路是：把空节点(也就是空孩子指针)假想地等效为“真实”节点。这些空节点也称作外部节点。

  • 因为查找么，无非就是查到和没查到，那么没查到怎么办，那么就用空节点来表示没有查到。

总结：查找的本质就是缩小查找范围。那么，在给定的范围下，如何高效地缩小范围呢，这个很重要。

• 线性结构是逐元素的：-1, -1, -1来逐步地缩小范围。
• 二分查找是一次一半儿的：-0.5N, -0.5*0.5N 这种来逐步地缩小范围。
• 树查找就不仅仅是1/2的系数了，可能是1/n的量。

---

二叉搜索树查找实现的语义约定——“命中等效性”

• 思想就是：尽可能地等效处理所有“情况”

• 这边查找的语义约定就是：

  • 视外部节点为真实存在的节点

    • 在代码层面，那两个指针位也确实存在，叶子节点也是具有“左右孩子的成员变量的”。

    • 这个逻辑就是，外部节点类似座位，那个座位本身是存在的，只不过座位上没人。

    • 那么查找的逻辑就是：

      • 找到了“座位”，也找到了“人” —— 命中节点。
      • 找到了“座位”，没有找到人 —— 节点没有命中。

  • 同时迭代保存当前节点e和其父节点 _hot：

    • 这么做便于后面的插入和删除

总结：视外部节点为存在的节点。这个思想就是把命中和没命中抽象成同一种对象，然后根据对象中具体的属性来做区分。这样做的好处是，便于代码的区分处理。

二叉搜索树查找的效率和瓶颈—— 查找树的高度

• 基本事实：

  • 在二叉搜索树的每一层，查找算法至多访问一个节点，且只需常数时间，故总体所需时间应线性正比于查找路径的长度，或最终返回节点的深度。

  • 对于节点数规模为N的二叉搜索树：

    • 最好情况：O(1)

    • 最坏情况：O(N)

      • 树退化为单链

• 树的查找效率瓶颈和优化思路：

  • 在于最坏情况下的效率优化。

  • 那么，结合二叉搜索树查找时候的基本事实

    • 若要控制单次查找在最坏情况下的运行时间，须从控制二叉搜索树的高度入手。

总结： 一层只搜一个节点，因此：效率<=>树高。

二叉搜索树插入算法的思想

• 两步走

  • 查找到位置，插入。
  • 调整子树高。

• 思路拆解：

  • 如何保持和查找算法的一致性呢——也就是尽量能够复用代码。

    • 同时迭代保存当前节点e和其父节点 _hot：

      • 这么做便于后面的插入和删除

  • 插入 = 查找 + 新建-更新 + （调整树结构）

    • 查找：对于一个要插入的节点$e_1 $，转换成在树中查找$e_1$，那么返回得到的两个变量$e$ 和$_hot$ 就分别是要插入的位置和该位置的父节点。这一点就是很重要的。
    • 新建-更新：然后在位置上新建节点，更新这个树维护的一些全局的元信息，包括当前节点的高度(深度)等等，甚至更激进一点，保留它的父节点的位置。
    • 调整树高度：对于普通的树结构是不需要调整树结构的，为了维持平衡性也就是查找效率，需要调整树结构。

总结：在查找算法中，我们希望

二叉搜索树插入算法的效率：—— 取决于查找算法的效率

注意：这边的效率说的是在非平衡的二叉树中。

• 开销主要取决于： 查找 + 元信息更新

  • 二者都取决于树的深度
  • 最坏情况下不超过全树的高度

总结：在非平衡树的场景中，插入算法的效率取决于查找算法的效率。

二叉搜索树删除算法及其实现

• 首先仍然是运行查找算法来确定要删除的位置。

• 单分支的删除

  • 场景：对于要删除的节点$e_1$，它或者只有左子树, 其前驱节点为$e_0$；或者只有右子树，其后继节点为$e_2$。

  • 基本事实：任一节点r的左（右）子树中，所有节点（若存在）均不大于（不小于）r。基本事实确定了有序性也强调了有序性，这个是二叉搜索树的核心。

  • 删除步骤：

    1. 把孩子子树（即孩子节点）（无论是左子树，还是右子树）替换到它本来的位置，则拓扑意义上的节点删除即告完成。

    2. 要更新节点的高度信息。

       1. 如果是高度的话，从_hot​节点往上进行所有兄弟姐妹父母祖先的更新。
       2. 如果是深度的话，这个操作就方便很多了。直接顺着_hot​往下走进行兄弟姐妹子孙的更新就可以了。
       3. 无论是使用高度还是使用深度，都是基于递归可以实现的，这一点可以注意一下。

• 双分支的删除

  • 场景：对于要删除的节点$e_1$，它的左孩子即其前驱节点为$e_0$；它的右孩子即其后继节点为$e_2$。

  • 方案A：以后继$e_2 $代替被删

    • 步骤：

      1. 查找到节点e

  • 方案B：以前驱$e_0$代替被删

    • 步骤：

      1. xxx

• 关于选择前驱节点还是后继节点

  ​​

总结：

1. 关于高度的更新，无论是深度还是高度，都是可以采取递归的方式进行。

   我之前的思维误区是：对于高度，我需要傻乎乎地从头节点来暴力搞定。这个就是纯纯傻逼，多久没碰代码了这是。

2. ‍

‍

注意辨析二叉搜索树中几个节点的概念：

1. 前驱节点：

   • 在二叉搜索树中，给定节点的前驱节点是键值比该节点小的最大节点。

     • 如果该节点有左子树，那么前驱节点是其左子树中的最大节点。
     • ‍

2. 后继节点：

3. 父节点：

   • 这个很好理解，在这个环境中，就是那个_hot​。
   • 如果当前节点的值比父节点小，那么，它就是父节点的左孩子。
   • 如果当前节点的值比父节点大，那么，它就是父节点的右孩子。

4. 子节点：

   • 每个节点可以有两个子节点。
   • 左子都小于父，右子都大于父。

5. 左孩子节点(左子树的根节点)：

   • 左孩子节点是二叉树中某个节点的左子节点，它的键值小于其父节点的键值。

6. 右孩子节点(右子树的根节点)：

   • 右孩子节点是二叉树中某个节点的右子节点，它的键值大于其父节点的键值。

‍

非平衡的搜索树中：查找、删除、插入三者的关系

1. 查找最核心的一个观念是：包含空节点在内的等效命中。

   • 对于查找节点$e_1$的任务：

     • 第一种情况： 树里面有该关键字的节点：返回关键字为$e_1$的节点。
     • 第二种情况： 树里面没有该关键字的节点：返回空节点。

2. 插入是基于查找，给定要插入的节点$e_1$，期望得到的是查找的第一种情况。—— 得到存在的实际的节点。

3. 删除也是基于查找，给定要插入的节点$e_2$，期望得到的是查找的第二种情况。—— 返回外部节点，也就是实际上我要插入的位置。

插入和删除操作对维护搜索树顺序性的异同

1. 插入操作只有两种情况：

   1. 待插入节点已经存在，那么要么报一个警告，要么就什么也不管。
   2. 待插入节点不存在，那么，根据上面的命中等效性约定，返回来的是一个空节点，也就是要出入的地址。那么新插入的节点一定是一个叶子节点。

   所以，插入操作整体来说是很简单的方法。并且这两种情况，无论哪种都不会破坏原来树的顺序性。

2. 而删除操作就不一样了，也是有两种情况：

   1. 所删除的节点仅有独子

      XXXXXXXXXXXXXXXXX

   2. 所删除的节点有两个儿子

      XXXXXXXXXXXXXXXXX

   叶子节点，想要单独看也行，想要视为有两个儿子也行，想要视为仅有独子也行，都行。因为它处理起来很简单。

   论证：为什么叶子节点的删除不会破坏搜索树的顺序性。

‍

二叉搜索树的常用性质

‍

‍

这里简单的介绍一下二叉搜索树木的问题。