红黑树算法 _红黑树算法

红黑树是二叉搜索树的增强版，我们知道优化二叉搜索树的核心是优化二叉搜索树的高度，也就是使树尽可能地平衡，红黑树就是解决这个问题的，它能够尽可能地平衡二叉搜索树的高度，保证动态集合操作在最差的情况下时间复杂度保持在O(lgn) 。

红黑树通过在每个节点对象（Node）上增加颜色属性（color）来保证从根到叶子的从A到B节点任意两条路径差距不超过2倍，因而是近似于平衡的。

注意：红黑树只是平衡二叉搜索树的其中一种，平衡二叉树还有其它算法。

关于二叉搜索树可以阅读笔者前面写的二叉搜索树文章，这里只给出二叉搜索树的定义，其它不再过多详细讲解，二叉搜索树是指具有下面定义的二叉树：

1、任何父节点的值均大于等于（>=）左孩子节点值以及左孩子下的所有孩子节点值
2、任何父节点的值均小于（<）右孩子节点值以及右孩子下的所有孩子节点值
3、树最根节点是唯一父节点值为null的节点

定义红黑树是一颗二叉搜索树，所以除了要满足二叉搜索树的定义外，红黑树还要满足下面的定义（背下来）：

1、每个节点要么是红色要么是黑色

文章插图

2、根节点是黑色的

文章插图

3、为null的叶节点是黑色的（代码实现上可以用一个全局对象代表所有为null的节点）

文章插图

4、如果一个节点是红色的，那么它的两个子节点都是黑色的

文章插图

5、给定任意节点，从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点

红黑树-左、右旋转（left/right-rotate）

我们知道，当对二叉搜索树进行插入、删除操作时会改变树结构，改变后的树结构可能会破坏红黑树的性质（前面列出的定义），为了保证每次改变结构后性质不被破坏，每次修改后需要调整，调整方式有两种，分别是变色和旋转，其中旋转又包含左旋转和右旋转。
注意，只有旋转才会改变（逐渐平衡）树的高度，变色是不会改变树高度的。
下面图解左右旋转分别是怎么调整节点位置的（学习旋转时我们先不要关注它们的颜色，只关注旋转怎么调整相关节点的位置）。

文章插图

我们通过上图可以很直观发现，B树左旋转后得到A树，A树可以通过B树右旋转还原回来，它们是对称的。下面是对左右旋转规律的总结：

B树a节点左旋转后得到A树位置调整如下：

1、将a节点的右孩子节点c替换到a节点位置的父节点下
2、a节点变为c节点的左孩子
3、c节点原来的左孩子变为a节点的右孩子
4、a节点原来的左孩子不变
5、c节点原来的右孩子节点不变

左旋转代码实现如下：

/** * 为null的节点统一对象 */private Node nil;/** * 根节点 */private Node rootNode;private static final int RED = 1;private static final int BLACK = 2;public RedBlackTree() {this.nil = new Node();this.nil.color = BLACK;this.rootNode = this.nil;}/** * 节点对象 */private class Node {private Node left;private T eleVal;private Node right;private Node parent;/*** 颜色RED：红色 BLACK：黑色*/private int color;private Node(T eleVal) {this.eleVal = eleVal;}private Node() {this.color = RED;this.left = null;this.right = null;this.parent = null;}@Overridepublic String toString() {return "Node{" +"eleVal=" + eleVal +", color=" + color +'}';}}/** * 左旋转 * * @param a 操作节点 */private void leftRotate(Node a) {Node c = a.right;//1、将a节点的右孩子节点c替换到a节点位置的父节点下c.parent = a.parent;if (a.parent == this.nil) {this.rootNode = c;} else if (a == a.parent.left) {a.parent.left = c;} else {a.parent.right = c;}//2、a节点变为c节点的左孩子c.left = a;a.parent = c;//3、c节点原来的左孩子变为a节点的右孩子a.right = c.left;if (c.left != this.nil) {c.left.parent = a;}}

A树c节点右旋转后得到B树位置调整如下：

1、将c节点的左孩子节点a替换到c节点位置的父节点下