论坛 › 数据结构与算法 › 随机化二叉树

andalousie 发表于 2014-4-27 15:26:53

随机化二叉树

本帖最后由 andalousie 于 2014-4-27 15:33 编辑

感觉自己好久没在鱼C上发东西了，虽然总是签到。
今天发一个随机化二叉树吧，包含了中序遍历的迭代器。
和往常一样，直接上代码~
RandomizedBST.cpp#include <iostream>
#include <string>
#include "Random.h"
#include "stack.h"

template<typename Index, typename Value> class BSTIterator;

template<typename Index, typename Value>
class BST
{
protected:
        struct Node
        {
                Node (Index k, Value v)
                :key(k), val(v), left(0),
                right(0), N(1)
                {}
                Index key;                  // key
      Value val;                  // associated data
      Node *left, *right;         // left and right subtrees
      int   N;                  // size of subtree rooted at this node
        };
public:
        typedef BSTIterator<Index, Value> iterator;
        friend class BSTIterator<Index, Value>;

        BST(): root(0) {}
        /*************************************************************************
        *BST search
        *************************************************************************/
        bool contains(Index& key) {
                return get(key) != 0;
        }

        // return value associated with the given key
        // if no such value, return null
        Value get(const Index& key) {
                return get(root, key);
        }

        /*************************************************************************
        *randomized insertion
        *************************************************************************/
        void put(Index key, Value val) {
                root = putRoot(root, key, val);
        }

        // remove and return value associated with given interval;
        // if no such interval exists return null
        Value remove(Index key) {
                Value value = get(key);
                root = remove(root, key);
                return value;
        }

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

        Index min()
        {
                Index key = 0;
                for (Node * x = root; x; x = x->left)
                        key = x->key;
                return key;
        }

        Index max()
        {
                Index key = 0;
                for (Node * x = root; x; x = x->right)
                        key = x->key;
                return key;
        }

        int size() { return size(root); }
        int height() { return height(root); }

        iterator begin() { return iterator(root); }
        iterator end() { return iterator(0); }
private:
        Node * root;
        Random rnd;
        int size(Node * x) {
                if (!x) return 0;
                else         return x->N;
        }
        int height(Node * x) {
                if (!x) return 0;
                return 1 + (height(x->left) > height(x->right)
                                          ? height(x->left) : height(x->right));
        }

        //Private methods
        Value get(Node *x, Index key)
        {
                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;
        }

        // make new node the root with uniform probability
        Node * put(Node * x, Index key, Value val) {
                if (!x) return new Node(key, val);
                int cmp = compare(key, x->key);
                if (!cmp)
                {
                        x->val = val;
                        return x;
                }
                if (rnd.bernoulli(1.0 / (size(x) + 1.0))) return putRoot(x, key, val);
                if (cmp < 0)x->left= put(x->left,key, val);
                else          x->right = put(x->right, key, val);
                fix(x);
                return x;
        }

        Node * putRoot(Node * x, Index key, Value val) {
                if (!x) return new Node(key, val);
                int cmp = compare(key, x->key);
                if (!cmp)
                {
                        x->val = val;
                        return x;
                }
                if (cmp < 0){ x->left= putRoot(x->left,key, val); x = rotR(x); }
                else          { x->right = putRoot(x->right, key, val); x = rotL(x); }
                return x;
        }

        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;
        }

        /*************************************************************************
        *deletion
        *************************************************************************/
        Node * joinLR(Node * a, Node * b) {
                if (!a) return b;
                if (!b) return a;

                if (rnd.bernoulli((double) size(a) / (size(a) + size(b)))){
                        a->right = joinLR(a->right, b);
                        fix(a);
                        return a;
                }
                else {
                        b->left = joinLR(a, b->left);
                        fix(b);
                        return b;
                }
        }

        Node * remove(Node * h, Index key) {
                if (!h) return 0;
                int cmp = compare(key, h->key);
                if      (cmp < 0) h->left= remove(h->left,key);
                else if (cmp > 0) h->right = remove(h->right, key);
                else            h = joinLR(h->left, h->right);
                fix(h);
                return h;
        }

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

        // fix auxilliar information (subtree count and max fields)
        void fix(Node * x) {
                if (!x) return;
                x->N = 1 + size(x->left) + size(x->right);
        }

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

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

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

/***********************************************************************
*Iterate using inorder traversal using a stack.
*Iterating through N elements takes O(N) time.
***********************************************************************/
template<typename Index, typename Value>
class BSTIterator
{
        typedef typename BST<Index, Value>::Node Node;
public:
        BSTIterator(Node * x)
        {
                do_push(x);
                if (stack.Empty())
                        _cur = 0;
                else
                {
                        x = stack.Top();
                        stack.Pop();
                        _cur = x;
                        do_push(x->right);
                }
        }

        void operator =(const BSTIterator& it)
        {
                stack = it.stack;
                _cur= it._cur;
        }

        bool operator == (const BSTIterator& it)
        {
                return _cur == it._cur;
        }

        bool operator != (const BSTIterator& it)
        {
                return _cur != it._cur;
        }

