C++版本的二叉搜索树(LLRB平衡)
本帖最后由 andalousie 于 2014-3-1 17:19 编辑不久前我曾发布过一个未平衡的二叉搜索树，时至今日，我觉得是时候发布一个基本平衡的左偏红黑树(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;
boolcolor; // 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) return1;
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仍然采用中序遍历。
总感觉在BST的initializer_list上才声明RED和BLACK的值有点晚。而且不能体现C和C++的特点。于是试着改了改代码，应用类内的enum类型。于是去掉后面的声明，并将 const bool RED;
const bool BLACK;这两行改成了简单明了的 enum { RED = true, BLACK = false };编译通过，大家可以试一试。注意这个枚举类型是没有枚举名称的~
页:
[1]