数据结构-搜索(一) 二叉搜索树

• 数据结构-搜索(一) 二叉搜索树,包括 python 源代码,及相关一部分证明

• 源码: https://github.com/Jasper-1024/python/tree/master/data_structure/search

• 更新

  19.03.18 初始
  19.04.03 基础库调整,摘要调整

• 参考资料

  https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000
  维基百科
  算法第四版,算法导论.

导语

• 本打算一章写完,二叉搜索树,2-3,红黑树的…粗略估算了一下代码和证明…嗯,二叉搜索树..
• 这一节主要是 二叉搜索树,及相关的证明
• 调试时候因为分析二叉树非常麻烦,下一篇2-3树延后,先去研究二叉树可视化了.
• 代码基本转译自算法第四版,证明来自算法导论.

基础库

• 对前面刷数据结构的代码,重新整理,清爽多了..

• /libs

  • BtNode 适配红黑树,增加颜色属性,移动到了/libs.
  • 把到处都是的 randoms 类,重新整理移动到了/libs.
  • 二叉树可视化的 prtree 也放到了/libs.
    • 修正了prtree传入none时的一个bug.
    • 添加了生成 gif 的方法,但因为 将 Graphviz 画出图的大小固定的设置还没搞定,生成的gif没法看..

• /ST

  • 搜索的基类重命名为 STclass
  • 在 __init__.py 中引用 /libs 下模块.
    • 因为 vscode python 调试,相对路径引用有问题,这里只能用绝对路径引用.

符号表

• 维基上的定义: 符号表是一种用于语言翻译器（例如编译器和解释器）中的数据结构。在符号表中，程序源代码中的每个标识符都和它的声明或使用信息绑定在一起，比如其数据类型、作用域以及内存地址.

• 在这里没有那么复杂,仅定义为储存键值对的数据结构,支持插入(put) 和 查找(get) 等操作.

• 这里约定查找部分的符号表为 ST ,有几种典型操作,各个部分需要自行实现(因可选的api较多,这里仅选典型几个).

  # 查找的基类
  class ST(object):
      # 查找
      def search(self, key):
          pass
  
      # 插入
      def insert(self, key, value):
          pass
  
      # 删除
      def delete(self, key):
          pass
  
      # 选择 返回排名k的key
      def select(self, k):
          pass
  
      # 排名 返回key的排名
      def rank(self, key):
          pass
  
      # 范围查找
      def keys(self, min, max):
          pass
  
      # 是否为空
      def isEmpty(self):
          pass

• 约定:

  • 每个键 key 只对应一个值(不允许重复).
  • 当键值相同时,新的值会替换旧的值
  • 健不为空,值不会空,(java中是 null ,python 中为 None),但在代码内未限制.
  • 这里约定,key为 int 类型.

• 性能测试:

  • 使用与快速排序相同的装饰器.
  • 随机生成超长数组,测试函数的执行时间.

• PS: 为方便实现,这里函数均为递归形式,实际项目中则基本都是循环形式.

二叉搜索树

• 二叉搜索树(Binary Search Tree),别名二叉查找树、有序二叉树、排序二叉树等.

  • 若任意节点的左子树不为空,则左子树的所有节点值小于根节点的值.
  • 若任意结点的右子树不为空,则右子树的所有结点值大于根节点的值.
  • 任意结点的左右子树也为二叉搜索树.
  • 键值没有重复.

• 相对于链表/无序数组实现的符号表,二叉搜索树的插入、搜索、删除的期望时间复杂度都是 $O(\log n)$ ,且支持动态查询.

• 当然最坏情况下其时间复杂度仍然为 $O(n)$ ,改进型的二叉搜索树例如 2-3树、红黑树等可以将最坏情况下时间复杂度降低到 $O(\log n)$.二叉搜索树作为这些数据结构的过度,这里回给出实现和时间复杂度的证明.

查找

• 查找的过程非常类似二叉树的遍历,只不过加入了比较过程.

• 实现:

  • 如果结点为空,返回
  • 如果键值与结点键值相同,返回结点的值
  • 如果键值小于节点键值,递归调用结点左子树
  • 如果键值大于结点键值,递归调用结点右子树

