目录

• 1、红黑树的属性
• 2、旋转
• 3、插入
• 4、删除
• 5、所有代码
• 6、演示

1、红黑树的属性 红黑树是一种二分查找树，与普通的二分查找树不同的一点是，红黑树的每个节点都有一个颜色（color）属性。该属性的值要么是红色，要么是黑色。
通过限制从根到叶子的任何简单路径上的节点颜色，红黑树确保没有比任何其他路径长两倍的路径，从而使树近似平衡。
假设红黑树节点的属性有键（key）、颜色（color）、左子节点（left）、右子节点（right），父节点（parent）。
一棵红黑树必须满足下面有下面这些特性（ 红黑树特性 ）：

• 树中的每个节点要么是红色，要么是黑色；
• 根节点是黑色；
• 每个叶子节点（null）是黑色；
• 如果某节点是红色的，它的两个子节点都是黑色；
• 对于每个节点到后面任一叶子节点（null）的所有路径，都有相同数量的黑色节点。

为了在红黑树代码中处理边界条件方便，我们用一个哨兵变量代替null。对于一个红黑树tree，哨兵变量RedBlackTree.NULL（下文代码中）是一个和其它节点有同样属性的节点，它的颜色（color）属性是黑色，其它属性可以任意取值。
我们使用哨兵变量是因为我们可以把一个节点node的子节点null当成一个普通节点。
在这里，我们使用哨兵变量RedBlackTree.NULL代替树中所有的null（所有的叶子节点及根节点的父节点）。
我们把从一个节点n（不包括）到任一叶子节点路径上的黑色节点的个数称为 黑色高度 ，用bh(n)表示。一棵红黑树的黑色高度是其根节点的黑色高度。
关于红黑树的搜索，求最小值，求最大值，求前驱，求后继这些操作的代码与二分查找树的这些操作的代码基本一致。可以在用java实现二分查找树查看。
结合上文给出下面的代码。
用一个枚举类Color表示颜色：

public enum Color {Black("黑色"), Red("红色"); private String color; private Color(String color) {this.color = color; }@Overridepublic String toString() {return color; }}

类Node表示节点：

public class Node {public int key; public Color color; public Node left; public Node right; public Node parent; public Node() {}public Node(Color color) {this.color = color; }public Node(int key) {this.key = key; this.color = Color.Red; }public int height() {return Math.max(left != RedBlackTree.NULL ? left.height() : 0, right != RedBlackTree.NULL ? right.height() : 0) + 1; }public Node minimum() {Node pointer = this; while (pointer.left != RedBlackTree.NULL)pointer = pointer.left; return pointer; }@Overridepublic String toString() {String position = "null"; if (this.parent != RedBlackTree.NULL)position = this.parent.left == this ? "left" : "right"; return "[key: " + key + ", color: " + color + ", parent: " + parent.key + ", position: " + position + "]"; }}

类RedTreeNode表示红黑树：

