二叉查找树

1. 介绍

为了解决线性结构下的二分查找无法支持高效的插入和删除操作的问题，同时提高插入和删除的效率；

我们采用二叉查找树来进行符号表的实现。

二叉查找树是一种树，它满足：

1. 每个节点都拥有一个 Comparable 键
2. 每个节点都大于它的左子节点，小于它的右子节点

2. 数据结构的实现

我们使用链式结构来实现这个树。一个节点包含了：

1. 左子结点的链接
2. 右子结点的链接
3. 以这个节点为根节点的树的节点总数
4. 节点的键和值

The Node of Binary Search Tree
Node leftChild	Key key	Value val	int N	Node rightChild

Code:

// The inner class of Node
private class Node {
    private Key key;
    private Value val;
    private Node left, right;

    // 以该节点为根的子树的节点个数，包括根节点
    private int N;

    public Node(Key key, Value val, int N) {
        this.key = key;
        this.val = val;
        this.N = N;
    }
}

3. API 实现

这一节主要介绍数据的形式和相应的方法操作。这些方法都是基于二分查找发展而来的

它们是：

1. get(), put()
2. min(), max(), floor(), ceiling()
3. delete(), deleteMin(), deleteMax()

3.1 搜索

下面是 get() 方法的基本实现思路

使用二叉搜索树来搜索数据与二分查找十分相像。

首先从根节点开始，做以下操作：

1. 如果根节点和所给的键值相等，那么命中
2. 如果所给的键值比根节点小，那么就在其左子树搜索
3. 如果所给的键值比根节点大，那么就在其右子树搜索
4. 假如最终找到了 null，那么说明所给键值不在符号表中，返回 null

Code:

public Value get(Key key) {
    return get(root, key);
}

private Value get(Node x, Key key) {

    if(x == null) {
        return null;
    }

    int cmp = key.compareTo(x.key);

    if(cmp < 0)
        return get(x.left, key);
    else if(cmp > 0)
        return get(x.right, key);
    else
        return x.val;
}

注意这里使用了递归的方法来深入子树中进行搜索。关于递归在下面的 put() 方法中也有运用。

3.2 插入

比起之前基于有序数组的二分查找，二叉搜索树的最大改进之处在于二叉搜索树拥有效率更高的元素插入操作。

事实上，进行元素的插入是十分简单的，仅仅只是定位元素位置，连接上新元素，就完成了。

需要注意的是，二叉搜索树是有序的，你必须事先定位元素的插入位置，也就是说，你不能将元素随便地插入到一些错误的地方。

对于 put() 方法，主要完成两项工作：

1. 如果键值已经存在于符号表中，那么就更新它的值
2. 如果键值不在符号表中，那么就创建一个新的节点存储键值对

下面是 put() 方法的代码

public void put(Key key, Value val) {
    root = put(root, key, val);
}

private Node put(Node x, Key key, Value val) {

    if (x == null)
        return new Node(key, val, 1);

    int cmp = key.compareTo(x.key);

    if (cmp < 0)
        x.left = put(x.left, key, val);
    else if (cmp > 0)
        x.right = put (x.right, key, val);
    else
        x.val = val;

    // 更新节点个数
    x.N = size(x.left) + size(x.right) + 1;
    return x;

}

注意到，put() 方法是递归的，这也是它的主要工作原理之一。
通过这个递归的方法，它才能深入树去进行搜索定位。
而最重要的一点是，此方法必须将我们传入的 Node 引用返回

如果我们传进去的是一个正常的节点，也就是一些我们不应该去修改的内部节点，那么此方法必须将这个引用原样返回，而且返回值要让原始的引用去捕获。
这样，我们才能维持树的基本结构，否则树的结构就会被损坏。

如果我们传进去的不是一个正常的节点，比如 null 值，那么方法会自动生成一个新的节点，并将其返回，那么原有的链接就能连上一个新的节点。

一件非常有趣的事是，不只是公有方法，而且递归的私有方法也出现了同样的代码结构，即 x = put(x, key, val), 我们将 x 传递进去，然后最终它却返回出来被原有的引用捕获了。

这是合理的，因为只有采用这种方式，我们才能保持树的结构然后更新链接，而不是毁掉它。

事实上，递归方法不返回引用也是可以的，只不过需要在函数内部将链接连上。

if (x == null) {
    x = new Node(key, val);
}

3.3 删除

删除操作是最为复杂的 BST 操作。
它拥有很多情况，让我们逐步分析。

