共有回帖数 0 个
-
Red-Black Tree（红黑树）是一种自平衡二叉查找树，它在1972年由 Rudolf Bayer 发明，他称之为 “Symmetric Binary B-Tree”。Leo J. Guibas 和 Robert Sedgewick 在1978年写的一篇论文中把它命名为“Red-Black Tree”。它有良好的最坏情况下的运行时间，实践中也非常高效。它可以在 Ο(log n) 的时间内查找、插入、删 除。很多版本的 C++ STL 中使用了 Red-Black Tree。
一颗 Red-Black Tree 中的每个结点都带有颜色域，可以是红色或黑色（正如它的名字）。除了二叉搜索树的基本要求外，还有如下要求：
1。根和叶子（nil）是黑色的
2。每个红色结点的两个子结点都必须是黑色（不能出现连续的红色结点）
3。从任一节点到其后裔的叶子结点的每条路径都包含相同数目的黑色结点
下面给出 Red-Black Tree 的 top-down 实现，无需 parent 域、递归或者额外的栈，空间复杂度为 Θ(1)。
#include iterator
using namespace std;
template typename key_type
class RedBlackTree
{
public:
typedef typename iterator_traitsstruct node *::difference_type difference_type;
typedef size_t size_type;
RedBlackTree()
{
nil = new node;
nil-size = 0;
nil-red = false;
//nil-link[0] = nil;
//nil-link[1] = nil;
root = nil;
}
~RedBlackTree()
{
clear();
delete nil;
}
void clear()
{
clear(root);
root = nil;
}
void erase(const key_type &key);
void insert(const key_type &key);
const key_type &select(size_type rank);
private:
struct node
{
key_type key;
size_type size;
bool red;
node *link[2];
node() {}
node(const key_type &key, bool red) : key(key), size(1), red(red) {}
}*nil, *root;
void clear(node *root);
node *double_rotate(node *root, difference_type dir)
{
root-link[!dir] = rotate(root-link[!dir], !dir);
return rotate(root, dir);
}
bool is_red(node *root)
{
return root-red;
}
node *rotate(node *root, difference_type dir)
{
node *p = root-link[!dir];
root-link[!dir] = p-link[dir];
p-link[dir] = root;
p-size = root-size;
root-size -= p-link[!dir]-size+1;
root-red = true;
p-red = false;
return p;
}
};
template typename key_type
void RedBlackTreekey_type::clear(node *root)
{
if (root != nil)
{
clear(root-link[0]);
clear(root-link[1]);
delete root;
}
}
template typename key_type
void RedBlackTreekey_type::erase(const key_type &key)
{
difference_type dir = 1, prev_dir;
node *deleted_node = nil, head, *g, *p = nil, *q = &head;
head.link[0] = nil;
head.link[1] = root;
while (q-link[dir] != nil)
{
prev_dir = dir;
g = p; p = q; q = q-link[dir];
--q-size;
dir = q-key key;
if (!dir && !(key q-key)) //q-key == key
deleted_node = q;
if (is_red(q) || is_red(q-link[dir])) continue;
if (is_red(q-link[!dir]))
p-link[prev_dir] = rotate(q, dir), p = p-link[prev_dir];
else
{
node *s = p-link[!prev_dir];
if (s == nil) continue;
if (!is_red(s-link[0]) && !is_red(s-link[1]))
p-red = false, q-red = true, s-red = true; //color flip
else
{
difference_type dir2 = p != g-link[0];
g-link[dir2] = is_red(s-link[prev_dir]) ? double_rotate(p, prev_dir) : rotate(p, prev_dir);
g-link[dir2]-red = true; q-red = true;
g-link[dir2]-link[0]-red = false;
g-link[dir2]-link[1]-red = false;
}
}
}
if (deleted_node == nil) throw "not found";
deleted_node-key = q-key;
p-link[q != p-link[0]] = q-link[q-link[0] == nil];
delete q;
root = head.link[1];
if (root != nil) root-red = false;
}
template typename key_type
void RedBlackTreekey_type::insert(const key_type &key)
{
if (root == nil)
{
root = new node(key, false);
root-link[0] = nil; root-link[1] = nil;
return;
}
difference_type dir = 0, prev_dir;
node head, *t = &head, *g = nil, *p = nil, *q = root;
head.link[1] = root;
for (; q != nil; )
{
++q-size;
if (is_red(q-link[0]) && is_red(q-link[1]))
q-red = true, q-link[0]-red = false, q-link[1]-red = false; //color flip
if (is_red(q) && is_red(p))
{ //fix red violation
difference_type dir2 = g != t-link[0];
t-link[dir2] = q == p-link[prev_dir] ? rotate(g, !prev_dir) : double_rotate(g, !prev_dir);
if (q != p-link[prev_dir]) --p-size;
}
prev_dir = dir;
dir = q-key key;
if (g != nil) t = g;
g = p; p = q; q = q-link[dir];
}
q = new node(key, true);
q-link[0] = nil; q-link[1] = nil;
p-link[dir] = q;
if (is_red(p))
{ //fix red violation
difference_type dir2 = g != t-link[0];
t-link[dir2] = q == p-link[prev_dir] ? rotate(g, !prev_dir) : double_rotate(g, !prev_dir);
}
root = head.link[1];
root-red = false;
}
template typename key_type
const key_type &RedBlackTreekey_type::select(size_type rank)
{
node *p = root;
for(;;)
{
if (rank p-link[0]-size)
p = p-link[0];
else if (p-link[0]-size rank)
rank -= p-link[0]-size+1, p = p-link[1];
else break;
}
return p-key;
}
楼主 2016-06-09 09:20 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
