二叉查找树

二叉查找树

定义

二叉查找树是一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。二叉查找树得以广泛应用的一个重要原因是它能够保持键的有序性，因此它可以作为实现有序符号表 API 中众多方法的基础，这是计算机科学中最重要的算法之一。

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

基本实现

和链表一样，在类中定义一个私有结构体来表示二叉查找树的一个节点，每个节点都含有一个键、一个值、一条左链接、一条右链接和一个节点计数器。左链接指向一棵由小于该节点的所有键组成的二叉查找树，右链接指向一棵由大于该节点的所有键组成的二叉查找树。

一棵二叉查找树代表了一组键（及其相应的值）的集合，而同一个集合可以用多棵不同二点二叉查找树表示。

struct Node
{
    Key key;
    Value val;
    Node *left = nullptr, *right = nullptr;
    int N;
    Node(Key key, Value val, int N) : key(key), val(val), N(N) {}
};

查找

我们很容易想到用递归的形式来进行查找。一般来说，在符号表中查找一个键可能得到两种结果，如果含有该键的节点在表中，就命中，然后返回相应的值。否则查找未命中，返回 nullptr。如果树是空的，则查找未命中，如果被查找的键和根节点的键相等，查找命中，如果被查找的键较小，选择左子树，较大选择右子树。

Value get(Node *x, Key key) {
    if (x == nullptr)
        return " ";
    if (x->key > key)
        return get(x->left, key);
    else if (x->key < key)
        return get(x->right, key);
    else
        return x->val;
}

插入

如果树是空的，就返回一个含有该键值对的新节点，如果被查找的键小于根节点的键，我们会继续在左子树中插入该键，如果被查找的键大于根节点的键，就在右子树中插入该键，如果相等，则更新值。并增加路径上每个节点中计数器的值。

Node* put(Node* x, Key key, Value val) {
    if (x == nullptr)
        return new Node(key, val, 1);
    if (x->key > key)
        x->left = put(x->left, key, val);
    else if (x->key < key)
        x->right = put(x->right, key, val);
    else
        x->val = val;
    x->N = size(x->left) + size(x->right) + 1;
    return x;
}

删除

二叉查找树中最复杂的方法就是删除操作，即从符号表中删除一个键值对。

首先考虑删除最小键所对应的键值对。我们需要不断深入根节点的左子树直到遇见一个空链接，然后将指向该节点的链接指向该节点的右子树。

删除的基本思想：删除节点 x 后用它的后继节点填补它的位置。

  1. 将指向即将被删除的节点的链接保存为 t ；
  2. 将 x 指向它的后继节点 min(t.right) ；
  3. 将 x 的右链接指向 deleteMin(t.right)，也就是在删除后所有节点仍然都大于 x.key 的子二叉查找树
  4. 将 x 的左链接设为 t.left
Node* min(Node* x) {
    if (x->left == nullptr)
        return x;
    return min(x->left);
}
Node* deleteMin(Node* x)
{
    if (x->left == nullptr)
        return x->right;
    x->left = deleteMin(x->left);
    x->N = size(x->left) + size(x->right) + 1;
    return x;
}
Node* deleteByKey(Node* x, Key key)
{
    if (x == nullptr)
        return nullptr;
    if (x->key > key)
        x->left = deleteByKey(x->left, key);
    else if (x->key < key)
        x->right = deleteByKey(x->right, key);
    else
    {
        if (x->right == nullptr)
            return x->left;
        if (x->left == nullptr)
            return x->right;
        Node* t = x;
        x = min(t->right);
        x->right = deleteMin(t->right);
        x->left = t->right;
    }
    x->N = size(x->left) + size(x->right) + 1;
    return x;
}

返回特定位置的键

得益于二叉查找树的有序性，我们可以返回特定位置的键。

Node* select(Node *x, int k) {
    if (x == nullptr)
        return nullptr;
    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;
}

分析

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

在由 N 个随机键构成的二叉查找树中，查找和插入平均所需的比较次数为 ~2lnN (约为1.39 lgN)

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

随机构造的树中所有路径长度都小于 3lgN

二叉查找树的基本实现的良好性能依赖于其中的键的分布足够随机以消除长路径

如果构造树的键不是随机的怎么办？下一节介绍平衡二叉查找树。

代码

template<typename Key, typename Value>
class BST
{
private:
    struct Node
    {
        Key key;
        Value val;
        Node *left = nullptr, *right = nullptr;
        int N;
        Node(Key key, Value val, int N) : key(key), val(val), N(N) {}
    };
    Node *root = nullptr;
    int size(Node *x) { if (x == nullptr) return 0; return x->N; }
    Value get(Node *x, Key key) {
        if (x == nullptr)
            return " ";
        if (x->key > key)
            return get(x->left, key);
        else if (x->key < key)
            return get(x->right, key);
        else
            return x->val;
    }
    Node* put(Node* x, Key key, Value val) {
        if (x == nullptr)
            return new Node(key, val, 1);
        if (x->key > key)
            x->left = put(x->left, key, val);
        else if (x->key < key)
            x->right = put(x->right, key, val);
        else
            x->val = val;
        x->N = size(x->left) + size(x->right) + 1;
        return x;
    }
    Node* min(Node* x) {
        if (x->left == nullptr)
            return x;
        return min(x->left);
    }
    Node* select(Node *x, int k) {
        if (x == nullptr)
            return nullptr;
        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;
    }
    Node* deleteMin(Node* x)
    {
        if (x->left == nullptr)
            return x->right;
        x->left = deleteMin(x->left);
        x->N = size(x->left) + size(x->right) + 1;
        return x;
    }
    Node* deleteByKey(Node* x, Key key)
    {
        if (x == nullptr)
            return nullptr;
        if (x->key > key)
            x->left = deleteByKey(x->left, key);
        else if (x->key < key)
            x->right = deleteByKey(x->right, key);
        else
        {
            if (x->right == nullptr)
                return x->left;
            if (x->left == nullptr)
                return x->right;
            Node* t = x;
            x = min(t->right);
            x->right = deleteMin(t->right);
            x->left = t->right;
        }
        x->N = size(x->left) + size(x->right) + 1;
        return x;
    }
public:
    int size() { return size(root); }
    Value get(Key key) { return get(root, key); }
    void put(Key key, Value val) { root = put(root, key, val);}
    Key min() { return min(root)->key; }
    Key select(int k) { return select(root, k)->key; }
    void deleteMin() { root = deleteMin(root); }
    void deleteByKey(Key key) { root = deleteByKey(root, key); }
};