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

发表于 2019-03-18 分类于计算机基础，数据结构阅读次数： Disqus：本文字数： 5.9k 阅读时长 ≈ 5 分钟

数据结构-搜索(一) 二叉搜索树,包括 python 源代码,及相关一部分证明
源码: https://github.com/Jasper-1024/python/tree/master/data_structure/search

更新

1 2	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二叉搜索树.