• 时间复杂度

  • 假设二叉搜索树的高度为 h .
  • 查找操作可以看作是由根节点向下延伸的单向简单路径.
  • 所以可以得出: 高度为h的二叉搜索树,查找的时间复杂度为 $O(h)$
  • 又在堆排序一节,证得 n 个结点的二叉树其高度最小为 $\log n$ ,最大高度为 $n$ (类似单向链表).
  • 所以可以得出: 高度为h的二叉搜索树,查找的时间复杂度最好为 $O(\log n)$,最坏为 $O(n)$

• 代码

  # 查找
  def search(self, key):
      return self.get(key, self.root)
  
  def get(self, key, node=None):
      # 找到以node为根节点的子树,返回key对应的值,不存在返回null
      if node is None:
          return None
      cmp = self.key_compare(key, node.key)
      if cmp < 0:
          return self.get(key, node.lchild)
      elif cmp > 0:
          return self.get(key, node.rchild)
      else:
          return node.value

插入

• 插入的整个过程也和查找类似.

• 步骤

  • 如果树为空,返回一个含键值对的新结点.
  • 键值小于结点键值,递归插入结点左子树
  • 键值大于节点键值,递归插入结点右子树
  • 键值等于结点键值,更新结点键值并返回

• 时间复杂度

  • 与查找的分析相同.
  • 插入的时间复杂度最好为 $O(\log n)$,最坏为 $O(n)$

• 代码

  # 插入
  def insert(self, key, value):
      # 有可能根节点更新
      self.root = self.put(key, value, self.root)
  def put(self, key, value, node=None):
      # 找到key,存在节点则更新值,否则插入新的节点.
      if node is None:
          return BtNode(key, value, N=1)
      cmp = self.key_compare(key, node.key)
      if cmp < 0:
          node.lchild = self.put(key, value, node.lchild)
      elif cmp > 0:
          node.rchild = self.put(key, value, node.rchild)
      else:
          node.value = value
      node.N = self.size(node.lchild) + self.size(node.rchild) + 1
      return node

删除

• 删除稍微复杂一点,分3种情况:

  • 待删除结点为叶子结点: 直接将链接断开即可 (c语言需要自行释放内存)
  • 待删除结点左/右子树单个不为空: 将不为空的左/右链接,连接到待删除结点的父节点即可.
  • 待删除结点左右子树均不为空: 这种情况稍微复杂,实现方式不一,基本方式是,删除结点x后使用其后继结点填充,同时保存二叉搜索树的有序性.
    • 使用右子树的最小结点 s 替换待删除结点 x,同时在右子树删除结点 s .链接原 x 的左右子树到 s.
    • 或者,使用左子树的最大结点 t 替换待删除结点 x,同时在左子树删除结点 t,链接原 x 的左右子树到 t.
    • 这里选择右子树最小结点 s
    • 对性能影响,见最后一小节.

• 步骤

  • 递归找到待删除结点(与查找类似)
  • 如果x的左子树为空,返回右子树链接.
  • 如果x的右子树为空,返回左子树链接.
  • 找到右子树最小结点,并在右子树删除最小结点
  • 右子树最小结点替换x,并连接原x的左右子树.
  • 返回x结点.

• 时间复杂度,

  • 假设二叉树高为 h ,待删除结点 x 深度为 hx.
  • 查找过程的时间复杂度为 $O(hx)$
  • 在删除节点x的过程中,除查找右子树最小节点的时间复杂度为 $O(h-hx)$.其他均为常数时间.
  • 所以整个删除操作的时间复杂度为 $O(h)$ 即 时间复杂度最好为 $O(\log n)$,最坏为 $O(n)$

• 代码

  # 删除
  def delete(self, key):
      self.root = self.delete_node(key, self.root)
  def delete_node(self, key, node=None):
      # 如果节点为空
      if node is None:
          return None
      cmp = self.key_compare(key, node.key)
      # 继续向下递归
      if cmp < 0:
          node.lchild = self.delete_node(key, node.lchild)
      elif cmp > 0:
          node.rchild = self.delete_node(key, node.rchild)
      else:
          # 如果只有一个节点/子节点均为空
          if node.lchild is None:
              return node.rchild
          if node.rchild is None:
              return node.lchild
          # 两个子节点均不为空
          tmp = node  # 备份node节点
          node = self.min(tmp.rchild)  # node位置被右子树最左边节点取代
          tmp.rchild = self.deleteMin(tmp.rchild)
          node.rchild = tmp.rchild  # 新node的右子树 = 删除最左边节点依旧大于新node的原node的右子树
          node.lchild = tmp.lchild  # 新node的左子树 = 原node的左子树
      # 更新节点计数器
      node.N = self.size(node.lchild) + self.size(node.rchild) + 1
      return node

