最近一直在复习面试的内容，会不断的记录相关自己看过或者写过的内容，这也是自己的收获或经历，以后查询也比较方便。

红黑树的性质不说了，直接贴代码上传。

/*
?* rbtree.h
?* 1. 每个节点是红色或者黑色
?* 2. 根节点是黑色
?* 3. 每个叶子节点是黑色（该叶子节点就空的节点）
?* 4. 如果一个节点是红色，则它的两个子节点是黑色的
?* 5.对每个节点，从该节点道其他所有后代的叶子节点的简单路径上，均包含相同数目的黑色节点
?*
?*/

#ifndef SRC_RBTREE_H_
#define SRC_RBTREE_H_
#include
#include

using namespace std;
enum colors{ RED,BLACK};
typedef int color_type;
?namespace red_black_tree{
? ? struct rb_tree_base{
? ? ? ? struct rb_tree_base * parent;
? ? ? ? struct rb_tree_base * left;
? ? ? ? struct rb_tree_base * right;
? ? ? ? color_type color;
? ? };

? ? template
? ? struct rb_tree_node:public rb_tree_base{
? ? ? ? T data;
? ? ? ? typedef rb_tree_node* link_type;
? ? };
? template
? ? class rb_tree{
? ? public:
? ? ? typedef rb_tree_base* rb_ptr;
? ? ? typedef typename rb_tree_node::link_type link_type;
? ? ? typedef rb_tree_node? tree_node;
? ? private:
? ? ? rb_ptr head;
? ? private:
? ? ? ? bool _right_rotate(rb_ptr root);
? ? ? ? bool _left_rotate(rb_ptr root);
? ? ? ? rb_ptr _get_node(const Value& e) const;
? ? ? ? bool _insert_fix_up(rb_ptr current_ptr);

? ? ? ? bool _erase_fix_up(rb_ptr current_ptr,rb_ptr parent_ptr);

? ? ? ? void _preOrder(rb_ptr root) const;

? ? ? ? rb_ptr _successor(rb_ptr current_ptr) const;
? ? public:
? ? ? ? rb_tree();
? ? ? ? ~rb_tree();
? ? ? ? bool insert(const Value &e);
? ? ? ? bool empty() const;
? ? ? ? bool erase(const Value &e);
? ? ? ? rb_ptr find(const Value &e);
? ? ? ? void levelOrder() const;
? ? ? ? void preOrder() const;
? ? };
? template
? ? rb_tree::rb_tree() {
? ? ? ? head = new? tree_node();
? ? ? ? head->left=head;
? ? ? ? head->right=head;
? ? ? ? head->parent=head;

? ? ? ? head->color=BLACK;
? ? }

? ? template
? ? rb_tree::~rb_tree() {
? ? }

? template
? ? bool rb_tree::insert(const Value& e) {
? ? ? ? rb_ptr insert_ptr =_get_node(e);
? ? ? ? if(head->parent ==head){
? ? ? ? ? ? head->parent=insert_ptr;
? ? ? ? ? ? insert_ptr->parent=head;
? ? ? ? ? ? insert_ptr->color=BLACK;
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? rb_ptr root_ptr=head->parent;
? ? ? ? rb_ptr root_remember=nullptr;
? ? ? ? while(root_ptr){
? ? ? ? ? ? root_remember=root_ptr;
? ? ? ? ? ? if(link_type(insert_ptr)->data<=link_type(root_ptr)->data)
? ? ? ? ? ? ? ? root_ptr=root_ptr->left;
? ? ? ? ? ? else
? ? ? ? ? ? ? ? root_ptr=root_ptr->right;
? ? ? ? }
? ? ? ? insert_ptr->parent=root_remember;
? ? ? ? if(link_type(insert_ptr)->data <= link_type(root_remember)->data )
? ? ? ? ? ? root_remember->left=insert_ptr;
? ? ? ? else if(link_type(insert_ptr)->data >link_type( root_remember)->data)
? ? ? ? ? ? root_remember->right=insert_ptr;
? ? ? ? bool ret =_insert_fix_up(insert_ptr);
? ? ? ? return ret;
? ? }
? ? template
? ? bool rb_tree::empty() const {

? ? ? ? return head->parent==head;
? ? }

? ? template
? ? bool rb_tree::erase(const Value& e) {

? ? ? ? rb_ptr erase_ptr = find(e);

? ? ? ? if(!erase_ptr)

? ? ? ? ? ? return false;

? ? ? ? int erase_color =erase_ptr->color;

? ? ? ? rb_ptr fix_up_ptr=nullptr;

? ? ? ? rb_ptr fix_up_parent_ptr=nullptr;

? ? ? ? if(erase_ptr){

? ? ? ? ? ? if(!erase_ptr->left&&!erase_ptr->right){//叶子节点

? ? ? ? ? ? ? ? if(erase_ptr==erase_ptr->parent->left){

? ? ? ? ? ? ? ? ? ? erase_ptr->parent->left=nullptr;

? ? ? ? ? ? ? ? ? ? fix_up_parent_ptr= erase_ptr->parent;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if(erase_ptr==erase_ptr->parent->right){

? ? ? ? ? ? ? ? ? ? erase_ptr->parent->right=nullptr;

? ? ? ? ? ? ? ? ? ? fix_up_parent_ptr= erase_ptr->parent;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if(erase_ptr==head->parent){

? ? ? ? ? ? ? ? ? ? head->parent=head;

? ? ? ? ? ? ? ? ? ? fix_up_parent_ptr=head;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? erase_color =erase_ptr->color;

? ? ? ? ? ? ? ? delete erase_ptr;

? ? ? ? ? ? }else if(erase_ptr->right){