二叉查找树（二）

05选择操作

排名select：找出排名为k的键

左子树中的结点数t大于k，那么我们就继续（递归地）在左子树中查找排名为k的键；

如果t等于k，我们就返回根结点中的键；

如果t小于k，我们就（递归地）在右子树中查找排名为（k-t-1）的键。

    // 返回排名为K的节点
    Node* select(Node* x, const 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;
    }

06排名操作

选择rank：找出小于指定键的键的数量

如果给定的键和根节点的键相等，返回左子树中节点总数t；

如果给定的键小于根节点，返回该键在左子树中的排名；

如果给定的键大于根节点，返回值为t+1+在右子树中的排名。

    // 返回以x为根节点的子树中小于key的键的数量
    int rank(const K& key, Node* x)
    {
        if (x == nullptr) return 0;
        int cmp = compareTo(key, x->_key);
        if (cmp < 0) return rank(key, x->_key);
        else if (cmp > 0) return 1 + size(x->_left) + rank(key, x->_right);
        else return size(x->_left);
    }