返回信息流## 红黑树实现
### 以下是基于算法导论的思想的红黑树实现，当初为了方便调试，类内有一个打印红黑树的程序，因为版内有同学要求，所以放出来，大家可以改为普通二叉树的版本，大神们轻拍～
### 程序运行结果
https://bbs.byr.cn/att/ACM_ICPC/0/96459/296
### 程序代码
```C++
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
#include <string>
#include <unordered_map>
#include <tuple>
using namespace std;
static int x = []()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}();
template <class T>
void print_vec(vector<T> vec)
{
for(int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
cout << endl;
}
class RBT
{
public:
enum color {R, B};
RBT()
{
color_ = B;
}
RBT(int key, RBT * left = RBT::nil, RBT * right = RBT::nil)
{
key_ = key;
left_ = left;
right_ = right;
left->parent_ = this;
right->parent_ = this;
}
RBT(int key, color c, RBT * left = RBT::nil, RBT * right = RBT::nil)
{
new(this)RBT(key, left, right);
color_ = c;
}
void level_print(RBT * T)
{
if(T == RBT::nil)
return;
queue<RBT * > q;
RBT * t = T;
q.push(t);
q.push(RBT::nil);
while(q.empty() == false)
{
t = q.front();
q.pop();
if(t == RBT::nil)
{
if(q.empty() == false)
q.push(RBT::nil);
cout << endl;
}
else
{
cout << t->key_ << ' ';
if(t->left_ != RBT::nil)
q.push(t->left_);
if(t->right_ != RBT::nil)
q.push(t->right_);
}
}
}
vector<RBT * > get_inorder_tree_walk_vec(RBT * T)
{
vector<RBT * > vec;
stack<RBT * > s;
RBT * P = T;
while(P != RBT::nil || s.empty() == false)
{
while(P != RBT::nil)
{
s.push(P);
P = P->left_;
}
if(s.empty() == false)
{
P = s.top();
vec.push_back(P);
s.pop();
P = P->right_;
}
}
return vec;
}
unordered_map<RBT * , int> generate_x_ind_map(RBT * T)
{
vector<RBT * > inorder_vec = get_inorder_tree_walk_vec(T);
unordered_map<RBT *, int> ind_map;
int tmp_ind = 0;
for(int i = 0; i < inorder_vec.size(); i++)
{
ind_map[inorder_vec[i]] = tmp_ind;
tmp_ind += to_string(inorder_vec[i]->key_).size() + 3;
}
return ind_map;
}
void put(char c, int times)
{
for(int i = 0; i < times; i++)
cout << c;
}
void draw_tree_without_lines(RBT * T)
{
if(T == RBT::nil)
return;
unordered_map<RBT *, int> ind_map = generate_x_ind_map(T);
queue<RBT * > q;
RBT * t = T;
q.push(t);
q.push(RBT::nil);
int tmp_line_ind = 0;
int tmp_vec_ind = 0;
while(q.empty() == false)
{
t = q.front();
q.pop();
if(t == RBT::nil)
{
if(q.empty() == false)
{
q.push(RBT::nil);
tmp_line_ind = 0;
cout << endl;
}
}
else
{
put(' ', ind_map[t] - tmp_line_ind);
cout << '(' << t->key_ << ')';
tmp_line_ind += ind_map[t] - tmp_line_ind + 2 +
to_string(t->key_).size();
tmp_vec_ind ++;
if(t->left_ != RBT::nil)
q.push(t->left_);
if(t->right_ != RBT::nil)
q.push(t->right_);
}
}
}
vector<vector<RBT * > > generate_print_base(RBT * T)
{
vector<vector<RBT * > > base_vec;
if(T == RBT::nil)
return base_vec;
queue<RBT * > q;
RBT * t = T;
q.push(t);
q.push(RBT::nil);
base_vec.push_back(vector<RBT * >());
while(q.empty() == false)
{
t = q.front();
q.pop();
if(t == RBT::nil)
{
if(q.empty() == false)
{
q.push(RBT::nil);
base_vec.push_back(vector<RBT * >());
}
}
else
{
if(t->left_ != RBT::nil)
q.push(t->left_);
if(t->right_ != RBT::nil)
q.push(t->right_);
base_vec[base_vec.size() - 1].push_back(t);
}
}
return base_vec;
}
void draw_tree(RBT * T)
{
cout << "draw_tree, (R), [B] : " << endl;
unordered_map<RBT * , int> ind_map = generate_x_ind_map(T);
vector<vector<RBT * > > base_vec = generate_print_base(T);
for(int i = 0; i < base_vec.size(); i++)
{
int tmp_line_ind = 0;
int next_level_node_ind = 0;
vector<pair<int, char> > lr_sign_vec;
for(int j = 0; j < base_vec[i].size(); j++)
{
int tmp_node_ind = ind_map[base_vec[i][j]];
if(base_vec[i][j]->left_ != RBT::nil)
{
int omament_ind = ind_map[base_vec[i + 1][next_level_node_ind ++]] + 1;
int space_length = omament_ind - tmp_line_ind;
put(' ', space_length);
tmp_line_ind += space_length;
lr_sign_vec.push_back(make_pair(tmp_line_ind - 1, '/'));
int omament_length = tmp_node_ind - omament_ind;
put('_', omament_length);
tmp_line_ind += omament_length;
}
else
{
int space_length = tmp_node_ind - tmp_line_ind;
put(' ', space_length);
tmp_line_ind += space_length;
}
if(base_vec[i][j]->color_ == R)
cout << "\033[31m" << "(" << base_vec[i][j]->key_ << ")" << "\033[37m";
else if(base_vec[i][j]->color_ == B)
cout << "\033[1m\033[30m" << "[" << base_vec[i][j]->key_ << "]" << "\033[37m";
//cout << base_vec[i][j]->parent_->key_;
tmp_line_ind += 2 + to_string(base_vec[i][j]->key_).size();
if(base_vec[i][j]->right_ != RBT::nil)
{
int omament_ind = ind_map[base_vec[i + 1][next_level_node_ind]];
int omament_length = omament_ind - tmp_line_ind +
to_string(base_vec[i + 1][next_level_node_ind ++]->key_).size() + 2 - 1;
put('_', omament_length);
tmp_line_ind += omament_length;
lr_sign_vec.push_back(make_pair(tmp_line_ind, '\\'));
}
}
cout << endl;
int tmp_lr_sign_line_ind = 0;
for(int k = 0; k < lr_sign_vec.size(); k++)
{
int tmp_lr_sign_line_space_length = lr_sign_vec[k].first - tmp_lr_sign_line_ind;
put(' ', tmp_lr_sign_line_space_length);
cout << lr_sign_vec[k].second;
tmp_lr_sign_line_ind += (tmp_lr_sign_line_space_length + 1);
}
cout << endl;
}
}
void left_rotate(RBT * T, RBT * x)
{
RBT * y = x->right_;
x->right_ = y->left_;
if(x->right_ != RBT::nil)
x->right_->parent_ = x;
y->parent_ = x->parent_;
if(x->parent_ == RBT::nil)
T->root_ = y;
else if(x == x->parent_->left_)
x->parent_->left_ = y;
else
x->parent_->right_ = y;
y->left_ = x;
x->parent_ = y;
}
void right_rotate(RBT * T, RBT * x)
{
RBT * y = x->left_;
x->left_ = y->right_;
if(x->left_ != RBT::nil)
x->left_->parent_ = x;
y->parent_ = x->parent_;
if(x->parent_ == RBT::nil)
T->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_insert(RBT * T, RBT * z)
{
RBT * y = RBT::nil;
RBT * x = T->root_;
while(x != RBT::nil)
{
y = x;
if(z->key_ < x->key_)
x = x->left_;
else
x = x->right_;
}
z->parent_ = y;
if(y == RBT::nil)
T->root_ = z;
else if(z->key_ < y->key_)
y->left_ = z;
else
y->right_ = z;
z->left_ = RBT::nil;
z->right_ = RBT::nil;
z->color_ = R;
//cout << "---Before fixup---" << endl;
//draw_tree(T->root_);
rb_insert_fixup(T, z);
}
void rb_insert_fixup(RBT * T, RBT * z)
{
while(z->parent_->color_ == R)
{
if(z->parent_ == z->parent_->parent_->left_)
{
RBT * y = z->parent_->parent_->right_;
if(y->color_ == R)
{
z->parent_->color_ = B;
y->color_ = B;
z->parent_->parent_->color_ = R;
z = z->parent_->parent_;
//cout << "case 1" << endl;
//draw_tree(T->root_);
}
else
{
if(z == z->parent_->right_)
{
z = z->parent_;
left_rotate(T, z);
//cout << "case 2" << endl;
//draw_tree(T->root_);
}
z->parent_->color_ = B;
z->parent_->parent_->color_ = R;
right_rotate(T, z->parent_->parent_);
//cout << "case 3" << endl;
//draw_tree(T->root_);
}
}
else
{
RBT * y = z->parent_->parent_->left_;
if(y->color_ == R)
{
z->parent_->color_ = B;
y->color_ = B;
z->parent_->parent_->color_ = R;
z = z->parent_->parent_;
}
else
{
if(z == z->parent_->left_)
{
z = z->parent_;
right_rotate(T, z);
}
z->parent_->color_ = B;
z->parent_->parent_->color_ = R;
left_rotate(T, z->parent_->parent_);
}
}
}
T->root_->color_ = B;
}
void rb_transplant(RBT * T, RBT * u, RBT * v)
{
if(u->parent_ == RBT::nil)
T->root_ = v;
else if(u == u->parent_->left_)
u->parent_->left_ = v;
else
u->parent_->right_ = v;
v->parent_ = u->parent_;
}
RBT * tree_minimum(RBT * T)
{
while(T != RBT::nil && T->left_ != RBT::nil)
T = T->left_;
return T;
}
void rb_delete(RBT * T, RBT * z)
{
RBT * x;
RBT * y = z;
RBT::color y_ori_color = y->color_;
if(z->left_ == RBT::nil)
{
x = z->right_;
rb_transplant(T, z, z->right_);
}
else if(z->right_ == RBT::nil)
{
x = z->left_;
rb_transplant(T, z, z->left_);
}
else
{
y = tree_minimum(z->right_);
y_ori_color = y->color_;
x = y->right_;
if(y->parent_ == z)
x->parent_ = y;
else
{
rb_transplant(T, y, y->right_);
y->right_ = z->right_;
y->right_->parent_ = y;
}
rb_transplant(T, z, y);
y->left_ = z->left_;
y->left_->parent_ = y;
y->color_ = z->color_;
}
delete z;
z = nullptr;
if(y_ori_color == B)
rb_delete_fixup(T, x);
}
void rb_delete_fixup(RBT * T, RBT * x)
{
while(x != T->root_ && x->color_ == B)
{
if(x == x->parent_->left_)
{
RBT * w = x->parent_->right_;
if(w->color_ == R)
{
w->color_ = B;
x->parent_->color_ = R;
left_rotate(T, x->parent_);
w = x->parent_->right_;
}
if(w->left_->color_ == B && w->right_->color_ == B)
{
w->color_ = R;
x = x->parent_;
}
else
{
if(w->right_->color_ == B)
{
w->left_->color_ = B;
w->color_ = R;
right_rotate(T, w);
w = x->parent_->right_;
}
w->color_ = x->parent_->color_;
x->parent_->color_ = B;
w->right_->color_ = B;
left_rotate(T, x->parent_);
x = T->root_;
}
}
else
{
RBT * w = x->parent_->left_;
if(w->color_ == R)
{
w->color_ = B;
x->parent_->color_ = R;
right_rotate(T, x->parent_);
w = x->parent_->left_;
}
if(w->right_->color_ == B && w->left_->color_ == B)
{
w->color_ = R;
x = x->parent_;
}
else
{
if(w->left_->color_ == B)
{
w->right_->color_ = B;
w->color_ = R;
left_rotate(T, w);
w = x->parent_->left_;
}
w->color_ = x->parent_->color_;
x->parent_->color_ = B;
w->right_->color_ = B;
right_rotate(T, x->parent_);
x = T->root_;
}
}
}
x->color_ = B;
}
int key_;
RBT * left_ = RBT::nil;
RBT * right_ = RBT::nil;
RBT * parent_ = RBT::nil;
color color_;
static RBT * nil;
static RBT * root_;
};
RBT * RBT::nil = new RBT();
RBT * RBT::root_ = nullptr;
int main()
{
RBT * T = new RBT(11, RBT::B,
new RBT(2, RBT::R,
new RBT(1, RBT::B),
new RBT(7, RBT::B,
new RBT(5, RBT::R),
new RBT(8, RBT::R)
)
),
new RBT(14, RBT::B,
RBT::nil,
new RBT(15, RBT::R)
)
);
T->root_ = T;
/*
T->draw_tree(T);
T->left_rotate(T, T->left_);
T->draw_tree(T);
T->right_rotate(T, T->left_);
T->draw_tree(T);
*/
T->rb_insert(T, new RBT(4));
T->draw_tree(T->root_);
T->rb_delete(T->root_, T->root_->right_);
T->draw_tree(T->root_);
return 0;
}
```
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #96465同步于 2018/9/5
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【心得】如何打印一棵红黑树
firekisser
2018/9/5镜像同步7 回复
订阅后，新回复会通过你的通知中心匿名送达。
7 条回复
不应该是用彩色打印机吗？要不怎么区分红和黑。
【 在 lance6716 的大作中提到: 】
: 厉害厉害，但是本杠精觉得最恰当的角色是网页前端去处理可视化，cpp安心写算法
如果是python的话，可以使用下面这个方法。
```python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
def treeNodeToString(root):
if not root:
return "[]"
output = ""
queue = [root]
current = 0
while current != len(queue):
node = queue[current]
current = current + 1
if not node:
output += "null, "
continue
output += str(node.val) + ", "
queue.append(node.left)
queue.append(node.right)
return "[" + output[:-2] + "]"
def stringToTreeNode(input):
input = input.strip()
input = input[1:-1]
if not input:
return None
inputValues = [s.strip() for s in input.split(',')]
root = TreeNode(int(inputValues[0]))
nodeQueue = [root]
front = 0
index = 1
while index < len(inputValues):
node = nodeQueue[front]
front = front + 1
item = inputValues[index]
index = index + 1
if item != "null":
leftNumber = int(item)
node.left = TreeNode(leftNumber)
nodeQueue.append(node.left)
if index >= len(inputValues):
break
item = inputValues[index]
index = index + 1
if item != "null":
rightNumber = int(item)
node.right = TreeNode(rightNumber)
nodeQueue.append(node.right)
return root
def prettyPrintTree(node, prefix="", isLeft=True):
if not node:
print("Empty Tree")
return
if node.right:
prettyPrintTree(node.right, prefix + ("│ " if isLeft else " "), False)
print(prefix + ("└── " if isLeft else "┌── ") + str(node.val))
if node.left:
prettyPrintTree(node.left, prefix + (" " if isLeft else "│ "), True)
def main():
import sys
def readlines():
for line in sys.stdin:
yield line.strip('\n')
lines = readlines()
while True:
try:
line = lines.next()
node = stringToTreeNode(line)
prettyPrintTree(node)
except StopIteration:
break
if __name__ == '__main__':
main()
```
运行时需要自己输入测试用例，比如输入[1, 2, 3, 4, 5, null, null, 4, 5, null, 6]
可以得到二叉树：
```
│ ┌── 3
└── 1
│ ┌── 6
│ ┌── 5
└── 2
│ ┌── 5
└── 4
└── 4
```
缺点是这棵树是从左到右的，不是常见的从上到下。
其他各个语言的版本见LeetCode的PlayGround.