一个不太成熟的伸展树

andalousie · 发表于 2014-5-1 00:02:18

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

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

x

源代码

#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");
}

复制代码

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

[技术交流] 一个不太成熟的伸展树

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