随机化二叉树

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 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) return 1;
else if(v < w) return -1;
else return 0;
}
};
/***********************************************************************
* 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 [low,high], 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;
}
#endif

复制代码

stack.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 [maxStack];
int _top;
};
template<class T>
void Stack<T>::Push(T i)
{
assert (_top<maxStack);
_arr [_top]=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 [_top-1];
}
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 return 0;
}
};
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测试通过

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

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

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

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

账号		自动登录	找回密码
密码			立即注册

[技术交流] 随机化二叉树

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块