符号表及其三种实现2：二叉查找树

二叉查找树

这种数据结构能够将链表插入的灵活性和有序数组查找的高效性结合，大名鼎鼎的二叉查找树，也叫二叉搜索树。下面的代码是一份完整的类实现

class BST
{
public:
    class Node
    {
    public:
        int key; //键
        int value; //值
        Node* left;
        Node* right;
        int N;//以该节点为根节点的树的节点总数
    public://Node类的构造函数
        Node(int key, int value, int N):key(key), value(value), N(N){}
    };
    Node root;
public:
    //BST(); //构造函数
    int Size(){ return Size(root); } //返回所有节点总数
    int Size(Node x)//以x节点为根节点的树的节点总数
    {
        if (&x == NULL)
        return x.N;    
    }
    int Get(int key){ return Get(root, key); } // 根据键获取值
    //递归实现，类似二分查找
    int Get(Node x, int key)
    {
        if (&x == NULL){ return NULL; }
        if (key < x.key){ return Get(*(x.left), key); }
        else if (key > x.key){ return Get(*(x.right), key); }
        else return x.value;
    }
    void Put(int key, int value){ root = Put(root, key, value); }//插入节点
    Node Put(Node x, int key, int val)
    {
        //递归触底没找到，就用这句话插入新节点
        if (&x == NULL){ return Node(key, val, 1); }
        if (key < x.key)
        {
            *(x.left) = Put(*(x.left), key, val);
        }
        else if (key > x.key)
        {
            *(x.right) = Put(*(x.right), key, val);
        }
        else //如果找到了就更新
        {
            x.value = val;
        }
        //更新N值，统一写法，任何节点的N都等于这个句子
        x.N = Size(*(x.left)) + Size(*(x.right)) + 1;
        return x;
    }
};

put和get都是O(lgN)

接下来我们来分别实现一些有用的成员函数：

最大键和最小键

很简单，最大键是最右节点，最小键是最左节点：

int Min(){ return Min(root).key; }//最小键
Node Min(Node x)
{
    if (x.left == NULL){ return x;}
    return Min(*(x.left));
}
int Max(){ return Max(root).key; } //最大键
Node Max(Node x)
{
    if (x.right == NULL){ return x; }
    return Max(*(x.right));
}

小于等于给定key的最大键

• 如果给定的key等于根节点，那么小于等于key的最大键就是根节点
• 如果给定的key小于根节点，那么小于等于key的最大键在左子树中（因为根已经大于key了）
• 如果给定的key大于根节点，那么分两种情况
  1. 右子树中存在小于等于key的节点，找到其中最小的
  2. 右子树中不存在这样的节点，那么根节点就是小于等于key的最大键
     代码也是按照这个思路写的：int Floor(int key)//小于等于key的最大键 { Node x = Floor(root, key); if (&x == NULL){ return 0; } return x.key; } Node Floor(Node x, int key) { if (&x == NULL){ return x; } if (key = x.key){ return x; } if (key < x.key){ return Floor(*(x.left), key); } Node t = Floor(*(x.right), key); if (&t != NULL){ return t; } else{ return x; } }

排名操作

首先是给定排名，找到对应的键：

Key select(int k){
    return select(root, k).key;
}
Node select(Node x, int k){ //找到排名为k的键，x为根节点
    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;
}

逆操作：给定键，找到它的排名，就是之前的rank函数

int rank(Key key){
    return rank(key, root);
}
int rank(Key key, Node x){
    if(x==NULL) return 0;
    if(key<x.key) return rank(key, x.left);
    else if(key>x.key) return 1+Size(x.left)+rank(key, x.right);
    else return Size(x.left);
}

麻烦的删除操作

先来个简单地删除最值，以最小值为例（删除最左节点）

void deleteMin(){
    root = deleteMin(root);
}
//要删除，先找到，所以很大程度上与前面查找类似
Node deleteMin(Node x){
    if(x.left==NULL) return x.right; //这步就是递归触底反弹，也是删除操作
    //被删除的最左节点，如果有右子就返回右子来替代它，没有右子就用NULL替换
    //这样其实貌似泄漏内存了，先不管。。。
    x.left = deleteMIn(x.left);
    x.N = Size(x.left)+Size(x.right)+1; //修正N值
    return x;

不清楚的看下图，算法书的作者最溜的就是画图了

接下来是最麻烦的删除给定的key

因为这个比较麻烦，我们先看图，再解释，最后贴代码：

应该怎样删除一个拥有两个子节点的节点呢？还记不记得在最大堆最小堆中我们的处理：用层序遍历的最后一个节点去替换根节点，然后再sink或swim，但是这里显然不能这么操作。

我们想想，被删除的父节点只有一条链接空出来，我们如果要在剩下的左子和右子树中挑一个节点去替代它，哪个节点最合适呢？那肯定是右子的最小和左子的最大，因为这样还能保证它是二叉查找树，下面我们就用右子最小来做这件事，一共分四步：

1. 将指向即将被删除的节点x的链接保存为t
2. 让x指向它的“继承人”min(t.right)
3. 将x的右链接指向deleteMin(t.right)，这步不仅删除了H，还把它搬上来作为x的替代，而且deleteMin()返回右子的根节点，正好也是x的右链接指向的节点
4. 将x的左链接设为t.left
   代码如下：```
   void delete(Key key){
   root = delete(root, key);
   }
   Node delete(Node x, Key key){
   if(x==NULL) return NULL;
   //当然，执行四部曲之前要先找到待删除的节点x
   if(key<x.key) x.left = delete(x.left, key); else if(key>x.key) x.right = delete(x.right, key);
   else{

   //待删除的节点x最多只有一个子节点时，很简单，拿另一个替代它即可
    if(x.right==NULL) return x.left;
    if(x.left==NULL) return x.right;
    // here comes sibuqu finally
    Node t = x;
    x = min(t.right);
    x.right = deleteMin(t.right);
    x.left = t.left;

   }
   x.N = Size(x.left)+Size(x.right)+1;
   return x;
   }
   ```

终于最后一个：范围查找

给定两个键值，找到二叉查找树中位于这两个键值之间的所有键

记住哈，二叉查找树的中序遍历就是按顺序遍历键值的：

void InorderPrint(Node x){
    if(x==NULL) return;
    InorderPrint(x.left);
    cout << x.key << endl;
    InorderPrint(x.right);
}

我们可以修改一下这段代码，将所有落在给定范围内的键加入队列，并跳过那些不可能含有所查找键的子树：

void FindKeys(Node x, queue q; key lo, key hi){
    if(x==NULL) return; //触底反弹对应L返回到M
    //只要lo<x.key，则x的左子树就有可能有所查找的节点，所以要一直递归
    if(lo<x.key) FindKeys(x.left, q, lo, hi); 
    if(x.key>=lo && x.key<=hi) q.push(x.key);
    if(hi>x.key) FindKeys(x.right, q, lo, hi);
}