选择

• 选择操作是返回排名为 k 的键.

• 步骤

  • 如果左子树的节点数 t > k ,递归查询左子树.
  • 如果左子树的节点数 t = k ,返回根节点健
  • 如果左子树的节点数 t < k ,递归查找右子树 k-t-1 的键.

• 时间复杂度

  • 证明和查找类似,不加赘述.
  • 选择的时间复杂度最好为 $O(\log n)$,最坏为 $O(n)$

• 代码

  # 选择 返回排名k的key
  def select(self, k):
      return self.select_node(k, self.root).key
  def select_node(self, k, node=None):
      # 返回排名k的节点
      if node is None:
          return None
      n = self.size(node.lchild)
      if n > k:
          return self.select_node(k, node.lchild)
      elif n < k:
          return self.select_node(k - n - 1, node.rchild)
      else:
          return node

排名

• 正好与选择相反,输入为key 返回 key 的排名.

• 步骤

  • key = 节点的键,返回左子树节点数
  • key < 节点的键,递归进入左子树查找.
  • key > 节点的键,返回 左子树节点总数 + 1 + 递归进入右子树查找

• 时间复杂度

  • 与查找类似,不加赘述
  • 时间复杂度最好为 $O(\log n)$,最坏为 $O(n)$

• 代码

  # 排名 返回key的排名
  def rank(self, key):
      return self.rank_node(key, self.root)
  def rank_node(self, key, node=None):
      # 返回node为根节点的子树中小于key的数量.
      if node is None:
          return 0
      cmp = self.key_compare(key, node.key)
      if cmp < 0:
          return self.rank_node(key, node.lchild)
      elif cmp > 0:
          return self.size(node.lchild) + 1 + self.rank_node(
              key, node.rchild)
      else:
          return self.size(node.lchild)

范围查找

• 返回给定范围内的所有键值.与查找类似,只不过加入了一个栈,将查找上限和下限过程中的所有结点全部加入栈中.

• 步骤

  • 结点为空,返回
  • 结点键小于上限,递归进入左子树.
  • 结点键在上限下限中间,入栈.
  • 结点键大于下限,递归进入右子树.

• 时间复杂度

  • 与查找的分析类似,多了入栈的操作,不过同样是 $O(h)$
  • 所以范围查找的时间复杂度最好为 $O(\log n)$,最坏为 $O(n)$

• 代码

  # 范围查找
  def kesys(self, min, max):
      arr = []
      self.keys_node(arr, min, max, self.root)
      return arr
  def keys_node(self, arr, min, max, node=None):
      if node is None:
          return
      cmpmin = self.key_compare(min, node.key)
      cmpmax = self.key_compare(max, node.key)
      if cmpmin < 0:
          self.keys_node(arr, min, max, node.lchild)
      if (cmpmin <= 0) and (cmpmax >= 0):
          arr.append(node)
      if cmpmax > 0:
          self.keys_node(arr, min, max, node.rchild)

性能分析

• 从前面的分析来看,整个二叉搜索树各个操作的时间复杂度与树高成正比.
• 影响二叉树树高的有插入和删除两个操作
  • 插入: 等同于二叉搜索树的生长过程,其与输入键值对的顺序有关,即使输入键值对的集合相同,也有可能出现最坏情况.
  • 删除: 删除结点的前两种情况不会影响树高,没有好坏之分.但当待删除结点的左右子树均不为空时,无论是选择左子树最大结点替换 还是 选择右子树最小结点替换,虽然可以正确执行删除操作,当完全没有考虑对树高的影响.
• 针对这两个问题,改进型的二叉搜索树则可以完美解决,保证即使是最坏情况下所以的操作都是 $O(\log n)$.
• 下一章,2-3二叉搜索树.