0%

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

导语

  • 本打算一章写完,二叉搜索树,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较多,这里仅选典型几个).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    # 查找的基类
    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)$
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # 查找
    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)$
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # 插入
    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)$
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    # 删除
    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)$
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # 选择 返回排名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)$
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # 排名 返回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)$
  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # 范围查找
    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二叉搜索树.