网站音乐播放器代码免费b站推广

红黑树原理详解与手写红黑树

红黑树的性质：

红黑树的性质	红黑树示例图
性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色节点的两个子节点一定都是黑色。不能有两个红色节点相连。
性质5：任意一节点到每个叶子节点的路径都包含数量相同的黑结点。俗称：黑高！
从性质5又可以推出：性质5.1：如果一个节点存在黑子节点，那么该结点肯定有两个子节点

红黑树并不是一个完美平衡二叉查找树，从图上可以看到，根结点P的左子树显然比右子树高，

但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。

所以我们叫红黑树这种平衡为黑色完美平衡。

红黑树的性质讲完了，只要这棵树满足以上性质，这棵树就是趋近与平衡状态的，

前面讲到红黑树能自平衡，它靠的是三种操作：左旋、右旋和变色。

1.变色结点的颜色由红变黑或由黑变红。

2.左旋以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

3.右旋以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变

左旋图示

​

右旋图示

​

红黑树查找：

​

红黑树插入：

插入操作包括两部分工作：

1.查找插入的位置

2.插入后自平衡

注意：插入节点，必须为红色，理由很简单，红色在父节点（如果存在）为黑色节点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。

但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。

在开始每个情景的讲解前，我们还是先来约定下:

​

红黑树插入节点情景分析

情景1：红黑树为空树

最简单的一种情景，直接把插入结点作为根结点就行

注意：根据红黑树性质2：根节点是黑色。还需要把插入结点设为黑色。

情景2：插入结点的Key已存在

处理：更新当前节点的值，为插入节点的值

​

情景3：插入结点的父结点为黑结点

由于插入的结点是红色的，当插入结点的黑色时，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。

​

情景4：插入节点的父节点为红色

再次回想下红黑树的性质2：根结点是黑色。如果插入节点的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。

这一点很关键，因为后续的旋转操作肯定需要祖父结点的参与。

​

插入情景4.1：叔叔结点存在并且为红结点

依据红黑树性质4可知，红色节点不能相连 ==> 祖父结点肯定为黑结点；

因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红

处理：

1.将P和U节点改为黑色

2.将PP改为红色

3.将PP设置为当前节点，进行后续处理

​

可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；

但如果PP的父结点是红色，则违反红黑树性质了。所以需要将PP设置为当前节点，继续做插入操作自平衡处理，直到平衡为止。

插入情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点

注意：单纯从插入前来看，叔叔节点非红即空（NIL节点），否则的话破坏了红黑树性质5，此路径会比其它路径多一个黑色节点。

​

插入情景4.2.1：新插入节点，为其父节点的左子节点（LL红色情况）

​

处理：

1.变颜色：将P设置为黑色，将PP设置为红色

2.对PP节点进行右旋

​

插入情景4.2.2：新插入节点，为其父节点的右子节点（LR红色情况）

​

处理：

1.对P进行左旋

2.将P设置为当前节点，得到LL红色情况

3.按照LL红色情况处理（1.变颜色 2.右旋PP）

​

**插入情景4.3：**叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点

该情景对应情景4.2，只是方向反转，直接看图。

​

插入情景4.3.1：新插入节点，为其父节点的右子节点（RR红色情况）

​

处理：

1.变颜色：将P设置为黑色，将PP设置为红色

2.对PP节点进行左旋

​

插入情景4.3.2：新插入节点，为其父节点的左子节点（RL红色情况）

​

处理：

1.对P进行右旋

2.将P设置为当前节点，得到RR红色情况

3.按照RR红色情况处理（1.变颜色 2.左旋PP）

​

红黑树代码详解

