#include "rb_tree.h"
void _rb_tree_rotate_left(_rb_tree_node_base *x, _rb_tree_node_base* &root)
{
_rb_tree_node_base *y = x->right;
x->right = y->left;
if (y->left != 0)
y->left->parent = x;
y->parent = x->parent;
if (x == root)
root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->left = x;
x->parent = y;
}
void _rb_tree_rotate_right(_rb_tree_node_base *x, _rb_tree_node_base* &root)
{
_rb_tree_node_base *y = x->left;
x->left = y->right;
if (y->right != 0)
y->right->parent = x;
y->parent = x->parent;
if (x == root)
root = y;
else if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
y->right = x;
x->parent = y;
}
void _rb_tree_rebalance(_rb_tree_node_base *x, _rb_tree_node_base* &root)
{
x->color = _rb_tree_red;
while (x!= root && x->parent->color ==_rb_tree_red)
{
if (x->parent == x->parent->parent->left)
{
_rb_tree_node_base* y = x->parent->parent->right;
if (y && y->color == _rb_tree_red)
{
x->parent->color = _rb_tree_black;
y->color = _rb_tree_black;
x->parent->parent->color = _rb_tree_red;
x = x->parent->parent;
}
else
{
if (x == x->parent->right)
{
x = x->parent;
_rb_tree_rotate_left(x, root);
}
x->parent->color = _rb_tree_black;
x->parent->parent->color = _rb_tree_red;
_rb_tree_rotate_right(x->parent->parent,root);
}
}
else
{
_rb_tree_node_base* y = x->parent->parent->left;
if (y && y->color == _rb_tree_red)
{
x->parent->color = _rb_tree_black;
y->color = _rb_tree_black;
x->parent->parent->color = _rb_tree_red;
x = x->parent->parent;
}
else
{
if (x == x->parent->left)
{
x = x->parent;
_rb_tree_rotate_right(x,root);
}
x->parent->color = _rb_tree_black;
x->parent->parent->color = _rb_tree_red;
_rb_tree_rotate_left(x->parent->parent, root);
}
}
}
root->color = _rb_tree_black;
}
map-stl.zip （73个子文件） 
rb_Tree.vcxproj.filters 2KB rb_Tree.vcxproj 6KB STL_construct.h 275B rb_treeTest.cpp 638B alloc.h 350B LICENSE 9KB rb_tree_node.h 707B
.git index 5KB HEAD 23B refs heads master 41B tags remotes origin HEAD 32B objects pack pack-dd8d55c4494f1151f07219df8447e5a74f666e4f.pack 263KB pack-dd8d55c4494f1151f07219df8447e5a74f666e4f.idx 2KB info description 73B packed-refs 114B info exclude 240B logs HEAD 183B refs heads master 183B remotes origin HEAD 183B hooks post-update.sample 189B prepare-commit-msg.sample 1KB commit-msg.sample 896B pre-receive.sample 544B update.sample 4KB pre-commit.sample 2KB pre-rebase.sample 5KB applypatch-msg.sample 478B fsmonitor-watchman.sample 5KB push-to-checkout.sample 3KB pre-applypatch.sample 424B pre-push.sample 1KB pre-merge-commit.sample 416B config 307B .vs rb_Tree v14 .suo 7KB x64 Debug rb_Tree.tlog CL.write.1.tlog 870B rb_Tree.lastbuildstate 189B CL.command.1.tlog 2KB link.command.1.tlog 2KB link.read.1.tlog 3KB link.write.1.tlog 904B CL.read.1.tlog 21KB rb_Tree.pdb 636KB rb_tree.obj 10KB rb_Tree.Build.CppClean.log 330B rb_Tree.ilk 546KB Maptest.obj 354KB rb_Tree.log 155B vc140.idb 619KB
rb_Tree.exe 111KB vc140.pdb 452KB rb_tree.h 5KB STL_alloc.h 494B rb_tree_iterator.h 2KB Map.h 2KB .gitignore 302B rb_tree.cpp 2KB Maptest.cpp 717B Debug rb_Tree.tlog CL.write.1.tlog 2KB rb_Tree.lastbuildstate 191B CL.command.1.tlog 2KB link.command.1.tlog 1KB link.read.1.tlog 3KB link.write.1.tlog 442B CL.read.1.tlog 42KB rb_Tree.pdb 620KB rb_tree.obj 8KB rb_Tree.ilk 454KB Maptest.obj 236KB rb_Tree.log 429B vc140.idb 619KB rb_Tree.exe 80KB vc140.pdb 436KB construct.h 210B资源评论