        BSTIterator& operator ++ ()
        {
                if (isEnd())
                {
                        _cur = 0;
                        return *this;
                }
                Node * x = stack.Top(); stack.Pop();
                _cur = x;
                do_push(x->right);
                return *this;
        }

        Index operator * () const { return _cur->key; }
private:
        Stack<Node *> stack;
        Node *      _cur;

        bool isEnd() { return stack.Empty(); }
        void do_push(Node * x)
        {
                while (x)
                {
                        stack.Push(x);
                        x = x->left;
                }
        }
};

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;

        BST<std::string, std::string>::iterator it = st.begin();
        while(it != st.end())
        {
                std::cout << *it << " " << st.get(*it) << std::endl;
                ++it;
        }
}Random.h#ifndef RANDOM_H
#define RANDOM_H

// Random class
// This code assumes 32-bit ints,
// which are standard on modern compilers.
//
// CONSTRUCTION: with (a) no initializer or (b) an integer
//   that specifies the initial state of the generator
//
// ******************PUBLIC OPERATIONS*********************
//   Return a random number according to some distribution:
// int randomInt( )                     --> Uniform, 1 to 2^31-1
// int random0_1( )                     --> Uniform, 0 to 1
// int randomInt( int low, int high )   --> Uniform low..high

class Random
{
      public:
                explicit Random( int initialValue = 1 );

                int      randomInt( );
                double   random0_1( );
                int      randomInt( int low, int high );
                bool   bernoulli( double p );

      private:
                int state;
};

//Implementations

static const int A = 48271;
static const int M = 2147483647;
static const int Q = M / A;
static const int R = M % A;

/**
* Construct with initialValue for the state.
*/
Random::Random( int initialValue )
{
    if( initialValue < 0 )
      initialValue += M;

    state = initialValue;
    if( state == 0 )
      state = 1;
}

/**
* Return a pseudorandom int, and change the
* internal state.
*/
inline int Random::randomInt( )
{
    int tmpState = A * ( state % Q ) - R * ( state / Q );

    if( tmpState >= 0 )
      state = tmpState;
    else
      state = tmpState + M;

    return state;
}

/**
* Return a pseudorandom double in the open range 0..1
* and change the internal state.
*/
inline double Random::random0_1( )
{
    return static_cast<double>( randomInt() ) / M;
}

/**
* Return an int in the closed range , and
* change the internal state. This is a poor implementation and
* will be biased toward some numbers, especially if the range is large.
*/
inline int Random::randomInt( int low, int high )
{
    double partitionSize = static_cast<double>( M ) / ( high - low + 1 );

    return static_cast<int>( randomInt() / partitionSize ) + low;
}

/**
* Returns a bool, which is true with probability p, and false otherwise.
*/
inline bool Random::bernoulli(double p)
{
      if (!(p >= 0.0 && p <= 1.0))
                throw "Probability must be between 0.0 and 1.0";
      return random0_1() < p;
}

#endifstack.h#pragma once
#include <cassert>

const int maxStack=16;

template<class T>
class Stack
{
public:
      Stack():_top(0){}
      void Push(T i);
      void Pop();
      T    Top() const;
      bool Empty() const;
private:
      T    _arr ;
      int_top;
};

template<class T>
void Stack<T>::Push(T i)
{
      assert (_top<maxStack);
      _arr =i;
      ++_top;
}

template<class T>
void Stack<T>::Pop()
{
      assert (_top>0);
      --_top;
}

template<class T>
T Stack<T>::Top()const
{
      assert (_top>0);
      return _arr ;
}

template<class T>
bool Stack<T>::Empty() const
{
      return !_top;
}这三个文件就是一个完整的随机化二叉树
还有一个随机化二叉树的应用，区间树。#include <iostream>
#include <cassert>
#include "Random.h"

class Interval1D
{
public:
      const int low;// left endpoint
      const int high; // right endpoint
      Interval1D(int left, int right)
                :low(left), high(right)
      {}
      bool intersects(Interval1D& that) {
      if (that.high < low) return false;
      if (high < that.low) return false;
      return true;
    }
      bool contains(int x) {
      return (low <= x) && (x <= high);
    }
      int compareTo(Interval1D& that) {
      if      (low< that.low)return -1;
      else if (low> that.low)return +1;
      else if (high < that.high) return -1;
      else if (high < that.high) return +1;
      else                            return0;
    }
};

class IntervalST
{
      typedef int Value;
      struct Node
      {
                Node(Interval1D i, Value v)
                :inv(i), val(v), left(0),
                right(0), N(1), max(i.high)
                {}
                Interval1D inv;      // key
      Value val;                  // associated data
      Node *left, *right;         // left and right subtrees
      int N;                      // size of subtree rooted at this node
      int max;                  // max endpoint in subtree rooted at this node
      };
public:
      IntervalST(): root(0) {}
      /*************************************************************************
    *BST search
    *************************************************************************/
      bool contains(Interval1D& inv) {
      return get(inv) != 0;
    }