package com.study.struct;/*** ClassName: TreeOperation* Description:** @author 周哥哥* @since 1.0.0*/
public class TreeOperation {/*树的结构示例：1/   \2       3/ \     / \4   5   6   7*/// 用于获得树的层数public static int getTreeDepth(RBTree.RBNode root) {return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));}private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {// 保证输入的树不为空if (currNode == null) return;// 先将当前节点保存到二维数组中res[rowIndex][columnIndex] = String.valueOf(currNode.getKey() /*+ "-" + (currNode.isColor() ? "R" : "B") + ""*/);// 计算当前位于树的第几层int currLevel = ((rowIndex + 1) / 2);// 若到了最后一层，则返回if (currLevel == treeDepth) return;// 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）int gap = treeDepth - currLevel - 1;// 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值if (currNode.getLeft() != null) {res[rowIndex + 1][columnIndex - gap] = "/";writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);}// 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值if (currNode.getRight() != null) {res[rowIndex + 1][columnIndex + gap] = "\\";writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);}}public static void show(RBTree.RBNode root) {if (root == null) System.out.println("EMPTY!");// 得到树的深度int treeDepth = getTreeDepth(root);// 最后一行的宽度为2的（n - 1）次方乘3，再加1// 作为整个二维数组的宽度int arrayHeight = treeDepth * 2 - 1;int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;// 用一个字符串数组来存储每个位置应显示的元素String[][] res = new String[arrayHeight][arrayWidth];// 对数组进行初始化，默认为一个空格for (int i = 0; i < arrayHeight; i ++) {for (int j = 0; j < arrayWidth; j ++) {res[i][j] = " ";}}// 从根节点开始，递归处理整个树// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');writeArray(root, 0, arrayWidth/ 2, res, treeDepth);// 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可for (String[] line: res) {StringBuilder sb = new StringBuilder();for (int i = 0; i < line.length; i ++) {sb.append(line[i]);if (line[i].length() > 1 && i <= line.length - 1) {i += line[i].length() > 4 ? 2: line[i].length() - 1;}}System.out.println(sb.toString());}}
}package com.study.struct;/*** ClassName: RBTree* Description:** ①创建RBTree，定义颜色* ②创建RBNode* ③辅助方法定义：parentOf(node)，isRed(node)，setRed(node)，setBlack(node)，inOrderPrint(RBNode tree)* ④左旋方法定义：leftRotate(node)* ⑤右旋方法定义：rightRotate(node)* ⑥公开插入接口方法定义：insert(K key, V value);* ⑦内部插入接口方法定义：insert(RBNode node);* ⑧修正插入导致红黑树失衡的方法定义：insertFIxUp(RBNode node);* ⑨测试红黑树正确性*** @author 周哥哥* @since 1.0.0*/
public class RBTree <K extends Comparable<K>, V> {//定义颜色常量private static final boolean RED = true;private static final boolean BLACK = false;//红黑树的树根private RBNode root;public RBNode getRoot() {return root;}/*** 公开的插入接口* @param key 键* @param value 值*/public void insert(K key, V value) {RBNode node = new RBNode();node.setKey(key);node.setValue(value);node.setColor(RED);insert(node);}/*** 内部插入接口定义*/private void insert(RBNode node) {//1.找到插入的位置RBNode parent = null;RBNode x = this.root;while(x != null) {parent = x;//a > b 则返回 1，否则返回 -1 ，相等返回0int cmp = node.key.compareTo(parent.key);if(cmp < 0) {x = x.left;} else if(cmp == 0) {parent.setValue(node.value);return;} else {x = x.right;}}node.parent = parent;if(parent != null) {if(node.key.compareTo(parent.key) < 0) {parent.left = node;} else {parent.right = node;}} else {this.root = node;}//插入之后需要进行修复红黑树，让红黑树再次平衡。insertFixUp(node);}/*** 插入后修复红黑树平衡的方法*     |---情景1：红黑树为空树*     |---情景2：插入节点的key已经存在*     |---情景3：插入节点的父节点为黑色**     情景4 需要咱们去处理*     |---情景4：插入节点的父节点为红色*          |---情景4.1：叔叔节点存在，并且为红色（父-叔 双红）*          |---情景4.2：叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树*               |---情景4.2.1：插入节点为其父节点的左子节点（LL情况）*               |---情景4.2.2：插入节点为其父节点的右子节点（LR情况）*          |---情景4.3：叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树*               |---情景4.3.1：插入节点为其父节点的右子节点（RR情况）*               |---情景4.3.2：插入节点为其父节点的左子节点（RL情况）*/private void insertFixUp(RBNode node) {RBNode parent = parentOf(node);RBNode gparent = parentOf(parent);//存在父节点且父节点为红色if(parent != null && isRed(parent)) {//父节点是红色的，那么一定存在爷爷节点//父节点为爷爷节点的左子树if(parent == gparent.left) {RBNode uncle = gparent.right;//4.1：叔叔节点存在，并且为红色（父-叔 双红）//将父和叔染色为黑色，再将爷爷染红，并将爷爷设置为当前节点，进入下一次循环判断if(uncle != null && isRed(uncle)) {setBlack(parent);setBlack(uncle);setRed(gparent);insertFixUp(gparent);return;}//叔叔节点不存在，或者为黑色，父节点为爷爷节点的左子树if(uncle == null || isBlack(uncle)) {//插入节点为其父节点的右子节点（LR情况）=>//左旋（父节点），当前节点设置为父节点，进入下一次循环if(node == parent.right) {leftRotate(parent);insertFixUp(parent);return;}//插入节点为其父节点的左子节点（LL情况）=>//变色（父节点变黑，爷爷节点变红），右旋爷爷节点if(node == parent.left) {setBlack(parent);setRed(gparent);rightRotate(gparent);}}} else {//父节点为爷爷节点的右子树RBNode uncle = gparent.left;//4.1：叔叔节点存在，并且为红色（父-叔 双红）//将父和叔染色为黑色，再将爷爷染红，并将爷爷设置为当前节点，进入下一次循环判断if(uncle != null && isRed(uncle)) {setBlack(parent);setBlack(uncle);setRed(gparent);insertFixUp(gparent);return;}//叔叔节点不存在，或者为黑色，父节点为爷爷节点的右子树if(uncle == null || isBlack(uncle)) {//插入节点为其父节点的左子节点（RL情况）//右旋（父节点）得到RR情况，当前节点设置为父节点，进入下一次循环if(node == parent.left) {rightRotate(parent);insertFixUp(parent);return;}//插入节点为其父节点的右子节点（RR情况）=>//变色（父节点变黑，爷爷节点变红），右旋爷爷节点if(node == parent.right) {setBlack(parent);setRed(gparent);leftRotate(gparent);}}}}setBlack(this.root);}/*** 左旋方法* 左旋示意图：左旋x节点*    p                   p*    |                   |*    x                   y*   / \         ---->   / \*  lx  y               x   ry*     / \             / \*    ly  ry          lx  ly** 左旋做了几件事？* 1.将y的左子节点赋值给x的右边，并且把x设置为y的左子节点的父节点* 2.将x的父节点（非空时）指向y，更新y的父节点为x的父节点* 3.将y的左子节点指向x，更新x的父节点为y*/private void leftRotate(RBNode x) {RBNode y = x.right;//将y的左子节点赋值给x的右边x.right = y.left;//并且把x设置为y的左子节点的父节点if(y.left != null) {y.left.parent = x;}//将x的父节点（非空时）指向yif(x.parent != null) {//如果x是parent左子树，则把y安放到parent的左边if(x.parent.left == x) {x.parent.left = y;} else {//否则把y安放到parent的右边x.parent.right = y;}//更新y的父节点为x的父节点y.parent = x.parent;} else {this.root = y;this.root.parent = null;}y.left = x;x.parent = y;}/*** 右旋方法* 右旋示意图：右旋y节点**    p                       p*    |                       |*    y                       x*   / \          ---->      / \*  x   ry                  lx  y* / \                         / \*lx  ly                      ly  ry** 右旋都做了几件事？* 1.将x的右子节点 赋值 给了 y 的左子节点，并且更新x的右子节点的父节点为 y* 2.将y的父节点（不为空时）指向x，更新x的父节点为y的父节点* 3.将x的右子节点指向y，更新y的父节点为x*/private void rightRotate(RBNode y) {//1.将x的右子节点赋值给y的左子节点，并将y赋值给x右子节点的父节点（x右子节点非空时）RBNode x = y.left;y.left = x.right;if(x.right != null) {x.right.parent = y;}//2.将y的父节点p（非空时）赋值给x的父节点，同时更新p的子节点为x（左或右）x.parent = y.parent;if(y.parent != null) {if(y.parent.left == y) {y.parent.left = x;} else {y.parent.right = x;}} else {this.root = x;this.root.parent = null;}//3.将x的右子节点赋值为y，将y的父节点设置为xx.right = y;y.parent = x;}/*** 获取当前节点的父节点*/private RBNode parentOf(RBNode node) {if(node != null) {return node.parent;}return null;}/*** node节点是否为红色* @return boolean true 表示是红色  false 表示不是红色*/private boolean isRed(RBNode node) {if(node != null) {return node.isColor() == RED;}return false;}/*** 设置节点为红色*/private void setRed(RBNode node) {if(node != null) {node.setColor(RED);}}/*** 设置节点为黑色*/private void setBlack(RBNode node) {if(node != null) {node.setColor(BLACK);}}/*** 中序打印，可以将二叉查找树有顺序的打印出来*/public void inOrderPrint() {if(this.root != null) {inOrderPrint(this.root);}}private void inOrderPrint(RBNode node) {if(node != null) {inOrderPrint(node.left);System.out.println("key -> " + node.key + ", value -> " + node.value);inOrderPrint(node.right);}}/*** node节点是否为黑色* @return boolean true 表示是黑色  false 表示不是黑色*/private boolean isBlack(RBNode node) {if(node != null) {return node.isColor() == BLACK;}return false;}/*** 红黑树Node*/static class RBNode<K extends Comparable<K>, V> {//颜色private boolean color;//左子节点private RBNode left;//右子节点private RBNode right;//父节点private RBNode parent;//keyprivate K key;//valueprivate V value;public RBNode(boolean color, RBNode left, RBNode right, RBNode parent, K key, V value) {this.color = color;this.left = left;this.right = right;this.parent = parent;this.key = key;this.value = value;}public RBNode() {}public boolean isColor() {return color;}public void setColor(boolean color) {this.color = color;}public RBNode getLeft() {return left;}public void setLeft(RBNode left) {this.left = left;}public RBNode getRight() {return right;}public void setRight(RBNode right) {this.right = right;}public RBNode getParent() {return parent;}public void setParent(RBNode parent) {this.parent = parent;}public K getKey() {return key;}public void setKey(K key) {this.key = key;}public V getValue() {return value;}public void setValue(V value) {this.value = value;}}/****************************************************************************** Print Method*****************************************************************************/public void padding ( String ch, int n ) {int i;for ( i = 0; i < n; i++ )System.out.printf(ch);}void print_node (RBNode root, int level ) {if ( root == null ) {padding ( "\t", level );System.out.println( "NIL" );} else {print_node ( root.right, level + 1 );padding ( "\t", level );if(root.color == BLACK) {System.out.printf(root.key + "(" + (root.isColor() ? "红" : "黑") +")" + "\n");} elseSystem.out.printf(root.key  + "(" + (root.isColor() ? "红" : "黑") +")" + "\n");print_node ( root.left, level + 1 );}}void print_tree() {print_node(this.root,0);System.out.printf("-------------------------------------------\n");}
}package com.study.struct;import java.util.Scanner;/*** ClassName: TestRBTree* 测试红黑树*/
public class TestRBTree {public static void main(String[] args) {RBTree<String, Object> rbt = new RBTree();//测试输入：ijkgefhdabcwhile(true) {Scanner sc = new Scanner(System.in);System.out.println("请输入key:");String key = sc.next();rbt.insert(key, null);TreeOperation.show(rbt.getRoot());}}
}