3.3.1 删除 最小/最大 值

这是删除操作中最为简单的情况，我们只需删除最左或者最右边的节点，然后链接上它剩下的子树即可

我们使用 delMin() 作为例子，将其反过来做，就变成了 delMax()
下面是相应的操作：

1. 一直深入左子树去查找，然后定位到最小的节点
2. 将它的右子树和它的父节点连接
3. 由于原有的连接最小节点的链接被其右子树占据，没有指向最小节点的引用，那么它就会被垃圾回收机制回收。

在这里，我们依旧使用递归的方法来深入树进行查找

public void deleteMin() {
    root = deleteMin(root);
}

private Node deleteMin(Node x) {
    if (x.left == null)
        return x.right;

    x.left = deleteMin(x.left);
    x.N = size(x.left) + size(x.right) + 1;

    return x;
}

与 put() 方法一样， delMin() 方法采用了递归的方法来深入树进行查找

所以，它需要返回我们传入的链接，然后让原有链接捕获它来保持整个树的结构。这也是更新链接的方式。

但是最有趣和最重要的一点是，当我们找到最小的节点之后，我们要将其右子树返回。

由于递归操作，最小节点的父节点的左链接会连接到最小节点的右子树上。
这个操作事实上 FREE 了最小的节点，而且保持了结构的完整。

这个操作在我们删除具有两个子节点的元素的时候也很有用。

那么在这里递归方法能不能不返回引用呢？
答案是不行！
delMin() 方法和 put() 方法不同的一点是它要回溯到上一个节点，当需要回溯到上一个节点的时候，我们就需要采用返回一个引用的方法，否则无法回溯。
所以建议统一采用返回引用的做法

3.3.2 通常节点的删除

我们可以使用类似 delMin() 的方法来删除只具有一个子节点的节点

但是删除具有两个子节点的节点会更为复杂。

这种情况下需要解决的最重要的问题是，我们需要找到一个节点来替代其位置，否则链接将会损坏。

为了解决这个问题，我们采用它的后继来替代它。

下面是找到所需删除元素 x 之后的步骤：

1. 将 x 保存一个副本 t

   t 即所需要删除的元素

2. 让 x 指向其后继 min(x.right)

   后继即比 x 大的下一个节点，也就是其右子树中最小的节点
   此时 x 已经指向后继。

3. 让 x.right 指向 delMin(t.right)

   这一步较为关键和难以理解。
   delMin(t.right) 主要做了如下几件事：

   1. 将后继从下层的链接释放出来

      t 是原有 x 的副本，所以 delMin(t.right) 最后会查找到其后继，并释放出来。

   2. 保持后继释放后的链接完整性。

      delMin() 在查找到最小节点之后会返回右链接，由于调用递归性，右链接会被上层捕获，从而保持了链接性。
      这里将后继释放出来后，会让其父节点来负责链接上其右子树。

   3. 更新计数，并将传入的链接原样返回

      这是最为重要的，首先将计数更新了，保证计数正确性。

      其次，delMin(x) 在最后退出递归的时候会返回 x。
      也就是 delMin(t.right) 的返回值是 t.right。
      那么 x.right = delMin(t.right) 也就相当于 x.right = t.right。

      正好是使用了 x 来替代 t（注意此时 x 已经是后继了）

4. 让 x.left 指向 t.left

5. 更新计数器，递归方法返回传入值来保持链接完整性

Code:

public void delete(Key key) {
    root = delete(root,key);
}
private Node delete(Node x, Key key) {
    // Notice that, we use recursive way
    // to locate the Node which will be delete
    // Also, we need to renew the counter

    // Therefore, in this method, we need to
    // retrun the link of the node itself, to
    // miantain the connectivity

    if (x == null) return null;
    int cmp = key.compareTo(key);

    // if not hit,
    // deep into subtree and continue search
    if (cmp < 0) x.left = delete (x.left, key);
    else if (cmp > 0) x.right = delete(x.right, key);
    else {  // hit
        // The deletion of one or none child
        if (x.right == null) return x.left;
        if (x.left == null) return x.right;

        // Two child
        Node t = x;
        x = min(t.right);
        // refer to the special notice
        x.right = deleteMin(t.right);
        x.left = t.left;
    }
    // renew counter
    x.N = size(x.left) + size(x.right) + 1;


    return x;   // return itself to maintain the conectivity
}

3.4 其他的有序方法

3.4.1 最小和最大

