一个不太成熟的伸展树

andalousie

源代码

#include <iostream>
#include <string>

template<typename Index, typename Value>
class BST
{
protected:
        struct Node
        {
                Node (Index k, Value v)
                :key(k), val(v), left(0), right(0)
                {}
                Index key;                  // key
        Value val;                  // associated data
        Node *left, *right;         // left and right subtrees
        };
public:
        BST(): root(0) {}

        bool contains(Index& key) {
                return get(key) != 0;
        }

        // return value associated with the given key
        // if no such value, return null
        Value get(Index key) {
                root = splay(root, key);
                int cmp = compare(key, root->key);
                if (!cmp) return root->val;
                else      return 0; //Error for std::string
        }

        /*************************************************************************
        *  splay insertion
        *************************************************************************/
        void put(Index key, Value val) {
                // splay key to root
                if (!root)
                {
                        root = new Node(key, val);
                        return;
                }

                root = splay(root, key);

                int cmp = compare(key, root->key);

                // Insert new node at root
                if (cmp) 
                {
                        Node * n = new Node(key, val);
                        if (cmp < 0)
                        {
                                n->left     = root->left;
                                n->right    = root;
                                root->left  = 0;
                        }
                        else
                        {
                                n->right    = root->right;
                                n->left     = root;
                                root->right = 0;
                        }
                        root = n;
                }

                // It was a duplicate key. Simply replace the value
                else
                        root->val = val;
        }

        /*************************************************************************
        *  splay insertion
        *************************************************************************/
        /* This splays the key, then does a slightly modified Hibbard deletion on
         * the root (if it is the node to be deleted; if it is not, the key was 
         * not in the tree). The modification is that rather than swapping the
         * root (call it node A) with its successor, it's successor (call it Node B)
         * is moved to the root position by splaying for the deletion key in A's 
         * right subtree. Finally, A's right child is made the new root's right 
         * child.
         */
        void remove(Index key) {
                if (!root) return; // empty tree

                root = splay(root, key);

                if (compare(key, root->key)) return;
                // It wasn't in the tree to remove

                if (!root->left)
                        root = root->right;
                else
                {
                        Node * x = root->right;
                        root = root->left;
                        splay(root, key);
                        root->right = x;
                }
        }

        int size() { return size(root); }
        int height() { return height(root); }
private:
        Node * root;
        int size(Node * x) { 
                if (!x) return 0;
                return 1 + size(x->left) + size(x->right);
        }
        int height(Node * x) {
                if (!x) return 0;
                return 1 + (height(x->left) > height(x->right)
                                          ? height(x->left) : height(x->right));
        }

        /*************************************************************************
        *  splay function
        *************************************************************************/
        // splay key in the tree rooted at Node h. If a node with that key exists,
        //   it is splayed to the root of the tree. If it does not, the last node
        //   along the search path for the key is splayed to the root.
        Node * splay(Node * h, Index key)
        {
                if (!h) return 0;

                int cmp1 = compare(key, h->key);

                if (!cmp1) return h;

                bool left = cmp1 < 0 ? true : false;
                Node * x = left ? h->left : h->right;
                // key not in tree, so we're done
                if (!x) return h;

                int cmp2 = compare(key, x->key);
                if      (cmp2 < 0)
                {
                        x->left = splay(x->left, key);
                        if (left)
                                h = rotateRight(h);
                        else if (x->left)
                                x = rotateRight(x);
                }
                else if (cmp2 > 0)
                {
                        x->right = splay(x->right, key);
                        if (!left)
                                h = rotateLeft(h);
                        else if (x->right)
                                x = rotateLeft(x);
                }

                x = left ? h->left : h->right; //Revise
                if (!x) return h;
                return left ? rotateRight(h) : rotateLeft(h);
        }

        /*************************************************************************
        *  helper BST functions
        *************************************************************************/

        // right rotate
        Node * rotateRight(Node * h) {
                Node * x = h->left;
                h->left  = x->right;
                x->right = h;
                return x;
        }

        // left rotate
        Node * rotateLeft(Node * h) {
                Node * x = h->right;
                h->right = x->left;
                x->left  = h;
                return x;
        }

        int   compare(Index& v, Index& w) const
        {
                if     (v > w) return  1;
                else if(v < w) return -1;
                else           return  0;
        }
};

int main()
{
        BST<std::string, std::string> st;

        st.put("www.cs.princeton.edu",   "128.112.136.11");
        st.put("www.cs.princeton.edu",   "128.112.136.35");
        st.put("www.princeton.edu",      "128.112.130.211");
        st.put("www.math.princeton.edu", "128.112.18.11");
        st.put("www.yale.edu",           "130.132.51.8");
        st.put("www.amazon.com",         "207.171.163.90");
        st.put("www.simpsons.com",       "209.123.16.34");
        st.put("www.stanford.edu",       "171.67.16.120");
        st.put("www.google.com",         "64.233.161.99");

        std::cout << st.get("www.cs.princeton.edu") << std::endl;
        std::cout << st.get("www.princeton.edu") << std::endl;
        st.remove("www.yale.edu");
        st.remove("www.princeton.edu");
}