红黑树算法( 二 ) _红黑树算法

2、c节点变为a节点的右孩子
3、a节点原来的右孩子变为c节点的左孩子
4、a节点原来的左孩子不变
5、c节点原来的右孩子节点不变

右旋转代码实现如下：
/** * 右旋转 * * @param c 操作节点 */private void rightRotate(Node c) {//1、将c节点的左孩子节点a替换到c节点位置的父节点下Node a = c.left;a.parent = c.parent;if (c.parent == this.nil) {this.rootNode = a;} else if (c.parent.left == c) {c.parent.left = a;} else {c.parent.right = a;}//2、c节点变为a节点的右孩子a.right = c;c.parent = a;//3、a节点原来的右孩子变为c节点的左孩子c.left = a.right;if (a.right != this.nil) {a.right.parent = c;}}实际上，这种调整是严格按照二叉搜索树定义来的，这里并不打算花时间详细去证明这种调整是如何总是能够保证满足红黑树二叉搜索树性质的，有兴趣读者可以自己去研究或参考网上资料进行深入学习。但是不管研究深度如何，最后的做法都是把调整的规律记下来。
最后有几个疑问，就是在什么情况下应该进行左旋转、在什么情况下又应该进行右旋转呢？还有变色又是怎么回事？带着这些问题我们继续往下看。

红黑树-插入（insert）

插入实际上就是构建红黑树性质的二叉搜索树，每次插入一个节点时，既要遵循二叉搜索树的定义又要保证不破坏红黑树的性质，可想而知，插入的逻辑会比较复杂。还是那个习惯，我们只关心操作规律规则，暂且不要纠结如何证明，因为证明的过程太复杂，很多程序员包括一般算法类工程师也未必能够用数学公式完全证明出来，大部分都是记住定义，就是学数学一样，把公式记下来。

我们先思考假设插入一个节点newNode,大概步骤有哪些？一般来说有以下步骤：

1、首先要根据二叉搜索树定义将newNode节点插入到正确位置，例如插入值为4的新节点图解如下（虽然下图颜色是满足红黑树定义的，但先不要关心颜色，因为现在还不到检查调整红黑树定义的步骤）：

文章插图

文章插图

二叉搜索树性质插入代码如下：

/** * 根据二叉搜索树定义插入新节点 * * @param newNode 新节点 */@SuppressWarnings("unchecked")private void twoForkSearchTreeInsert(Node newNode) {Node insertParent = this.nil;Node currentParent = this.rootNode;//只要不是为null的叶子节点，就一直查找下去while (currentParent != this.nil) {//当前父节点作为本次插入节点的父节点insertParent = currentParent;//newNode.eleVal <= currentParent.eleVal//左孩子作为父节点继续判断if (newNode.eleVal.compareTo(currentParent.eleVal) <= 0) {currentParent = currentParent.left;} else {//newNode.eleVal > currentParent.eleVal//右孩子作为父节点继续判断currentParent = currentParent.right;}}newNode.parent = insertParent;//如果父节点为null，本次插入的直接作为最根节点if (insertParent == this.nil) {this.rootNode = newNode;} else if (newNode.eleVal.compareTo(insertParent.eleVal) <= 0) {//左孩子insertParent.left = newNode;} else {//右孩子insertParent.right = newNode;}}

2、为新节点新增颜色（默认为红色），以及设置为null的叶子节点为nil属性，代码如下：

/** * 给新插入节点进行红黑树着为红色 * * @param newNode 新插入节点 */private void setRedBlackTreeProperty(Node newNode) {newNode.left = this.nil;newNode.right = this.nil;newNode.parent = this.nil;//红色newNode.color = RED;}

为什么将新插入的节点默认着为红色，答案在红黑树第五条定义：
“给定任意节点，从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点”
从这条定义可以看出，如果插入黑色的话，一定是错误的。当然，红色也可能错误，但是红色导致的错误比黑色导致的错误容易处理些，所以选择了红色作为插入的默认颜色。

3、根据二叉搜索树插入后，接下来就需要判断是否满足红黑树性质，如果不满足则需要进行调整。我们知道新插入节点颜色默认着为红色，根据红黑树的定义，下面我们分析哪些定义可能会被破坏：

定义1：每个节点要么是红色要么是黑色（不会被破坏）
定义2：根节点是黑色的（可能会被破坏）
定义3：为null的叶节点是黑色的（不会被破坏）
定义4：如果一个节点是红色的，那么它的两个子节点都是黑色的（可能会被破坏）