找到最小或者最大的元素是很简单的，只需要深入左子树或者右子树就可以了。

public Key min() {
    return min(root).key;
}

private Node min(Node x) {
    if (x.left == null) return x;
    return min(x.left);
}

3.4.2 向下取整/向上取整

这两个方法的目的是寻找到一个不大于或者不小于输入节点的节点

我们使用向下取整来举个例子：

这个方法的核心思想就是：

1. 如果所给的键值比根节点小，那么所需的节点就肯定在左子树中

2. 如果所给的键值比根节点大，那么所需的节点可能在右子树中

   也就是说，如果我们在右子树中找不到所需节点，那么根节点就是所需节点

public Key floor(Key key) {
    Node x = floor(root, key);
    if (x == null) return null;
    return x.key;
}

private Node floor(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return x;
    if (cmp < 0) return floor(x.left, key);
    Node t = floor(x.right, key);
    if (t != null) return t;
    else return x;
}

3.4.3 选择和排序

这两个方法是关于节点在树中的排位问题的。

这也是为什么我们需要维护一个子树的节点总数的原因。

select() 和 rank() 是一对互逆方法，一个给排名，返回键值，另一个给键值，返回排名

下面用 rank() 方法举个例子，此方法的步骤是：

1. 如果键值和根节点相等，那么根节点的左子树的总数就是所给节点的排名

2. 如果所给的键值比根节点小，那么就在左子树中寻找

3. 如果所给的键值比根节点大，那么在右子树中寻找，此时，所给节点的排名为：

   $Rank = Size(left\ subtree) + Rank(right\ subtree) + 1$

   左子树中的节点都比根节点小，既然所给节点都比根节点大，那么理应比左子树的节点都要大。所以排名还要加上左子树中的节点个数。其中的 $1$ 表示的是根节点本身。

public Key select(int k) {
    return select(root, k).key;
}

private Node select(Nodex, int k) {
    if (x == null) return null;
    int t = size(x.left);
    if (t >k) return select(x.left, k);
    else if (t < k) return select(x.right,k - t - 1);
    else return x;
}

public int rank(Key key) {
    return rank(key, root);
}

private int rank(Key key, Node x) {
    if(x == null) return  0;
    int cmp = key.compareTo(x.key);
    if (cmp < 0) return rank(key, x.left);
    else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right);
    else return size(x.left);
}

由方法的步骤可以看出，这两个方法都具有浓重的递归特质，使用递归类型的方法会简便得多

3.4.4 范围

keys() 方法的主要算法思想就是要返回在一个特定范围内的所有键值

我们使用队列来保存这些键值

1. 如果根节点比范围小，那么找右子树

2. 如果根节点比范围大，那么找左子树

3. 如果根节点在范围内，将其入列，然后分别找左子树和右子树

   这么做的目的是，如果一个节点在范围内，那么它的左子树和右子树也有可能在范围内

public Iterable<Key> keys() {
    return keys(min(), max());
}

public Iterable <Key> keys(Key lo, Key hi) {
    Queue<Key> queue = new Queue<Key>();
    keys(root, queue, lo, hi);
    return queue;
}

private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
    if (x == null) return;
    int comlo = lo.compareTo(x.key);
    int cmphi = hi.compareTo(x.key);

    // Notice that there is no *eles*,
    // that's because we need to traversal the subtree
    if (cmplo < 0) keys(x.left, queue, lo, hi);
    if (cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key);     // Within range
    if (cmphi > 0) keys(x.right, queue, lo, hi);
}

4. 性能

BST 的性能是依赖于输入模型的。

最好的情况是 BST 完美平衡，也就是说所有叶节点到根节点的距离是$\sim lgN$

最坏的情况是 BST 中的每一个节点都在同一侧，此时搜寻效率将会减少到 $O(N)$

在平均情况下，一个有 $N$ 个随机键值的二叉树中，插入和未命中搜索需要 $\sim 2lnN$ (大约是 $1.39lgN$) 次的比较;

对于删除操作，在平均情况下，则需要 $\sqrt{N}$ 次比较

5. 结论

使用 BST 可以很好地解决数组插入和删除引起的性能问题。

事实上，在 BST 中进行搜索需要大约 $39\%$ 的额外性能，但是由于插入的开销被减少到了对数级别，所以这一额外的花销是值得的。

但是，BST 没有时间复杂度上的性能保证，在最坏情形下，它搜寻一个键仍然需要线性级别的时间