红黑树的基本性质
（1）红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉搜索树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 结点是红色或黑色。
性质2. 根结点是黑色。
性质3. 所有叶子都是黑色。（叶子是NIL结点）
性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
性质4导致路径上不能有两个连续的红色结点确保了这个结果。最短的可能路径都是黑色结点，最长的可能路径有交替的红色和黑色结点。因为根据性质5所有最长的路径都有相同数目的黑色结点，这就表明了没有路径能多于任何其他路径的两倍长。
因为红黑树是一种特化二叉查找树，所以红黑树上的只读操作与普通二叉查找树相同。
结点设置和初始化：
typedef enum {RED = 0,BLACK = 1}ColorType;
typedef int KeyType;typedef struct rb_node
{rb_node* leftchild;rb_node* parent;rb_node* rightchild;ColorType color;KeyType key;
}rbnode;
typedef struct
{struct rb_node *root;struct rb_node* Nil;//哨兵结点int cursize;
}RBTree;
rb_node* Buynode(rb_node* parg, ColorType carg)
{rb_node* s = (rb_node*)calloc(1,sizeof(rb_node));if (s == nullptr)exit(1);s->color = carg;s->parent = parg;return s;
}
void Freenode(rb_node* p)
{free(p);
}
void InitRBTree(RBTree* ptree)
{assert(ptree != nullptr);ptree->Nil = Buynode(nullptr, BLACK);ptree->root = ptree->Nil;ptree->cursize = 0;
}插入
插入过程首先是根据一般二叉查找树的插入步骤， 把新结点 插入到 某个叶结点的位置上，然后将 新节点着为红色。 为了保证红黑树的性质能继续保持，再对有关结点重点着色并旋转，其插入算法如下：
1 按二叉查找树的插入步骤将结点新节点插入到 树tree中；
2 如果前面没有节点，则置为根节点（结束）；
3 找到插入的位置，判断是双亲结点的左孩子还是右孩子；
4 从插入节点开始回溯，调整红黑树的结构使其满足上述五个性质；
bool Insert(rb_node*& tree, KeyType kx)
{assert(tree!= nullptr);rb_node* pa = nullptr;rb_node* p = tree;while (p != nullptr && p->key != kx)//找到插入位置{pa = p;p = kx < p->key ? p->leftchild : p->rightchild;}if (p != nullptr && p->key == kx) return false;p = Buynode();//购买节点p->key = kx;p->parent = pa;if (kx < pa->key)//判断是左右那个孩子{pa->leftchild = p;}else{pa->rightchild = p;}PassRBTree(tree, p);return true;
}
void PassRBTree(rb_node*& tree, rb_node* p)//左旋右旋函数与AVL树相同
{rb_node* _X = nullptr;for (; p != tree && p->parent->color == RED;){if (p->parent->parent->rightchild == p->parent) // ringht{_X = p->parent->parent->leftchild;if (_X->color == RED){_X->color = BLACK;p->parent->color = BLACK;p->parent->parent->color = RED;p = p->parent->parent;}else{if (p->parent->leftchild == p){p = p->parent;RotateRight(tree, p);}p->parent->color = BLACK;p->parent->parent->color = RED;RotateLeft(tree, p->parent->parent);}}else{_X = p->parent->parent->rightchild;if (_X->color == RED){_X->color = BLACK;p->parent->color = BLACK;p->parent->parent->color = RED;p = p->parent->parent;}else{if (p->parent->rightchild == p){p = p->parent;RotateLeft(tree, p);}p->parent->color = BLACK;p->parent->parent->color = RED;RotateRight(tree, p->parent->parent);}}}tree->color = BLACK;
}