public class RedBlackTree {// 表示哨兵变量public final static Node NULL = new Node(Color.Black); public Node root; public RedBlackTree() {this.root = NULL; }}

2、旋转 红黑树的插入和删除操作，能改变红黑树的结构，可能会使它不再有前面所说的某些特性性。为了维持这些特性，我们需要改变树中某些节点的颜色和位置。
我们可以通过旋转改变节点的结构。主要有 左旋转 和 右旋转 两种方式。具体如下图所示。
左旋转：把一个节点n的右子节点right变为它的父节点，n变为right的左子节点，所以right不能为null。这时n的右指针空了出来，right的左子树被n挤掉，所以right原来的左子树称为n的右子树。
右旋转：把一个节点n的左子节点left变为它的父节点，n变为left的右子节点，所以left不能为null。这时n的左指针被空了出来，left的右子树被n挤掉，所以left原来的右子树被称为n的左子树。

文章图片

可在RedTreeNode类中，加上如下实现代码：

public void leftRotate(Node node) {Node rightNode = node.right; node.right = rightNode.left; if (rightNode.left != RedBlackTree.NULL)rightNode.left.parent = node; rightNode.parent = node.parent; if (node.parent == RedBlackTree.NULL)this.root = rightNode; else if (node.parent.left == node)node.parent.left = rightNode; elsenode.parent.right = rightNode; rightNode.left = node; node.parent = rightNode; }public void rightRotate(Node node) {Node leftNode = node.left; node.left = leftNode.right; if (leftNode.right != RedBlackTree.NULL)leftNode.right.parent = node; leftNode.parent = node.parent; if (node.parent == RedBlackTree.NULL) {this.root = leftNode; } else if (node.parent.left == node) {node.parent.left = leftNode; } else {node.parent.right = leftNode; }leftNode.right = node; node.parent = leftNode; }

3、插入 红黑树的插入代码与二分查找树的插入代码非常相似。只不过红黑树的插入操作会改变红黑树的结构，使其不在有该有的特性。
在这里，新插入的节点默认是红色。
所以在插入节点之后，要有维护红黑树特性的代码。

public void insert(Node node) {Node parentPointer = RedBlackTree.NULL; Node pointer = this.root; while (this.root != RedBlackTree.NULL) {parentPointer = pointer; pointer = node.key < pointer.key ? pointer.left : pointer.right; }node.parent = parentPointer; if(parentPointer == RedBlackTree.NULL) {this.root = node; }else if(node.key < parentPointer.key) {parentPointer.left = node; }else {parentPointer.right = node; }node.left = RedBlackTree.NULL; node.right = RedBlackTree.NULL; node.color = Color.Red; // 维护红黑树属性的方法this.insertFixUp(node); }

用上述方法插入一个新节点的时候，有两类情况会违反红黑树的特性。

• 当树中没有节点时，此时插入的节点称为根节点，而此节点的颜色为红色。
• 当新插入的节点成为一个红色节点的子节点时，此时存在一个红色结点有红色子节点的情况。

对于第一类情况，可以直接把根结点设置为黑色；而针对第二类情况，需要根据具体条件，做出相应的解决方案。
具体代码如下：

public void insertFixUp(Node node) {// 当node不是根结点，且node的父节点颜色为红色while (node.parent.color == Color.Red) {// 先判断node的父节点是左子节点，还是右子节点，这不同的情况，解决方案也会不同if (node.parent == node.parent.parent.left) {Node uncleNode = node.parent.parent.right; if (uncleNode.color == Color.Red) {// 如果叔叔节点是红色，则父父一定是黑色// 通过把父父节点变成红色，父节点和兄弟节点变成黑色，然后在判断父父节点的颜色是否合适uncleNode.color = Color.Black; node.parent.color = Color.Black; node.parent.parent.color = Color.Red; node = node.parent.parent; } else if (node == node.parent.right) {node = node.parent; this.leftRotate(node); } else {node.parent.color = Color.Black; node.parent.parent.color = Color.Red; this.rightRotate(node.parent.parent); }} else {Node uncleNode = node.parent.parent.left; if (uncleNode.color == Color.Red) {uncleNode.color = Color.Black; node.parent.color = Color.Black; node.parent.parent.color = Color.Red; node = node.parent.parent; } else if (node == node.parent.left) {node = node.parent; this.rightRotate(node); } else {node.parent.color = Color.Black; node.parent.parent.color = Color.Red; this.leftRotate(node.parent.parent); }}}// 如果之前树中没有节点，那么新加入的点就成了新结点，而新插入的结点都是红色的，所以需要修改。this.root.color = Color.Black; }

下面的图分别对应第二类情况中的六种及相应处理结果。
情况1：

文章图片

情况2：

文章图片

情况3：

文章图片

情况4：

文章图片

情况5：

文章图片

情况6：

文章图片


4、删除 红黑树中节点的删除会使一个结点代替另外一个节点。所以先要实现这样的代码：

public void transplant(Node n1, Node n2) {if(n1.parent == RedBlackTree.NULL){this.root = n2; }else if(n1.parent.left == n1) {n1.parent.left = n2; }else {n1.parent.right = n2; }n2.parent = n1.parent; }

红黑树的删除节点代码是基于二分查找树的删除节点代码而写的。
删除结点代码：

public void delete(Node node) {Node pointer1 = node; // 用于记录被删除的颜色，如果是红色，可以不用管，但如果是黑色，可能会破坏红黑树的属性Color pointerOriginColor = pointer1.color; // 用于记录问题的出现点Node pointer2; if (node.left == RedBlackTree.NULL) {pointer2 = node.right; this.transplant(node, node.right); } else if (node.right == RedBlackTree.NULL) {pointer2 = node.left; this.transplant(node, node.left); } else {// 如要删除的字节有两个子节点，则找到其直接后继（右子树最小值），直接后继节点没有非空左子节点。pointer1 = node.right.minimum(); // 记录直接后继的颜色和其右子节点pointerOriginColor = pointer1.color; pointer2 = pointer1.right; // 如果其直接后继是node的右子节点，不用进行处理if (pointer1.parent == node) {pointer2.parent = pointer1; } else {// 否则，先把直接后继从树中提取出来，用来替换nodethis.transplant(pointer1, pointer1.right); pointer1.right = node.right; pointer1.right.parent = pointer1; }// 用node的直接后继替换node，继承node的颜色this.transplant(node, pointer1); pointer1.left = node.left; pointer1.left.parent = pointer1; pointer1.color = node.color; }if (pointerOriginColor == Color.Black) {this.deleteFixUp(pointer2); }}

当被删除节点的颜色是黑色时需要调用方法维护红黑树的特性。
主要有两类情况：

• 当node是红色时，直接变成黑色即可。
• 当node是黑色时，需要调整红黑树结构。，
  

private void deleteFixUp(Node node) {// 如果node不是根节点，且是黑色while (node != this.root && node.color == Color.Black) {// 如果node是其父节点的左子节点if (node == node.parent.left) {// 记录node的兄弟节点Node pointer1 = node.parent.right; // 如果他兄弟节点是红色if (pointer1.color == Color.Red) {pointer1.color = Color.Black; node.parent.color = Color.Red; leftRotate(node.parent); pointer1 = node.parent.right; }if (pointer1.left.color == Color.Black && pointer1.right.color == Color.Black) {pointer1.color = Color.Red; node = node.parent; } else if (pointer1.right.color == Color.Black) {pointer1.left.color = Color.Black; pointer1.color = Color.Red; rightRotate(pointer1); pointer1 = node.parent.right; } else {pointer1.color = node.parent.color; node.parent.color = Color.Black; pointer1.right.color = Color.Black; leftRotate(node.parent); node = this.root; }} else {// 记录node的兄弟节点Node pointer1 = node.parent.left; // 如果他兄弟节点是红色if (pointer1.color == Color.Red) {pointer1.color = Color.Black; node.parent.color = Color.Red; rightRotate(node.parent); pointer1 = node.parent.left; }if (pointer1.right.color == Color.Black && pointer1.left.color == Color.Black) {pointer1.color = Color.Red; node = node.parent; } else if (pointer1.left.color == Color.Black) {pointer1.right.color = Color.Black; pointer1.color = Color.Red; leftRotate(pointer1); pointer1 = node.parent.left; } else {pointer1.color = node.parent.color; node.parent.color = Color.Black; pointer1.left.color = Color.Black; rightRotate(node.parent); node = this.root; }}}node.color = Color.Black; }

对第二类情况，有下面8种：
情况1：

文章图片

情况2：

文章图片

情况3：

文章图片

情况4：

文章图片

情况5：

文章图片

情况6：

文章图片

情况7：

文章图片

情况8：

文章图片


5、所有代码

public enum Color {Black("黑色"), Red("红色"); private String color; private Color(String color) {this.color = color; }@Overridepublic String toString() {return color; }}public class Node {public int key; public Color color; public Node left; public Node right; public Node parent; public Node() {}public Node(Color color) {this.color = color; }public Node(int key) {this.key = key; this.color = Color.Red; }/*** 求在树中节点的高度* * @return*/public int height() {return Math.max(left != RedBlackTree.NULL ? left.height() : 0, right != RedBlackTree.NULL ? right.height() : 0) + 1; }/*** 在以该节点为根节点的树中，求最小节点* * @return*/public Node minimum() {Node pointer = this; while (pointer.left != RedBlackTree.NULL)pointer = pointer.left; return pointer; }@Overridepublic String toString() {String position = "null"; if (this.parent != RedBlackTree.NULL)position = this.parent.left == this ? "left" : "right"; return "[key: " + key + ", color: " + color + ", parent: " + parent.key + ", position: " + position + "]"; }}import java.util.LinkedList; import java.util.Queue; public class RedBlackTree {public final static Node NULL = new Node(Color.Black); public Node root; public RedBlackTree() {this.root = NULL; }/*** 左旋转* * @param node*/public void leftRotate(Node node) {Node rightNode = node.right; node.right = rightNode.left; if (rightNode.left != RedBlackTree.NULL)rightNode.left.parent = node; rightNode.parent = node.parent; if (node.parent == RedBlackTree.NULL)this.root = rightNode; else if (node.parent.left == node)node.parent.left = rightNode; elsenode.parent.right = rightNode; rightNode.left = node; node.parent = rightNode; }/*** 右旋转* * @param node*/public void rightRotate(Node node) {Node leftNode = node.left; node.left = leftNode.right; if (leftNode.right != RedBlackTree.NULL)leftNode.right.parent = node; leftNode.parent = node.parent; if (node.parent == RedBlackTree.NULL) {this.root = leftNode; } else if (node.parent.left == node) {node.parent.left = leftNode; } else {node.parent.right = leftNode; }leftNode.right = node; node.parent = leftNode; }public void insert(Node node) {Node parentPointer = RedBlackTree.NULL; Node pointer = this.root; while (pointer != RedBlackTree.NULL) {parentPointer = pointer; pointer = node.key < pointer.key ? pointer.left : pointer.right; }node.parent = parentPointer; if (parentPointer == RedBlackTree.NULL) {this.root = node; } else if (node.key < parentPointer.key) {parentPointer.left = node; } else {parentPointer.right = node; }node.left = RedBlackTree.NULL; node.right = RedBlackTree.NULL; node.color = Color.Red; this.insertFixUp(node); }private void insertFixUp(Node node) {// 当node不是根结点，且node的父节点颜色为红色while (node.parent.color == Color.Red) {// 先判断node的父节点是左子节点，还是右子节点，这不同的情况，解决方案也会不同if (node.parent == node.parent.parent.left) {Node uncleNode = node.parent.parent.right; if (uncleNode.color == Color.Red) { // 如果叔叔节点是红色，则父父一定是黑色// 通过把父父节点变成红色，父节点和兄弟节点变成黑色，然后在判断父父节点的颜色是否合适uncleNode.color = Color.Black; node.parent.color = Color.Black; node.parent.parent.color = Color.Red; node = node.parent.parent; } else if (node == node.parent.right) { // node是其父节点的右子节点，且叔叔节点是黑色// 对node的父节点进行左旋转node = node.parent; this.leftRotate(node); } else { // node如果叔叔节点是黑色，node是其父节点的左子节点，父父节点是黑色// 把父节点变成黑色，父父节点变成红色，对父父节点进行右旋转node.parent.color = Color.Black; node.parent.parent.color = Color.Red; this.rightRotate(node.parent.parent); }} else {Node uncleNode = node.parent.parent.left; if (uncleNode.color == Color.Red) {uncleNode.color = Color.Black; node.parent.color = Color.Black; node.parent.parent.color = Color.Red; node = node.parent.parent; } else if (node == node.parent.left) {node = node.parent; this.rightRotate(node); } else {node.parent.color = Color.Black; node.parent.parent.color = Color.Red; this.leftRotate(node.parent.parent); }}}// 如果之前树中没有节点，那么新加入的点就成了新结点，而新插入的结点都是红色的，所以需要修改。this.root.color = Color.Black; }/*** n2替代n1* * @param n1* @param n2*/private void transplant(Node n1, Node n2) {if (n1.parent == RedBlackTree.NULL) { // 如果n1是根节点this.root = n2; } else if (n1.parent.left == n1) { // 如果n1是其父节点的左子节点n1.parent.left = n2; } else { // 如果n1是其父节点的右子节点n1.parent.right = n2; }n2.parent = n1.parent; }/*** 删除节点node* * @param node*/public void delete(Node node) {Node pointer1 = node; // 用于记录被删除的颜色，如果是红色，可以不用管，但如果是黑色，可能会破坏红黑树的属性Color pointerOriginColor = pointer1.color; // 用于记录问题的出现点Node pointer2; if (node.left == RedBlackTree.NULL) {pointer2 = node.right; this.transplant(node, node.right); } else if (node.right == RedBlackTree.NULL) {pointer2 = node.left; this.transplant(node, node.left); } else {// 如要删除的字节有两个子节点，则找到其直接后继（右子树最小值），直接后继节点没有非空左子节点。pointer1 = node.right.minimum(); // 记录直接后继的颜色和其右子节点pointerOriginColor = pointer1.color; pointer2 = pointer1.right; // 如果其直接后继是node的右子节点，不用进行处理if (pointer1.parent == node) {pointer2.parent = pointer1; } else {// 否则，先把直接后继从树中提取出来，用来替换nodethis.transplant(pointer1, pointer1.right); pointer1.right = node.right; pointer1.right.parent = pointer1; }// 用node的直接后继替换node，继承node的颜色this.transplant(node, pointer1); pointer1.left = node.left; pointer1.left.parent = pointer1; pointer1.color = node.color; }if (pointerOriginColor == Color.Black) {this.deleteFixUp(pointer2); }}/*** The procedure RB-DELETE-FIXUP restores properties 1, 2, and 4* * @param node*/private void deleteFixUp(Node node) {// 如果node不是根节点，且是黑色while (node != this.root && node.color == Color.Black) {// 如果node是其父节点的左子节点if (node == node.parent.left) {// 记录node的兄弟节点Node pointer1 = node.parent.right; // 如果node兄弟节点是红色if (pointer1.color == Color.Red) {pointer1.color = Color.Black; node.parent.color = Color.Red; leftRotate(node.parent); pointer1 = node.parent.right; }if (pointer1.left.color == Color.Black && pointer1.right.color == Color.Black) {pointer1.color = Color.Red; node = node.parent; } else if (pointer1.right.color == Color.Black) {pointer1.left.color = Color.Black; pointer1.color = Color.Red; rightRotate(pointer1); pointer1 = node.parent.right; } else {pointer1.color = node.parent.color; node.parent.color = Color.Black; pointer1.right.color = Color.Black; leftRotate(node.parent); node = this.root; }} else {// 记录node的兄弟节点Node pointer1 = node.parent.left; // 如果他兄弟节点是红色if (pointer1.color == Color.Red) {pointer1.color = Color.Black; node.parent.color = Color.Red; rightRotate(node.parent); pointer1 = node.parent.left; }if (pointer1.right.color == Color.Black && pointer1.left.color == Color.Black) {pointer1.color = Color.Red; node = node.parent; } else if (pointer1.left.color == Color.Black) {pointer1.right.color = Color.Black; pointer1.color = Color.Red; leftRotate(pointer1); pointer1 = node.parent.left; } else {pointer1.color = node.parent.color; node.parent.color = Color.Black; pointer1.left.color = Color.Black; rightRotate(node.parent); node = this.root; }}}node.color = Color.Black; }private void innerWalk(Node node) {if (node != NULL) {innerWalk(node.left); System.out.println(node); innerWalk(node.right); }}/*** 中序遍历*/public void innerWalk() {this.innerWalk(this.root); }/*** 层次遍历*/public void print() {Queue queue = new LinkedList<>(); queue.add(this.root); while (!queue.isEmpty()) {Node temp = queue.poll(); System.out.println(temp); if (temp.left != NULL)queue.add(temp.left); if (temp.right != NULL)queue.add(temp.right); }}// 查找public Node search(int key) {Node pointer = this.root; while (pointer != NULL && pointer.key != key) {pointer = pointer.key < key ? pointer.right : pointer.left; }return pointer; }}

6、演示 演示代码：

public class Test01 {public static void main(String[] args) {int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 }; RedBlackTree redBlackTree = new RedBlackTree(); for (int i = 0; i < arr.length; i++) {redBlackTree.insert(new Node(arr[i])); }System.out.println("树的高度： " + redBlackTree.root.height()); System.out.println("左子树的高度： " + redBlackTree.root.left.height()); System.out.println("右子树的高度： " + redBlackTree.root.right.height()); System.out.println("层次遍历"); redBlackTree.print(); // 要删除节点Node node = redBlackTree.search(4); redBlackTree.delete(node); System.out.println("树的高度： " + redBlackTree.root.height()); System.out.println("左子树的高度： " + redBlackTree.root.left.height()); System.out.println("右子树的高度： " + redBlackTree.root.right.height()); System.out.println("层次遍历"); redBlackTree.print(); }}

【利用Java实现红黑树】到此这篇关于利用Java实现红黑树的文章就介绍到这了,更多相关Java实现红黑树内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！

推荐阅读

• 

  永嘉风光 永嘉哪里好玩
• 

  劳动是意思相近的词吗 快乐是意思相近的词语吗
• 

  没开封茶叶会不会过期
• 

  迷你世界手机版怎么去竹桃林 桃林地形码迷你世界分享
• 

  画图工具怎么手绘一款简笔画蛋糕？画图工具手绘简笔画蛋糕的方法
• 

  win10epic遭遇了网络连接问题解决方法
• 

  荷包蛋面条怎么做 荷包蛋面条怎么做视频
• 

  4s店样品车可以买吗现在 4s店样品车可以买吗
• 

  汽车新四化是什么 谈谈汽车新四化
• 

  聪明的梅花鹿告诉了我们什么道理 一只梅花鹿告诉我们什么道理
• 

  周公解梦梦见骨灰盒是什么意思 梦见骨灰盒好不好
• 

  皮肤瘙痒冷敷多久最好
• 

  毛衣可以和其他衣服一起用洗衣机洗吗
• 

  十一岁的男孩怎么教育
• 

  win101909声卡没声音解决方法
• 

  3dmax怎么做雪景 关于3DMAX制作雪景的详细操作
• 

  品牌规划的流程
• 

  手机里库乐队删了怎么办 手机库乐队没了怎么办
• 

  准备从事棋牌游戏人员必读
• 

  审议不通过怎么写会议纪要 如何写会议纪要

• JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
• 关于QueryWrapper|关于QueryWrapper,实现MybatisPlus多表关联查询方式
• MybatisPlus使用queryWrapper如何实现复杂查询
• python学习之|python学习之 实现QQ自动发送消息
• 事件代理
• 孩子不是实现父母欲望的工具——林哈夫
• opencv|opencv C++模板匹配的简单实现
• Java|Java OpenCV图像处理之SIFT角点检测详解
• Node.js中readline模块实现终端输入
• java中如何实现重建二叉树