数据结构红黑树添加、修改原理分析

源码分析大纲

• 数据结构解析
• 红黑树试下原理刨析

数据结构解析

1.红黑树

红黑树图形

1.1 红黑树概念

红黑树（Red Black Tree） 是一种自平衡二叉查找树，
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。它与AVL树之间的区别:AVL树必须通过多次旋转后达到平衡，而红黑树可以通过旋转或者变色从而保持平衡。

1.2 红黑树的特性

1. 节点为黑色或红色
2. 根节点为黑色
3. 每个叶子节点都是黑色的空节点（NIL） [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
4. 每个红色节点的两个孩子节点都是黑色（保证从每个叶子到根的所有路径上不能有两个连续的红色节点
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（保证了红黑树从根到叶子的最长路径不会超过最短路径的两倍）

红黑树图片
红黑树模拟生成地址

1.3 红黑树保持平衡方式(旋转、变色)

左旋转

左旋图

以1为节点进行左旋，1往下3节点往上走，3节点的左节点变成1，3的原来左节点挂到1的右节点上，形成左旋。

右旋

右旋图

以3节点为中心进行右旋，3节点往下走，1节点提上，1节点的右节点变为3节点，1节点的原先右节点挂到3节点的右节点上，旋转完毕。

变色
安装红黑树五条规定进行操作。

1.4 红黑树的插入(当前节点默认为红色)

• 1. 当前节点的插入点为根节点的时候，对插入节点进行变色处理。

     
     根节点

• 2.当前节点插入点为黑色的情况直接插入。

  
  image.png

• 3.当前节点的插入点为红色，并且它的兄弟节点也为红色的时候，插入点，和兄弟节点变为黑色，插入点的父节点变为红色，再以插入点的父节点作为当前节点，进行下一轮的判断。(I为当前节点，P为插入点，PP为父节点，S为叔叔节点)

  
  叔红情况判断

• 4. 当前节点的插入点为红色，并且他的兄弟节点为黑色或者不存在，把插入点变黑色，插入点的父节点变为红色，如果当前点在插入的左子树，以插入点的父节点为中心，进行右旋转，如果当前点在插入点的右子树，以插入点的父节点为中心，进行左旋转。进而平衡。

     
     叔为黑或者为空情况
     叔为黑或者为空情况

1.5红黑树删除问题分析。

• 1.如果删除的的为根节点。

  
  删除根节点

• 2.如果删除节点为红节点，并且只有左节点，或者只有右节点，使用左节点，或者右节点代替当前删除节点。并且把左节点或者右节点变为黑色。直接删除节点。

  
  有一个子类

• 3.如果删除节点为黑色，并且只有左节点，或者只有右节点，直接使用下面的节点代替删除点，不用进行变色操作。

  
  image.png

• 4. 删除节点，既有左子树，又有右子树的情况，直接获取它的后继节点代替当前节点，变为删除后继节点方法。后继节点只有两种情况，没有节点，或者为只有右节点。

     
     删除节点两点情况

• 4.1 当只有右节点的时候规则转换为2和3的规则。

• 4.2 当没有节点的时候，如果节点为红色，直接进行删除。

  
  没有节点的情况

• 4.3 当没有左节点且没有右节点的情况，并且颜色为黑色，如果他的兄弟节点为黑色。

• 4.3.1 如果兄弟节点没有左子树，并且没有右子树，把兄弟节点变为红色，如果父节点为红色，把父亲节点变为黑色，循环平衡结束， 如果父亲节点为黑色，删除当前子树节点后，当前节点会少一个黑节点，再以当前父类节点作为当前节点进行下一次循环判断，直到平衡(注意:通过画图的，下一次循环不会再进入4.3.1而会进入4.3.2或者为root节点。从而实现平衡)(treemap删除循环逻辑)**
  

  第一种情况
  第二种循环的情况

• 4.3.1 如果兄弟节点为黑色，有右子树，把右子树设置为黑色，兄弟节点的颜色与父节点交换，把父节点设置为黑色，以兄弟节点进行左旋，这样，左边节点比右边节点多出一个黑节点，删除多余的那个节点，保持了红黑树平衡
  

  兄弟节点有值情况展示
  兄弟节点有值情况展示

• 4.3.2 **如果兄弟节点为红色，把兄弟节点变为黑色，父节点变为红色，以兄弟节点进行左旋，得到4.3.1的情况，以4.3.1的情况继续进行操作。

  
  兄弟节点为红色情况