3.2 二叉查找树 Binary Search Tree

一颗二叉查找树（BST）是一颗二叉树，其中每个结点都含有一个 Comparable 的键（以及相关联的值）且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。

键之间有顺序之分以支持高效地查找。（通过键来排序，之后通过查找键来取出值。）

详解二叉查找树

基本实现

数据表示

每个结点都含有一个键，一个值，一条左链接，一条右链接，和一个结点计数器。左链接指向一个由小于该结点的所有键组成的二叉查找树；右链接指向一个由大于该结点的所有键组成的二叉查找树。
size(x) = size(x.left) + size(x.right) + 1

一个二叉查找树代表了一组键的集合，而同一个结合可以用多颗不同的二叉查找树表示。将一颗二叉查找树的所有键投影到一条直线上，保证一个结点的左子树中的键出现在它的左边，右子树中的键出现在它的右边，那么我们可以得到一条有序的键列。

两颗能够表示同一组键的二叉查找树

查找

二叉查找树中查找一个键的递归算法：如果树是空的，则查找未命中；若被查找的键和根结点的键相等，查找命中；否则就（递归地）在适当的子树中继续查找。如果被查找的键较小就选择左子树，较大则选择右子树。

随着我们不断向下查找，当前结点所表示的子树的大小也在减小（理想情况下是减半，但至少会有一个结点）。当找到一个含有被查找的键的结点（命中）或者当前子树变为空（未命中）时这个过程才会结束。

二叉查找树的查找命中（左）和未命中（右）

class BST():
    def __init__(self):
        self.root = None

    class Node():
        def __init__(self, key, val, size):
            self.key = key
            self.val = val
            self.size = size
            self.left = None
            self.right = None
    
    def size(self):
        return self._size(self.root)
    
    def _size(self, node):
        if node:
            return node.size
        else:
            return 0

    def get(self, key):
        return self._get(self.root, key)

    def _get(self, node, key):
        if node is None:
            return None
        if key < node.key:
            return self._get(node.left, key)
        elif key > node.key:
            return self._get(node.right, key)
        else:
            return node.val

    def put(self, key, val):
        self.root = self._put(self.root, key, val)

    def _put(self, node, key, val):
        if node is None:
            return BST.Node(key, val, 1)
        if key < node.key:
            node.left = self._put(node.left, key, val)
        elif key > node.key:
            node.right = self._put(node.right, key, val)
        else:
            node.val = val
        node.size = self._size(node.left) + self._size(node.right) + 1
        return node

插入

查找代码的简洁性是二叉查找树的重要特性之一。
另一个更重要的特性就是插入的实现难度和查找差不多。

二叉查找树的插入操作

递归

可以将递归调用前的代码想象成沿着树向下走：它会将给定的键和每个结点的键相比较并根据结果向左或者向右移动到下一个结点。

然后可以讲递归调用后的代码想象成沿着树向上爬。

对于 get() 方法，这对应着一系列的返回指令（return），但是对于 put() 方法，这意味着重置搜索路径上的每个父结点指向子结点的链接，并增加路径上每个结点中的计数器的值。

一般的二叉查找树的实现常常是被递归的。

使用二叉查找树的标准索引用例的轨迹

分析

使用二叉查找树的算法的运行时间取决于树的形状，而树的形状又取决于键被插入的先后顺序。在最好的情况下，一颗含有 N 个结点的树是完全平衡的，每条空链接和根结点的距离都为 lgN；在最坏的情况下，搜索路径上可能有 N 个结点。

二叉查找树的可能形状

在由 N 个随机键构造的二叉查找树中，查找命中平均所需的比较次数为 2lgN（约 1.39lgN）

在由 N 个随机键构造的二叉查找树中插入操作和查找未命中平均所需的比较次数为 2lnN（约 1.39lgN）

二叉查找树中查找随机键的成本比二分查找高约 39%，但这些额外的成本是值得的，因为插入一个新键的成本是对数级别的 -- 这是基于二分查找的有序数组所不具备的灵活性，因为它的插入操作所需访问数组的次数是线性级别的。

有序性相关的方法和删除操作

二叉查找树得以广泛应用的一个重要原因就是它能够保持键的有序性，因此它可以作为实现有序符号表 API 中的众多方法的基础。这使得符号表的用例不仅能够通过键还能通过键的相对顺序来访问键值对。

