参考文献：《算法导论（中文第二版）》Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein [著]
本文涉及的所有代码下载链接为：http://xule.ren/wp-content/uploads/2017/01/RBTree.zip
除却 AVLTree 外，由 R.Bayer 于 1972 年在论文《Symmetric binary B-trees: Data structure and maintenance algorithms》中提出的红黑树也是众多平衡树中的一种，红黑树在每个结点上增加了颜色域，通过对任何一条从根到叶子结点的路径上各个结点着色方式的限制，确保没有一条路径会比其他长出两倍，因而是接近平衡的。
红黑树具备以下五条红黑性质：
- 每个结点或是红的，或是黑的；
- 根结点是黑的；
- 每个叶结点（NIL）是黑的；
- 如果一个结点是红的，则它的两个儿子都是黑的；
- 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
为便于处理代码中的边界条件，采用一个哨兵来代表 NIL，哨兵结点的颜色域是黑的，其他域可以设置成任意值，所有指向 NULL 的指针都被替换成指向哨兵 NIL 的指针。使用哨兵后，就可以将结点 x 的 NIL 孩子视为一个其父结点为 x 的普通结点。从某个结点 x 出发（不包括该结点）到达一个叶结点的任意一条路径上，黑色结点的个数为该结点 x 的黑高度，红黑树的黑高度定义为其根结点的黑高度。一棵有 n 个内结点的红黑树的高度至多为 2 log(n+1)。
红黑树结点的定义如下，本文的实现不包含 parent 指针域
enum Color { R, B };
/**
* @brief Node type of a balanced binary search tree(RB tree).
*
* @tparam _Key Type of key objects.
* @tparam _Value Type of mapped objects.
*/
template <typename _Key, typename _Value>
class RBNode
{
public:
RBNode() : key(), value(), left(NULL), right(NULL), color(Color::B) {}
RBNode(_Key k, _Value v, RBNode<_Key, _Value> *NIL) : key(k), value(v), left(NIL), right(NIL), color(Color::R) {}
_Key key; ///< key of this node.
_Value value; ///< value of this node.
RBNode *left; ///< pointing to the left child node of this node.
RBNode *right; ///< pointing to the right child node of this node.
Color color; ///< color.
};
红黑树的定义如下
#ifndef __RBTREE_H__
#define __RBTREE_H__
#include <cstdlib>
#include <vector>
#include <stack>
#include <functional>
#include <cassert>
/**
* @brief A balanced binary search tree(RB tree), which can be retrieved based on a key, in logarithmic time.
*
* @tparam _Key Type of key objects.
* @tparam _Value Type of mapped objects.
* @tparam _Compare Comparison function object type, defaults to less<_Key>.
*/
template <typename _Key, typename _Value, typename _Compare = std::less<_Key> >
class RBTree
{
public:
/** @name constructors, destructor of RBTree. */
///@{
RBTree() : node_count(0), key_compare(), root(NULL) { NIL = new RBNode<_Key, _Value>; }
RBTree(const _Compare& _compare) : node_count(0), key_compare(), root(NULL) { NIL = new RBNode<_Key, _Value>; }
RBTree(const RBTree& rhs) : node_count(rhs.node_count), key_compare(rhs.key_compare), root(rhs.root), NIL(rhs.NIL) {}
~RBTree() { clear(); delete NIL; }
///@}
RBTree& operator=(const RBTree& rhs)
{
node_count = rhs.node_count;
key_compare = rhs.key_compare;
root = rhs.root;
NIL = rhs.NIL;
return *this;
}
/** @name APIs of RBTree. */
///@{
/** @brief return true if RBTree has no nodes. */
bool empty() { return node_count == 0; }
/** @brief return the number of nodes of RBTree. */
size_t size() { return node_count; }
/** @brief return the left-most node of RBTree. */
RBNode<_Key, _Value>* minimum();
/** @brief return the right-most node of RBTree. */
RBNode<_Key, _Value>* maximum();
/** @brief return the point to the finding node if found, return NULL if not found. */
RBNode<_Key, _Value>* find(_Key k);
/**
* @brief insert a node.
*
* @param k key of RBNode.
* @param v value of RBNode.
* @return point to the inserted RBNode.
*/
RBNode<_Key, _Value>* insert(_Key k, _Value v);
/** @brief erase a node only need adjust points. */
bool erase(_Key k);
/** @brief erase all the nodes of RBTree. */
void clear();
///@}
/** @name Traverse methods of RBTree. */
///@{
void preOrderTraverse(std::vector<RBNode<_Key, _Value>* >& vec);
void inOrderTraverse(std::vector<RBNode<_Key, _Value>* >& vec);
void postOrderTraverse(std::vector<RBNode<_Key, _Value>* >& vec);
///@}
/** @name Debug methods of RBTree. */
///@{
void validateBlackHeight();
void fetchBlackHeight(RBNode<_Key, _Value> *node, int& ph, int& h);
///@}
private:
/** @name Critical methods of RBTree. */
///@{
/** @brief rebalance after inserting a node. */
void _insertRebalance(RBNode<_Key, _Value> *p, std::vector<RBNode<_Key, _Value>* >& S);
/** @brief rebalance after erasing a node. */
void _eraseRebalance(RBNode<_Key, _Value> *p, std::vector<RBNode<_Key, _Value>* >& S);
/** @brief execute left rotate as to node p. */
RBNode<_Key, _Value>* leftRotate(RBNode<_Key, _Value> **p);
/** @brief execute right rotate as to node p. */
RBNode<_Key, _Value>* rightRotate(RBNode<_Key, _Value> **p);
///@}
private:
size_t node_count; ///< maintaining the number of nodes of RBTree.
_Compare key_compare; ///< key compare predicate of RBNode.
RBNode<_Key, _Value> *root; ///< root node of RBTree.
RBNode<_Key, _Value> *NIL; ///< sentinel node of RBTree.
};
#endif /* __RBTREE_H__ */
之前文章已经叙述过的方法不再赘述，注意哨兵结点 NIL 在构造函数中被创建，在析构函数中被销毁。
旋转操作
红黑树有左旋和右旋两种对称的旋转方式。当在某个结点 x 上做左旋时，其右孩子不能为 NIL，左旋以 x 到 y 之间的链为 “支轴” 进行，它使 y 成为该子树新的根，x 成为 y 的左孩子，而 y 的左子树则成为 x 的右子树。
两种旋转的实现代码如下
template <typename _Key, typename _Value, typename _Compare>
RBNode<_Key, _Value>* RBTree<_Key, _Value, _Compare>::leftRotate(RBNode<_Key, _Value> **p)
{
RBNode<_Key, _Value> *q = (*p)->right;
(*p)->right = q->left;
q->left = *p;
return q;
}
template <typename _Key, typename _Value, typename _Compare>
RBNode<_Key, _Value>* RBTree<_Key, _Value, _Compare>::rightRotate(RBNode<_Key, _Value> **p)
{
RBNode<_Key, _Value> *q = (*p)->left;
(*p)->left = q->right;
q->right = *p;
return q;
}
注意返回的 q 需要在函数调用处赋给原来 p 的父结点的左孩子指针域或是右孩子指针域。
插入操作
首先找到待插结点的合适位置并插入，由于没有 parent 指针域，在此沿树下降的过程中要用栈记录下降路径，随后进行重平衡。
插入部分实现如下，在空树中插入第一个结点的情况需要分开处理
template <typename _Key, typename _Value, typename _Compare>
RBNode<_Key, _Value>* RBTree<_Key, _Value, _Compare>::insert(_Key k, _Value v)
{
if (root == NULL)
{
root = new RBNode<_Key, _Value>(k, v, NIL);
root->color = Color::B;
++node_count;
return root;
}
RBNode<_Key, _Value> *p = root;
std::vector<RBNode<_Key, _Value>* > S;
S.reserve(32);
while (p != NIL)
{
S.push_back(p);
if (key_compare(k, p->key)) // k < p->key
p = p->left;
else if (key_compare(p->key, k)) // k > p->key
p = p->right;
else // k == p->key
return NULL;
}
p = new RBNode<_Key, _Value>(k, v, NIL);
RBNode<_Key, _Value> *q = S.back(), *r = p;
if (q->key > p->key)
q->left = p;
else
q->right = p;
++node_count;
_insertRebalance(p, S);
return r;
}
新插入结点初始设置为红色，插入操作只会破坏红黑树的性质 2 或 4，前者在新插入结点为根时被破坏，后者在新插入结点的父结点为红色时被破坏，重平衡操作着重决处理后者。性质 4 被破坏时，若新插入结点的父结点为新插入结点的祖父结点的左孩子，分为三种情况：
情况 1：新插入结点 z 的叔叔 y 是红色的
可以将 z 的父结点和 y 都着为黑色以解决 z 和其父结点都是红色的问题，将 z 的祖父结点着为红色以保持性质 5，然后把 z 的祖父结点当作新增的结点 z 来重复处理，指针 z 在树中上移两层。
情况 2：新插入结点 z 的叔叔 y 是黑色的，而且 z 是右孩子
情况 3：新插入结点 z 的叔叔 y 是黑色的，而且 z 是左孩子
在情况 2 中 z 是其父结点的右孩子，可以对其父结点使用一个左旋将情况 2 转变为情况 3，在情况 3 中，改变某些结点颜色并作一次右旋以保持性质 5，此时 z 的父结点为黑色，所有处理到此完毕。
情况 1 不做任何旋转，x 指针沿树上升的次数至多为 log n 次，一旦进入情况 3 则处理结束，因此插入操作最多执行两次旋转，花费 O(log n) 时间。三种情况及其对称的另三种情况的实现代码如下
template <typename _Key, typename _Value, typename _Compare>
void RBTree<_Key, _Value, _Compare>::_insertRebalance(RBNode<_Key, _Value> *p, std::vector<RBNode<_Key, _Value>* >& S)
{
int h = static_cast<int>(S.size()); // height of p
while (h > 0 && S[h-1]->color == Color::R)
{
RBNode<_Key, _Value> *q = S[h-1], *r = S[h-2]; // q is parent of p, r is parent of q
h -= 2; // now, S[h] is r
if (q == r->left)
{
RBNode<_Key, _Value> *t = r->right; // t is uncle of p
if (t->color == Color::R)
{
q->color = Color::B;
t->color = Color::B;
r->color = Color::R;
p = r;
}
else
{
if (p == q->right)
{
if (q == r->left)
r->left = leftRotate(&q);
else
r->right = leftRotate(&q);
p->color = Color::B;
}
else
q->color = Color::B;
r->color = Color::R;
if (h > 0) // r is not the root
{
if (r == S[h-1]->left)
S[h-1]->left = rightRotate(&r);
else
S[h-1]->right = rightRotate(&r);
}
else // r is the root
root = rightRotate(&r);
break;
}
}
else // (q == r->right)
{
RBNode<_Key, _Value> *t = r->left; // t is uncle of p
if (t->color == Color::R)
{
q->color = Color::B;
t->color = Color::B;
r->color = Color::R;
p = r;
}
else
{
if (p == q->left)
{
if (q == r->left)
r->left = rightRotate(&q);
else
r->right = rightRotate(&q);
p->color = Color::B;
}
else
q->color = Color::B;
r->color = Color::R;
if (h > 0) // r is not the root
{
if (r == S[h-1]->left)
S[h-1]->left = leftRotate(&r);
else
S[h-1]->right = leftRotate(&r);
}
else // r is the root
root = leftRotate(&r);
break;
}
}
}
root->color = Color::B;
}
删除操作
若树只有树根一个结点并且树根就是需要删除的结点，这种情况需要单独处理。其他情况中，若待删除结点左子树不为空，则采用前驱替代的方式删除其前驱，若待删除结点的右子树不为空，则采用后继替代的方式删除其后继，若待删除结点左右子树都为空，则直接删除其自身。同插入操作一样，删除操作也是先删除，再调整，在沿树下降的过程中采用栈来记录下降路径
template <typename _Key, typename _Value, typename _Compare>
bool RBTree<_Key, _Value, _Compare>::erase(_Key k)
{
if (root == NULL)
return false;
if (node_count == 1)
{
if (root->key != k)
return false;
delete root;
root = NULL;
node_count = 0;
return true;
}
RBNode<_Key, _Value> *p = root;
std::vector<RBNode<_Key, _Value>* > S;
S.reserve(32);
while (p != NIL)
{
S.push_back(p);
if (key_compare(k, p->key)) // k < p->key
p = p->left;
else if (key_compare(p->key, k)) // k > p->key
p = p->right;
else // k == p->key
break;
}
if (p == NIL)
return false;
RBNode<_Key, _Value> *q = p, *r = q;
if (p->left != NIL) // q is predecessor of p
{
q = p->left;
S.push_back(q);
while (q->right != NIL)
{
r = q;
q = q->right;
S.push_back(q);
}
if (q == r->left)
r->left = q->left;
else
r->right = q->left;
}
else if (p->right != NIL) // q is successor of p
{
q = p->right;
S.push_back(q);
while (q->left != NIL)
{
r = q;
q = q->left;
S.push_back(q);
}
if (q == r->left)
r->left = q->right;
else
r->right = q->right;
}
S.pop_back(); // let S.back() == parent of q
if (q != p)
{
p->key = q->key;
p->value = q->value;
}
else
{
if (q == S.back()->left)
S.back()->left = NIL;
else
S.back()->right = NIL;
}
if (q->color == Color::B)
_eraseRebalance(p->left != NIL ? q->left : q->right, S);
delete q;
--node_count;
return true;
}
将 x 视为还有额外的一层黑色以保持性质 5，x 的颜色域仍然是红（如果 x 是红黑的）或黑（如果 x 是双重黑色），则删除操作可能破坏性质 1, 2, 4，调整思路是将额外的黑色沿树上移，直到
- x 指向一个红黑结点，此时将 x 单独着为黑色；
- x 指向根，这时可以简单地消除那层额外的黑色，或者
- 做必要的旋转和颜色修改
当 x 是其父结点的左孩子时，分为四种情况
情况 1：x 的兄弟 w 是红色的
因为 w 必须有黑色孩子，可以改变 w 和 x 的父结点的颜色，再对 x 的父结点做一次左旋，而且红黑性质得以保持。现在 x 的新兄弟是旋转之前 w 的某个黑色孩子，这样就将情况 1 转换为了情况 2, 3, 4。
情况 2：x 的兄弟 w 是黑色的，而且 w 的两个孩子都是黑色的
从 x 和 w 上去掉一重黑色，从而 x 只有一重黑色而 w 为红色，为了弥补这去掉的一重黑色，需要在原来是红色或黑色的 x 的父结点内新增一重额外黑色，通过以 x 的父结点为新结点 x 来重复循环。注意如果通过情况 1 进入情况 2，则新结点 x 是红黑色的，因为原来 x 的父结点是红色的，因此循环结束。
情况 3：x 的兄弟 w 是黑色的，w 的左孩子是红色的，右孩子是黑色的
可以交换 w 和其左孩子的颜色，并对 w 进行右旋，而红黑性质得以保持。现在 x 的兄弟 w 是一个有红色右孩子的黑结点，这样情况 3 转换成了情况 4。
情况 4：x 的兄弟 w 是黑色的，而且 w 的右孩子是红色的
对 x 的父结点做一次左旋，则 w 处于子树根的位置，通过将 w 保持为原来子树根（x 的父结点）的颜色，同时将 w 的两个新的子节点的颜色变为黑色，去掉 x 的额外一重黑色，从而整个问题得到了解决，将 x 置为根后，循环结束。
情况 1, 3, 4 在各执行一定次数的颜色修好和至多三次旋转后便结束，情况 2 是唯一可以引起循环重复的情况，其中指针 x 沿树上升的次数至多为 log n 次，且不执行任何旋转。因此删除操作至多执行三次旋转，花费 O(log n) 时间。
实现代码如下
template <typename _Key, typename _Value, typename _Compare>
void RBTree<_Key, _Value, _Compare>::_eraseRebalance(RBNode<_Key, _Value> *p, std::vector<RBNode<_Key, _Value>* >& S)
{
int h = static_cast<int>(S.size()); // height of p
while (p != root && p->color == Color::B)
{
RBNode<_Key, _Value> *q = S[h-1], *r = h > 1 ? S[h-2] : NULL; // q is parent of p, r is parent of q
if (p == q->left)
{
RBNode<_Key, _Value> *w = q->right; // w is brother of p
if (w->color == Color::R)
{
w->color = Color::B;
q->color = Color::R;
if (r != NULL)
{
if (q == r->left)
r = r->left = leftRotate(&q);
else
r = r->right = leftRotate(&q);
}
else
r = root = leftRotate(&q);
S.back() = w;
S.push_back(q);
++h;
w = q->right;
}
if (w->left->color == Color::B && w->right->color == Color::B)
{
w->color = Color::R;
p = q;
S.pop_back();
--h;
}
else
{
if (w->right->color == Color::B)
{
w->left->color = Color::B;
w->color = Color::R;
q->right = rightRotate(&w);
w = q->right;
}
w->color = q->color;
q->color = Color::B;
w->right->color = Color::B;
if (r != NULL)
{
if (q == r->left)
r->left = leftRotate(&q);
else
r->right = leftRotate(&q);
}
else
root = leftRotate(&q);
p = root;
}
}
else
{
RBNode<_Key, _Value> *w = q->left; // w is brother of p
if (w->color == Color::R)
{
w->color = Color::B;
q->color = Color::R;
if (r != NULL)
{
if (q == r->left)
r = r->left = rightRotate(&q);
else
r = r->right = rightRotate(&q);
}
else
r = root = rightRotate(&q);
S.back() = w;
S.push_back(q);
++h;
w = q->left;
}
if (w->left->color == Color::B && w->right->color == Color::B)
{
w->color = Color::R;
p = q;
S.pop_back();
--h;
}
else
{
if (w->left->color == Color::B)
{
w->right->color = Color::B;
w->color = Color::R;
q->left = leftRotate(&w);
w = q->left;
}
w->color = q->color;
q->color = Color::B;
w->left->color = Color::B;
if (r != NULL)
{
if (q == r->left)
r->left = rightRotate(&q);
else
r->right = rightRotate(&q);
}
else
root = rightRotate(&q);
p = root;
}
}
}
p->color = Color::B;
}
test
为验证性质 5 在插入删除操作后不被破坏，函数 validateBlackHeight() 验证根结点至所有叶子结点路径上黑结点的数目是否一致
template <typename _Key, typename _Value, typename _Compare>
void RBTree<_Key, _Value, _Compare>::validateBlackHeight()
{
int ph = -1, h = 0;
fetchBlackHeight(root, ph, h);
}
template <typename _Key, typename _Value, typename _Compare>
void RBTree<_Key, _Value, _Compare>::fetchBlackHeight(RBNode<_Key, _Value> *node, int &ph, int& h)
{
if (node != NULL)
{
h += node->color == Color::B ? 1 : 0;
if (node->left == NIL && node->right == NIL)
{
if (ph == -1)
ph = h;
assert(h == ph);
}
fetchBlackHeight(node->left, ph, h);
fetchBlackHeight(node->right, ph, h);
h -= node->color == Color::B ? 1 : 0;
}
}
对红黑树插入删除操作的测试代码如下：
template <typename _Key, typename _Value>
void printTraverseResult(std::vector<RBNode<_Key, _Value>* >& v)
{
for (size_t i = 0; i < v.size(); ++i)
cout << v[i]->key << '(' << (v[i]->color == Color::R ? 'R' : 'B') << ") ";
cout << endl;
}
void fillRBTree(RBTree<int, double>& rbTree)
{
rbTree.insert(1, 3.23);
rbTree.insert(2, 1.34);
rbTree.insert(3, 8.36);
rbTree.insert(4, 9.73);
rbTree.insert(5, 7.18);
rbTree.insert(6, 7.51);
rbTree.insert(7, 8.13);
rbTree.insert(16, 4.16);
rbTree.insert(15, 2.86);
rbTree.insert(14, 1.01);
rbTree.insert(13, 5.69);
rbTree.insert(12, 4.97);
rbTree.insert(11, 9.61);
rbTree.insert(10, 3.27);
rbTree.insert(8, 7.12);
rbTree.insert(9, 8.69);
/*
* After fill, the structure of RB tree looks:
* 4(B)
*
* / \
*
* 2(B) 13(R)
* / \ / \
* 1(B) 3(B) 8(B) 15(B)
* / \ / \
* 6(R) 11(R) 14(B) 16(B)
* / \ / \
* 5(B)7(B) 10(B)12(B)
* /
* 9(R)
*/
}
int main(int argc, char *argv[])
{
cout << "Test RBTree methods: " << endl;
RBTree<int, double> rbTree;
fillRBTree(rbTree);
cout << "before erase :\n";
std::vector<RBNode<int, double>* > preOrderRB, inOrderRB, postOrderRB;
rbTree.preOrderTraverse(preOrderRB);
rbTree.inOrderTraverse(inOrderRB);
rbTree.postOrderTraverse(postOrderRB);
cout << "PreOrder: "; printTraverseResult(preOrderRB);
cout << "InOrder: "; printTraverseResult(inOrderRB);
cout << "PostOrder: "; printTraverseResult(postOrderRB);
preOrderRB.clear(); inOrderRB.clear(); postOrderRB.clear();
rbTree.erase(1);
/*
* After erase 1, the structure of RB tree looks:
* 13(B)
*
* / \
*
* 8(R) 15(B)
* / \ / \
* 4(B) 11(B) 14(B) 16(B)
* / \ / \
* 2(B) 6(R) 10(B) 12(B)
* \ / \ /
* 3R 5B 7B 9R
*/
cout << "after erase :\n";
rbTree.preOrderTraverse(preOrderRB);
rbTree.inOrderTraverse(inOrderRB);
rbTree.postOrderTraverse(postOrderRB);
cout << "PreOrder: "; printTraverseResult(preOrderRB);
cout << "InOrder: "; printTraverseResult(inOrderRB);
cout << "PostOrder: "; printTraverseResult(postOrderRB);
rbTree.clear();
return 0;
}
代码中的例子运行结果为
nonstd::map
STL 的关联容器 std::set, std::map 均由红黑树实现，只是其实现中使用了 parent 指针，本文的实现并未采用 parent 指针。
namespace nonstd
{
/**
* @brief A non-standard map made up of (key,value) pairs, which can be retrieved based on a key, in logarithmic time.
*
* @tparam _K Type of key objects.
* @tparam _V Type of mapped objects.
* @tparam _C Comparison function object type, defaults to less<_K>.
*/
template <typename _K, typename _V, typename _C = std::less<_K> >
class map
{
public:
/** @name container typedefs for easy of use. */
///@{
typedef _K key_type;
typedef _V data_type;
typedef _V mapped_type;
typedef std::pair<const _K, _V> value_type;
typedef _C key_compare;
typedef RBNode<_K, _V>* iterator;
///@}
/** @name constructors, destructor of nonstd::map. */
///@{
map() : _M_t() {}
explicit map(const _C& __comp) : _M_t(__comp) {}
map(const map& __x) : _M_t(__x._M_t) { }
~map() { clear(); }
///@}
map& operator=(const map& __x) { _M_t = __x._M_t; return *this; }
/** @name APIs of nonstd::map. */
///@{
bool empty() { return _M_t.empty(); }
size_t size() { return _M_t.size(); }
iterator begin() { return _M_t.minimum(); }
iterator end() { return NULL; }
iterator find(const key_type& __x) { return _M_t.find(__x); }
size_t count(const key_type& __x) { return _M_t.find(__x) == end() ? 0 : 1; }
iterator insert(const value_type& __x) { return _M_t.insert(__x.first, __x.second); }
void erase(const key_type& __x) { _M_t.erase(__x); }
void clear() { _M_t.clear(); }
///@}
void validate() { _M_t.validateBlackHeight(); }
private:
RBTree<_K, _V, _C> _M_t; ///< Red-Black tree representing nonstd::map.
};
} // end namespace nonstd
下面的程序用来对 std::map 和 nonstd::map 的插入、删除、查找性能进行比较
#include "RBTree.h"
#include <time.h>
#include <iostream>
#include <map>
#include <algorithm> // random_shuffle
using std::cout;
using std::endl;
/**
* @brief convenience class, which prints procedure executing time between Timer's construction and its destruction.
*/
class Timer
{
public:
/** record constructing time in the constructor. */
explicit Timer(const char *s) : _note(s) { _start_time = clock(); }
~Timer() { cout << _note << elapsed() << "s." << endl; }
/** calculate how much time elapsed since constructed. */
inline double elapsed() { return static_cast<double>(clock() - _start_time) / CLOCKS_PER_SEC; }
private:
Timer(const Timer&);
Timer& operator=(const Timer&);
private:
std::string _note; ///< this string will be printed when timer elapsed.
clock_t _start_time; ///< record the time when the timer is constructed.
};
#define DATA_SCALE 1000000
#define FAIL_RATIO 0.30
inline double dblrand() { return static_cast<double>(rand())/RAND_MAX + (static_cast<double>(rand())/RAND_MAX * (1.0/RAND_MAX)); }
inline int idxrand(int minIdx, int maxIdx) { return rand() % (maxIdx - minIdx) + minIdx; }
int main(int argc, char *argv[])
{
cout << "performance evaluation of RBTree, compared with std::map which implemented by red-black tree.\n";
std::map<int, double> std_map;
nonstd::map<int, double> nonstd_map;
unsigned int seed = 1;
// srand(time(NULL));
srand(seed);
int i = 0;
// generate random keys and values
std::vector<int> keys;
std::vector<double> values;
keys.reserve(DATA_SCALE);
values.reserve(DATA_SCALE);
for (i = 0; i < DATA_SCALE; ++i)
{
keys.push_back(rand());
values.push_back(dblrand());
}
// determine the order of elements' index in the operations of insert(), erase() and find()
std::vector<int> insertOrder, eraseOrder, findOrder;
insertOrder.reserve(2*DATA_SCALE);
eraseOrder.reserve(DATA_SCALE);
findOrder.reserve(DATA_SCALE);
for (i = 0; i < DATA_SCALE; ++i) // 0-100%
{
insertOrder.push_back(i); // 100%
if (i % 4 == 0)
eraseOrder.push_back(i); // 25%
else if (i % 4 == 1)
findOrder.push_back(i); // 25%
}
for (i = 0; i < FAIL_RATIO*DATA_SCALE; ++i)
{
int idx = idxrand(0, DATA_SCALE);
insertOrder.push_back(idx); // FAIL_RATIO * 100%
}
for (i = 0; i < FAIL_RATIO*DATA_SCALE; i += 2)
{
int idx = idxrand(0, DATA_SCALE);
while (idx % 4 < 2)
idx = idxrand(0, DATA_SCALE);
eraseOrder.push_back(idx); // FAIL_RATIO * 50%
}
for (i = 0; i < FAIL_RATIO*DATA_SCALE; i += 2)
{
int idx = idxrand(0, DATA_SCALE);
while (idx % 4 < 2)
idx = idxrand(0, DATA_SCALE);
findOrder.push_back(idx); // FAIL_RATIO * 50%
}
std::random_shuffle(insertOrder.begin(), insertOrder.end()); // using built-in random generator
std::random_shuffle(eraseOrder.begin(), eraseOrder.end()); // using built-in random generator
std::random_shuffle(findOrder.begin(), findOrder.end()); // using built-in random generator
// execute operations of insert(), erase() and find() for both std::map and nonstd::map
{
Timer timer("insertion of std::map costs: ");
for (i = 0; i < DATA_SCALE * (1+FAIL_RATIO); ++i)
std_map.insert(std::pair<int, double>(keys[insertOrder[i]], values[insertOrder[i]]));
}
nonstd_map.validate();
{
Timer timer("insertion of nonstd::map costs: ");
for (i = 0; i < DATA_SCALE * (1+FAIL_RATIO); ++i)
nonstd_map.insert(std::pair<int, double>(keys[insertOrder[i]], values[insertOrder[i]]));
}
{
Timer timer("erasure of std::map costs: ");
for (i = 0; i < DATA_SCALE/2 * (1+FAIL_RATIO); ++i)
std_map.erase(keys[eraseOrder[i]]);
cout << "[erasure] std::map elements' count: " << std_map.size() << endl;
}
{
Timer timer("erasure of nonstd::map costs: ");
for (i = 0; i < DATA_SCALE/2 * (1+FAIL_RATIO); ++i)
nonstd_map.erase(keys[eraseOrder[i]]);
cout << "[erasure] nonstd::map elements' count: " << nonstd_map.size() << endl;
}
nonstd_map.validate();
{
Timer timer("finding of std::map costs: ");
int existCount = 0;
for (i = 0; i < DATA_SCALE/2 * (1+FAIL_RATIO); ++i)
if (std_map.find(keys[findOrder[i]]) != std_map.end())
++existCount;
cout << "std::map::find() exist elements' count: " << existCount << endl;
}
{
Timer timer("finding of nonstd::map costs: ");
int existCount = 0;
for (i = 0; i < DATA_SCALE/2 * (1+FAIL_RATIO); ++i)
if (nonstd_map.find(keys[findOrder[i]]) != nonstd_map.end())
++existCount;
cout << "nonstd::map::find() exist elements' count: " << existCount << endl;
}
std_map.clear();
nonstd_map.clear();
cout << "From comparsion, we can draw a conclusion that the performance of nonstd::map is slightly worse than std::map." << endl;
return 0;
}
使用代码中的规模设置，某次运行的结果如下（代码中在插入结束阶段和删除结束阶段都调用了 validate() 函数，并未出现断言不满足的情况，通过了性质 5 的验证，从而证明了实现的正确性）
可以看到 nonstd::map 的性能虽然比 std::map 的性能稍差（缺乏 parent 指针域，用栈记录路径导致的开销），但是还是非常接近的。