C++版本的二叉搜索树(LLRB平衡)

andalousie

不久前我曾发布过一个未平衡的二叉搜索树，时至今日，我觉得是时候发布一个基本平衡的左偏红黑树(LLRB)来取代原来的二叉树了。仍将沿用原来的queue.h和main.cpp，只是基于原来的BST做了修改。不多说了，下面分享代码。
BST.h

#if !defined (BST_H)
#defind BST_H
#include "queue.h"

template<typename Index, typename Value>
class BST
{
private:
        const bool RED;
        const bool BLACK;
        struct Node
        {
                Node(Index k, Value v, int n, bool cl)
                :key(k), val(v), N(n), 
                 left(0), right(0), color(cl)
                {}
                Index key;
                Value val;
                Node *left, *right;
                bool  color; // color of parent link
                int   N;
        };
        Node *root;
        bool isRed(Node* x)
        {
                if(!x) return false;
                return x->color = RED;
        }

        Node* rotateLeft(Node* h)
        {
                assert (isRed(h->right));
                Node *x = h->right;
                h->right = x->left;
                x->left = h;
                x->color = h->color;
                h->color = RED;
                x->N = h->N;
                h->N = 1 + size(h->left)
                        + size(h->right);
                return x;
        }

        Node* rotateRight(Node* h)
        {
                assert (isRed(h->left));
                Node *x = h->left;
                h->left = x->right;
                x->right = h;
                x->color = h->color;
                h->color = RED;
                x->N = h->N;
                h->N = 1 + size(h->left)
                        + size(h->right);
                return x;
        }

        Node* moveRedLeft(Node* h)
        { // Assuming that h is red and both h->left and h->left->left
          // are black, make h->left or one of its children red.
                flipColors(h);
                if (isRed(h->right->left))
                {
                        h->right = rotateRight(h->right);
                        h = rotateLeft(h);
                }
                return h;
        }

        void flipColors(Node* h)
        {
                h->color = !h->color;
                h->left->color = !h->left->color;
                h->right->color = !h->right->color;
        }

        Node* balance(Node* h) 
        {
                assert(h);
                if (isRed(h->right) && !isRed(h->left)) h = rotateLeft(h);
                if (isRed(h->left) && isRed(h->left->left)) h = rotateRight(h);
                if (isRed(h->left) && isRed(h->right)) flipColors(h);

                h->N = size(h->left) + size(h->right) + 1;
                return h;
        }
public:
        BST(): RED(true), BLACK(false), root(0){}
        int    size() {        return size(root);        }
        bool isEmpty() { return !root; }
        Index min()        { return min(root)->key; }

        Index floor(Index key)
        {
                Node *x = floor(root, key);
                if(!x) return 0;
                return x->key;
        }

        Value get(Index key) { return get(root, key); }

        void put(Index key, Value val)
        { // Search for key. Update value if found; grow table if new.
                root = put(root, key, val);
                root->color = BLACK;
        }

        Value select(int k) { return select(root, k)->key; }

        int rank(Index key) { return rank(key, root); }

        void delMin()
        {   // if both children of root are black, set root to red
                if (!isRed(root->left) && !isRed(root->right))
                        root->color = RED;
                root = delMin(root);
                if (!isEmpty()) root->color = BLACK;
        }

        // delete the key-value pair with the given key
        void del(Index key)
        {   // if both children of root are black, set root to red
                if (!isRed(root->left) && !isRed(root->right))
                        root->color = RED;
                root = del(root, key);
                if (!isEmpty()) root->color = BLACK;
        }

        void iterate()
        {
                Queue<Index> q;
                inorder(root, q);
                while(!q.empty())
                {
                        Index key =  q.pop();
                        std::cout << get(key);
                }
        }
private:
        int   size(Node *x)
        {
                if(!x) return 0;
                else   return x->N;
        }

        Node* min(Node* x)
        {
                if(!(x->left)) return x;
                return min(x->left);
        }

        Node* floor(Node* x, Index& key)
        {
                if(!x) return 0;
                int cmp = compare(key, x->key);

                if (cmp == 0) return x;

                if (cmp < 0) return floor(x->left, key);

                Node* t = floor(x->right, key);
                if(t) return t;
                else return x;
        }
        
        Value get(Node *x, Index& key)
        { // Return value associated with key in the subtree rooted at x;
          // return null if key not present in subtree rooted at x.
                if (!x) return 0;
                int cmp = compare(key, x->key);
                if (cmp < 0) return get(x->left, key);
                else if (cmp > 0) return get(x->right, key);
                else return x->val;
        }
        
        Node* put(Node* h, Index key, Value val)
        {
                if(!h)
                {
                        h = new Node(key, val, 1, RED);
                        return h;
                }
                int cmp = compare(key, h->key);
                if(cmp < 0)
                        h->left  = put(h->left, key, val);
                else if(cmp > 0)
                        h->right = put(h->right, key, val);
                else
                        h->val = val;

                return balance(h);
        }

        Node* select(Node* x, int& k)
        {   // Return Node containing key of rank k.
                if(!x) return 0;
                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;
        }

        int   rank(Index& key, Node* x)
        {
                if(!x) return 0;
                int cmp = compare(key, 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);
        }

        Node* delMin(Node* h)
        {
                if (!(h->left)) return 0;
                if (!isRed(h->left) && !isRed(h->left->left))
                        h = moveRedLeft(h);
                h->left = delMin(h->left);
                return balance(h);
        }

        Node* del(Node* h, Index& key)
        {
                if(!h) return 0;
                int cmp = compare(key, h->key);
                /* search for key */
                if (cmp < 0)
                {
                        if (!isRed(h->left) && !isRed(h->left->left))
                                h = moveRedLeft(h);
                        h->left = del(h->left, key);
                }
                else
                {
                        if (isRed(h->left))
                                h = rotateRight(h);
                        if (!cmp && (!h->right))
                                return 0;
                        if (!isRed(h->right) && !isRed(h->right->left))
                                h = moveRedLeft(h);
                        if (!cmp)
                        {
                                /* replace with successor */
                                Node* x = min(h->right);
                                h->key = x->key;
                                h->val = x->val;
                                h->right = delMin(h->right);
                        }
                        else h->right = del(h->right, key);
                }
                return balance(h);
        }
        
        int   compare(Index& v, Index& w) const
        {
                if(v > w)      return  1;
                else if(v < w) return -1;
                return 0;
        }

        void inorder(Node* x, Queue<Index>& q)
        {
                if(!x) return;
                inorder(x->left, q);
                q.push(x->key);
                inorder(x->right, q);
        }
};

#endif

仍然采用中序遍历。

andalousie

总感觉在BST的initializer_list上才声明RED和BLACK的值有点晚。而且不能体现C和C++的特点。于是试着改了改代码，应用类内的enum类型。于是去掉后面的声明，并将

        const bool RED;
        const bool BLACK;

这两行改成了简单明了的

        enum { RED = true, BLACK = false };

编译通过，大家可以试一试。注意这个枚举类型是没有枚举名称的~