最大键和最小键

如果根结点的左链接为空，那么一个二叉查找树中最小的键就是根结点；如果左链接非空，那么树中的最小键就是左子树中的最小键。

向上取整和向下取整

如果给定的键 key 小于二叉查找树的根结点的键，那么小于等于 key 的最大键 floor(key) 一定在根结点的左子树中；如果给定的键 key 大于二叉查找树的根节点，那么只有当根结点右子树中存在小于等于 key 的结点时，小于等于 key 的最大键才会出现在右子树中。

计算 floor() 函数

    def min(self):
        return self._min(self.root).key

    def _min(self, node):
        if node.left is None:
            return node
        return self._min(node.left)

    def floor(self, key):
        node = self._floor(self.root, key)
        if node is None:
            return None
        return node.key

    def _floor(self, node, key):
        if node is None:
            return None
        if node.key == key:
            return node
        if key < node.key:
            return self._floor(node.left, key)
        t = self._floor(node.right, key)
        if t is not None:
            return t
        else:
            return node

选择操作

二叉查找树的选择操作类似基于切分的数组选择操作。在二叉查找树的每个结点中维护的子树结点计数器变量就是用来支持此操作的。

想找到排名为 k 的键（即树中正好有 k 个小于它的键）。如果左子树中的结点树 t 大于 k，那么我们就继续（递归地）在左子树中查找排名为 k 的键；如果 t 等于 k，就返回根结点中的键；如果 t 小于 k，就（递归地）在右子树中查找排名为（k-t-1）的键。

二叉查找树中的 select() 操作

排名

rank() 是 select() 的逆方法。它会返回给定键的排名。实现和 select() 类似：如果给定的键和根结点的键相等，返回左子树中的结点总数 t；如果给定的键小于根结点，返回该键在左子树中的排名（递归计算）；如果给定的键大于根结点，返回 t+1（根结点）加上它在右子树中的排名（递归计算）。

    def select(self, k):
        return self._select(self.root, k).key

    def _select(self, node, k):
        if node is None:
            return None
        t = self._size(node.left)
        if t > k:
            return self._select(node.left, k)
        elif t < k:
            return self._select(node.right, k - t - 1)
        else:
            return node

    def rank(self, key):
        return self._rank(self.root, key)

    def _rank(self, node, key):
        if node is None:
            return 0
        if node.key > key:
            return self._rank(node.left, key)
        elif node.key < key:
            return 1 + self._size(node.left) + self._rank(node.right, key)
        else:
            return self._size(node.left)

删除最大键和删除最小键

对于 deleteMin()，不断地深入根结点的左子树直至遇见一个空链接，然后将指向该结点的链接指向该结点的右子树。

删除二叉查找树中的最小结点

删除操作

在删除结点 x 后用它的后继结点填补他的位置。因为 x 有一个右子结点，因此它的后继结点就是其右子树中的最小结点。这样的替换仍然能够保证书的有序性，因为 x.key 和它的后继结点的键之间不存在其他的键。

1. 将指向即将被删除的结点的连接保存为 t；
2. 将 x 指向它的后继结点 min(t.right)；
3. 将 x 的右链接（原本指向一颗所有结点都大于 x.key 的二叉查找树）指向 deleteMin(t.right)，也就是再删除后所有结点仍然都大于 x.key 的子二叉查找树。
4. 将 x 的左链接（本为空）设为 t.left （其下所有的键都小于被删除的结点和它的后继结点）。

前趋节点和后继节点的选择应该是随机的。

二叉查找树中的删除操作

    def deleteMin(self):
        self.root = self._deleteMin(self.root)

    def _deleteMin(self, node):
        if node.left is None:
            return node.right
        node.left = self._deleteMin(node.left)
        node.size = self._size(node.left) + self._size(node.right) + 1
        return node

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, x, key):
        if x is None:
            return None
        if x.key > key:
            x.left = self._delete(x.left, key)
        elif x.key < key:
            x.right = self._delete(x.right, key)
        else:
            if x.right is None:
                return x.left
            if x.left is None:
                return x.right
            t = x
            x = self._min(t.right)
            x.right = self._deleteMin(t.right)
            x.left = t.left
        x.size = self._size(x.left) + self._size(x.right) + 1
        return x

在一颗二叉查找树中，所有操作在最坏情况下所需的时间都和树的高度成正比。