红-黑树的特征
它主要有两个特征：.节点都有颜色；.在插入和删除的过程中，要遵循保持这些颜色的不同排列的规则。首先第一个特征很好解决，在节点类中店家一个数据字段，例如boolean型变量，以此来表示节点的颜色信息。第二个特征比较复杂，红-黑树有它的几个规则，如果遵循这些规则，那么树就是平衡的。红-黑树的主要规则如下：
.每个节点不是红色就是黑色的；
.根节点总是黑色的；
3.如果节点是红色的，则它的子节点必须是黑色的（反之不一定）；
4.从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）。
在红-黑树中插入的节点都是红色的，这不是偶然的，因为插入一个红色节点比插入一个黑色节点违背红-黑规则的可能性更小。原因是：插入黑色节点总会改变黑色高度（违背规则4），但是插入红色节点只有一半的机会会违背规则3。另外违背规则3比违背规则4要更容易修正。当插入一个新的节点时，可能会破坏这种平衡性，那么红-黑树是如何修正的呢？
.平衡性的修正红-黑树主要通过三种方式对平衡进行修正，改变节点颜色、左旋和右旋。这看起来有点抽象，我们分别来介绍它们。
.变色改变节点颜色比较容易理解，因为它违背了规则3。假设现在有个节点E，然后插入节点A和节点S，节点A在左子节点，S在右子节点，目前是平衡的。如果此时再插一个节点，那么就出现了不平衡了，因为红色节点的子节点必须为黑色，但是新插的节点是红色的。所以这时候就必须改变节点颜色了。所以我们将根的两个子节点从红色变为黑色（至于为什么都要变，下面插入的时候会详细介绍），将父节点会从黑色变成红色。可以用如下示意图表示一下：
.左旋通常左旋操作用于将一个向右倾斜的红色链接旋转为向左链接。示意图如下：
3.右旋右旋可左旋刚好相反，这里不再赘述，直接看示意图：
这里主要介绍了红-黑树对平衡的三种修正方式，大家有个感性的认识，那么什么时候该修正呢？什么时候该用哪种修正呢？这将是接下来我们要探讨的问题。
3.红-黑树的操作
红-黑树的基本操作是添加、删除和旋转。对红-黑树进行添加或删除后，可能会破坏其平衡性，会用到哪种旋转方式去修正呢？我们首先对红-黑树的节点做一介绍，然后分别对左旋和右旋的具体实现做一分析，最后我们探讨下红-黑树的具体操作。
.红-黑树的节点
红-黑树是对二叉搜索树的改进，所以其节点与二叉搜索树是差不多的，只不过在它基础上增加了一个boolean型变量来表示节点的颜色，具体看RBNodeT类：
.左旋具体实现
上面对左旋的概念已经有了感性的认识了，这里就不再赘述了，我们从下面的代码中结合上面的示意图，探讨一下左旋的具体实现：
[java]viewplaincopy
/*************对红黑树节点x进行左旋操作******************/
/*
*左旋示意图：对节点x进行左旋
*pp
*//
*xy
*/\/\
*lxy-----xry
*/\/\
*lyrylxly
*左旋做了三件事：
*.将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)
*.将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
*3.将y的左子节点设为x，将x的父节点设为y
*/
privatevoidleftRotate(RBNodeTx){
//.将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)
RBNodeTy=x.right;
x.right=y.left;
if(y.left!=null)
y.left.parent=x;
//.将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
y.parent=x.parent;
if(x.parent==null){
this.root=y;//如果x的父节点为空，则将y设为父节点
}else{
if(x==x.parent.left)//如果x是左子节点
x.parent.left=y;//则也将y设为左子节点
else
x.parent.right=y;//否则将y设为右子节点
}
//3.将y的左子节点设为x，将x的父节点设为y
y.left=x;
x.parent=y;
}
3.右旋具体实现
上面对右旋的概念已经有了感性的认识了，这里也不再赘述了，我们从下面的代码中结合上面的示意图，探讨一下右旋的具体实现：
[java]viewplaincopy
/*************对红黑树节点y进行右旋操作******************/
/*
*左旋示意图：对节点y进行右旋
*pp
*//
*yx
*/\/\
*xry-----lxy
*/\/\
*lxrxrxry
*右旋做了三件事：
*.将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)
*.将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右)
*3.将x的右子节点设为y，将y的父节点设为x
*/
privatevoidrightRotate(RBNodeTy){
//.将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时)
RBNodeTx=y.left;
y.left=x.right;
if(x.right!=null)
x.right.parent=y;
//.将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
x.parent=y.parent;
if(y.parent==null){
this.root=x;//如果x的父节点为空，则将y设为父节点
}else{
if(y==y.parent.right)//如果x是左子节点
y.parent.right=x;//则也将y设为左子节点
else
y.parent.left=x;//否则将y设为右子节点
}
//3.将y的左子节点设为x，将x的父节点设为y
x.right=y;
y.parent=x;
}
4.插入操作
分析完了红-黑树中主要的旋转操作，接下来我们开始分析常见的插入、删除等操作了。这里先分析插入操作。由于红-黑树是二叉搜索树的改进，所以插入操作的前半工作时相同的，即先找到待插入的位置，再将节点插入，先来看看插入的前半段代码：
[java]viewplaincopy
/***********************向红黑树中插入节点**********************/
publicvoidinsert(Tkey){
RBNodeTnode=newRBNodeT(key,RED,null,null,null);
if(node!=null)
insert(node);
}
//将节点插入到红黑树中，这个过程与二叉搜索树是一样的
privatevoidinsert(RBNodeTnode){
RBNodeTcurrent=null;//表示最后node的父节点
RBNodeTx=this.root;//用来向下搜索用的
//.找到插入的位置
while(x!=null){
current=x;
intcmp=node.key.北京白癜风治疗最好的医院在哪白癜风可以治愈