      // return value associated with the given key
    // if no such value, return null
    Value get(Interval1D& inv) {
      return get(root, inv);
    }

      /*************************************************************************
    *randomized insertion
    *************************************************************************/
    void put(Interval1D inv, Value val) {
      if (contains(inv))
                { std::cout << "duplicate" << std::endl; remove(inv);}
      root = randomizedInsert(root, inv, val);
    }

      // remove and return value associated with given interval;
    // if no such interval exists return null
    Value remove(Interval1D inv) {
      Value value = get(inv);
      root = remove(root, inv);
      return value;
    }

      // return an interval in data structure that intersects the given inteval;
    // return null if no such interval exists
    // running time is proportional to log N
      Interval1D search(Interval1D& inv) {
      return search(root, inv);
    }

      // look in subtree rooted at x
    Interval1D search(Node * x, Interval1D inv) {
      while (!x) {
            if (inv.intersects(x->inv))return x->inv;
            else if (!x->left)             x = x->right;
            else if (x->left->max < inv.low)x = x->right;
            else                                 x = x->left;
      }
      return Interval1D(0, 0);
    }

      // return *all* intervals in data structure that intersect the given interval
    // running time is proportional to R log N, where R is the number of intersections
    void searchAll(Interval1D& inv) { searchAll(root, inv); }

      // look in subtree rooted at x
    bool searchAll(Node * x, Interval1D inv) {
         bool found1 = false;
         bool found2 = false;
         bool found3 = false;
         if (!x)
            return false;
      if (inv.intersects(x->inv)) {
                        std::cout << '[' << x->inv.low
                              << ',' << x->inv.high << "]\n";
            found1 = true;
      }
      if (x->left && x->left->max >= inv.low)
            found2 = searchAll(x->left, inv);
      if (found2 || !x->left || x->left->max < inv.low)
            found3 = searchAll(x->right, inv);
      return found1 || found2 || found3;
    }

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

      //Private methods
      Value get(Node *x, Interval1D& inv)
      {
                if (!x) return 0;
                int cmp = inv.compareTo(x->inv);
                if      (cmp < 0) return get(x->left, inv);
                else if (cmp > 0) return get(x->right, inv);
                else            return x->val;
      }

      // make new node the root with uniform probability
    Node * randomizedInsert(Node * x, Interval1D inv, Value val) {
      if (!x) return new Node(inv, val);
      if (rnd.random0_1() * size(x) < 1.0) return rootInsert(x, inv, val);
      int cmp = inv.compareTo(x->inv);
      if (cmp < 0)x->left= randomizedInsert(x->left,inv, val);
      else          x->right = randomizedInsert(x->right, inv, val);
      fix(x);
      return x;
    }

      Node * rootInsert(Node * x, Interval1D inv, Value val) {
      if (!x) return new Node(inv, val);
      int cmp = inv.compareTo(x->inv);
      if (cmp < 0){ x->left= rootInsert(x->left,inv, val); x = rotR(x); }
      else          { x->right = rootInsert(x->right, inv, val); x = rotL(x); }
      return x;
    }

      /*************************************************************************
    *deletion
    *************************************************************************/
    Node * joinLR(Node * a, Node * b) {
      if (!a) return b;
      if (!b) return a;

      if (rnd.random0_1() * (size(a) + size(b)) < size(a)){
            a->right = joinLR(a->right, b);
            fix(a);
            return a;
      }
      else {
            b->left = joinLR(a, b->left);
            fix(b);
            return b;
      }
    }

      Node * remove(Node * h, Interval1D inv) {
      if (!h) return 0;
      int cmp = inv.compareTo(h->inv);
      if      (cmp < 0) h->left= remove(h->left,inv);
      else if (cmp > 0) h->right = remove(h->right, inv);
      else            h = joinLR(h->left, h->right);
      fix(h);
      return h;
    }

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

    // fix auxilliar information (subtree count and max fields)
    void fix(Node * x) {
      if (!x) return;
      x->N = 1 + size(x->left) + size(x->right);
      x->max = max3(x->inv.high, max(x->left), max(x->right));
    }

    int max(Node * x) {
      if (!x) return -1;
      return x->max;
    }

    // precondition: a is not null
    int max3(int a, int b, int c) {
                int max = ( a < b ) ? b : a;
      return ( ( max < c ) ? c : max );
    }

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

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

int main()
{
      IntervalST st;
      Random rand_inv;
      for (int i = 0; i < 50; i++) {
                int low= rand_inv.randomInt(0, 1000);
                int high = rand_inv.randomInt(0, 50) + low;
                Interval1D interval(low, high);
                st.put(interval, i);
      }
      Interval1D ready(400, 700);
      st.searchAll(ready);
}大家学习参考一下。

andalousie 发表于 2014-4-27 15:39:14

VS2008测试通过{:5_109:}

枫界易城 发表于 2014-4-27 16:58:12

感谢楼主分享！《，，，，，，

cable5881 发表于 2014-8-12 08:58:56

谢谢楼主分享！！！！！！！！

查看完整版本: 随机化二叉树