代码下载
Demooo/java-demoo/src/main/java/myredblacktree at master · cbeann/Demooo · GitHub
红黑树难点
红黑树性质
- 1.每一个节点要么是黑色,要么是红色的。
- 2.根节点是黑色。
- 3.叶子节点(Null)是黑色。
- 4.每一个红色节点的两个子节点一定都是黑色。不能有两个红色节点相连。
- 5.任意一个节点到每一个叶子节点的路径都包含相同的黑节点,俗称“黑高”(推论:如果一个节点存在黑子节点,那么该节点肯定有两个子节点)。
插入节点必为红色
假设插入的节点为红色,那么在不考虑空树的情况下,该插入节点的父节点可能为红色,也可能为黑色。如果父节点为黑色,插入后没有破坏红黑树的性质;如果父节点为红色,则破坏了红黑树性质(不能有两个红色节点相连)。
假设插入的节点为黑色,则插入后必破坏红黑树的性质(任意一个节点到每一个叶子节点的路径都包含相同的黑节点)
综上:插入节点必为红色
插入变色规则
插入后修复红黑树平衡的方法
情景1:红黑树为空树,插入节点将作为根,将根节点染色为黑色。
情景2:插入节点的key已经存在,则只需要替换value值即可。
情景3:插入节点的父节点为黑色,插入后不需要其他操作。(因为插入的的为红色,黑色节点没有变化,所以红黑树依然平衡,所以不需要处理)
情景4:插入节点的父节点为红色(非常复杂)
情景4-1:叔叔节点存在。并且叔叔为红色(父-叔 双红)。将爸爸和叔叔染色为黑色,将爷爷染色为红色,并且在以爷爷节点为当前节点,进行下一轮处理。
情景4-2:叔叔节点不存在或者为黑色。父节点为爷爷节点的左子树。
情景4-2-1:插入节点为其父节点的左子节点(LL情景)。将爸爸染色为黑色,将爷爷染色为红色,然后以爷爷节点右旋,就结束了。
情景4-2-2:插入节点为其父节点的右子节点(LR情景)。以爸爸节点进行一次左旋,得到LL双红的情景(4.2.1),然后指定爸爸节点为当前节点进行下一轮处理。
情景4-3:叔叔节点不存在,或者为黑色。父节点为爷爷节点的右子树
情景4-3-1:插入节点为其父节点的右子节点(RR情景)。将爸爸染色为黑色,将爷爷染色为红色,然后以爷爷节点左旋,就结束了。
情景4-3-2:插入节点为其父节点的左子节点(RL情景)。以爸爸节点进行一次右旋,得到RR双红的情景(4.3.1),然后指定爸爸节点为当前节点进行下一轮处理。
左旋右旋编码实现
以左旋为例,如下图和代码所示,虽然我的写的左旋代码很乱,但是只要知道修改了下图中红色标记的点的某几个指针(左子树、右子树、父节点),而且你也知道修改后的应该指向哪,那这个左旋就应该差不多了,编码的时候注意null,然后就实现了左旋代码。
/** * 左旋 * * @param x <br> * 图片:https://www.processon.com/view/link/5ff15f05e0b34d19e4f880f1 */ private void leftRotate(Node x) { if (x == null) { return; } // 记录父节点 Node parent = x.getParent(); // 记录X节点的左子树和右子树 Node xl = x.getLeft(); Node xr = x.getRight(); // ---> 修改父节点的指针 if (null != parent) { if (x == parent.left) { parent.left = xr; } else { parent.right = xr; } } else { // parent=null表示为根 this.root = xr; xr.parent = null; } // ---> 修改x节点的指针 // 修改左子树(不需要修改) // 修改右子树 if (xr != null) { x.right = xr.left; } // 修改父节点 x.parent = xr; // ---> 修改xl节点的指针(不需要修改) // ---> 修改xr节点的指针 if (xr != null) { // 修改左子树 xr.left = x; // 修改右子树(不需要修改) // 修改父节点 if (null != parent) { xr.parent = parent; } } // ---> 修改xrl节点的指针 // 修改左子树(不需要修改) // 修改右子树(不需要修改) // 修改父节点 if (xr.left != null) { xr.left.parent = x; } }
代码
Node节点
package myredblacktree; import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor; /** * @author chaird * @create 2021-01-03 13:46 <br> * 红黑树节点 */ @Data @AllArgsConstructor @NoArgsConstructor public class Node<K extends Comparable<K>, V> { public Node(K key, V value) { this.key = key; this.value = value; } // 父节点 Node parent; // 左子树 Node left; // 右子树 Node right; // 颜色,红色为true,黑色为false Boolean color; // key K key; // vale V value; @Override public String toString() { return "Node{" + ", color=" + color + ", key=" + key + ", value=" + value + '}'; } }
红黑树实体类
package myredblacktree; import lombok.Data; /** * @author chaird * @create 2021-01-03 13:52<br> * 红黑树 */ @Data public class RBTree<K extends Comparable<K>, V> { // 根节点 private Node root; // 定义红黑树常量 private static final boolean RED = true; private static final boolean BLACK = false; /** * 当前节点是否是红色 * * @param node * @return */ private Boolean isRed(Node node) { if (null != node) { return node.getColor() == RED; } return false; } /** * 当前节点是否是黑色 * * @param node * @return */ private Boolean isBlack(Node node) { if (null != node) { return node.getColor() == BLACK; } return false; } /** * 设置节点为红色 * * @param node */ private void setRed(Node node) { if (null != node) { node.setColor(RBTree.RED); } } /** * 设置节点为黑色 * * @param node */ private void setBlack(Node node) { if (null != node) { node.setColor(RBTree.BLACK); } } /** * 左旋 * * @param x <br> * 图片:https://www.processon.com/view/link/5ff15f05e0b34d19e4f880f1 */ private void leftRotate(Node x) { if (x == null) { return; } // 记录父节点 Node parent = x.getParent(); // 记录X节点的左子树和右子树 Node xl = x.getLeft(); Node xr = x.getRight(); // ---> 修改父节点的指针 if (null != parent) { if (x == parent.left) { parent.left = xr; } else { parent.right = xr; } } else { // parent=null表示为根 this.root = xr; xr.parent = null; } // ---> 修改x节点的指针 // 修改左子树(不需要修改) // 修改右子树 if (xr != null) { x.right = xr.left; } // 修改父节点 x.parent = xr; // ---> 修改xl节点的指针(不需要修改) // ---> 修改xr节点的指针 if (xr != null) { // 修改左子树 xr.left = x; // 修改右子树(不需要修改) // 修改父节点 if (null != parent) { xr.parent = parent; } } // ---> 修改xrl节点的指针 // 修改左子树(不需要修改) // 修改右子树(不需要修改) // 修改父节点 if (xr.left != null) { xr.left.parent = x; } } /** * 右旋 * * @param x <br> * 图片:https://www.processon.com/view/link/5ff1660807912977bede44d5 */ private void rightRotate(Node x) { if (null == x) { return; } // 记录父节点 Node parent = x.getParent(); // 记录X节点的左子树和右子树 Node xl = x.getLeft(); Node xr = x.getRight(); // ---> 修改父节点的指针 if (null != parent) { if (x == parent.left) { parent.left = xl; } else { parent.right = xl; } } else { // parent=null表示为根 this.root = xl; xl.parent = null; } // ---> 修改X节点的指针 // 修改左子树 if (xl != null) { x.left = xl.right; } // 修改右子树(不需要修改) // 修改父节点 x.parent = xl; // ---> 修改xl节点的指针 // 修改左子树(不需要修改) // 修改右子树 xl.right = x; // 修改父节点 xl.parent = parent; // ---> 修改XR节点的指针(不需要修改) // ---> 修改XLR节点的指针 // 修改左子树(不需要修改) // 修改右子树(不需要修改) // 修改父节点 if (xl.right != null) { xl.parent = x; } } public void insert(K key, V value) { Node node = new Node(key, value); // 新阶段一定是红色 node.setColor(RED); insert(node); } private void insert(Node node) { // 第一步:查找当前的node的父节点 Node parent = null; Node x = this.root; while (x != null) { parent = x; int cmp = node.getKey().compareTo(x.getKey()); if (cmp > 0) { x = x.getRight(); } else if (cmp < 0) { x = x.getLeft(); } else if (cmp == 0) { x.setValue(node.getValue()); return; } } node.setParent(parent); // 判断node是parent的左子树还是右子树 if (parent != null) { int cmp = node.getKey().compareTo(parent.getKey()); if (cmp > 0) { parent.setRight(node); } else { parent.setLeft(node); } } else { this.root = node; } // 需要调用红黑树平衡的方法 insertFixUp(node); } // 修复红黑树(复杂) /** * 插入后修复红黑树平衡的方法<br> * 情景1:红黑树为空树,将根节点染色为黑色。 <br> * 情景2:插入节点的key已经存在(不需要处理) <br> * 情景3:插入节点的父节点为黑色(因为插入的的为红色,黑色节点没有变化,所以红黑树依然平衡,所以不需要处理) <br> * 情景4:插入节点的父节点为红色(复杂) 情景4-1:叔叔节点存在。并且为红色(父-叔 双红)。将爸爸和叔叔染色为黑色,将爷爷染色为红色,并且在以爷爷节点为当前节点,进行下一轮处理 * 情景4-2:叔叔节点不存在,或者为黑色。父节点为爷爷节点的左子树 <br> * 情景4-2-1:插入节点为其父节点的左子节点(LL情景)。将爸爸染色为黑色,将爷爷染色为红色,然后以爷爷节点右旋,就结束了 * 情景4-2-2:插入节点为其父节点的右子节点(LR情景)。以爸爸节点进行一次左旋,得到LL双红的情景(4.2.1),然后指定爸爸节点为当前节点进行下一轮处理 * 情景4-3:叔叔节点不存在,或者为黑色。父节点为爷爷节点的右子树 <br> * 情景4-3-1:插入节点为其父节点的右子节点(RR情景)。将爸爸染色为黑色,将爷爷染色为红色,然后以爷爷节点左旋,就结束了 * 情景4-3-2:插入节点为其父节点的左子节点(RR情景)。以爸爸节点进行一次右旋,得到RR双红的情景(4.3.1),然后指定爸爸节点为当前节点进行下一轮处理 * * @param node */ private void insertFixUp(Node node) { // 情景1:红黑树为空树,将根节点染色为黑色。 if (this.root == node) { setBlack(node); } // 情景2:插入节点的key已经存在(不需要处理) (走不到这里) // 情景3:插入节点的父节点为黑色(因为插入的的为红色,黑色节点没有变化,所以红黑树依然平衡,所以不需要处理) <br> if (node.getParent() != null && isBlack(node.getParent())) { return; } // 情景4:插入节点的父节点为红色(复杂) if (node.getParent() != null && isRed(node.getParent())) { Node parent = node.getParent(); Node gParent = parent.getParent(); Node uncle = null; if (parent == gParent.left) { // 爸爸是爷爷的左子树 uncle = gParent.right; } else { // 爸爸是爷爷的右子树 uncle = gParent.left; } // 情景4-1:叔叔节点存在。并且为红色(父-叔 双红)。将爸爸和叔叔染色为黑色,将爷爷染色为红色,并且在以爷爷节点为当前节点,进行下一轮处理 if (null != uncle && isRed(uncle)) { setBlack(parent); setBlack(uncle); setRed(gParent); insertFixUp(gParent); return; } // 情景4-2:叔叔节点不存在,或者为黑色。父节点为爷爷节点的左子树 if (null == uncle || isBlack(uncle)) { if (parent == gParent.left) { // 情景4-2-1:插入节点为其父节点的左子节点(LL情景)。将爸爸染色为黑色,将爷爷染色为红色,然后以爷爷节点右旋,就结束了 if (node == parent.left) { setBlack(parent); setRed(gParent); rightRotate(gParent); return; } else { leftRotate(parent); insertFixUp(parent); return; } } } // 情景4-3:叔叔节点不存在,或者为黑色。父节点为爷爷节点的右子树 if (null == uncle || isBlack(uncle)) { if (parent == gParent.right) { if (node == parent.right) { setBlack(parent); setRed(gParent); leftRotate(gParent); return; } else { rightRotate(parent); insertFixUp(parent); return; } } } } } }
打印红黑树工具类(针对本文)
package myredblacktree; /** * @author chaird * @create 2021-01-03 10:21 */ public class TreeOperation { /* 树的结构示例: 1 / \ 2 3 / \ / \ 4 5 6 7 */ // 用于获得树的层数 public static int getTreeDepth(Node root) { return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right))); } private static void writeArray( Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) { // 保证输入的树不为空 if (currNode == null) return; // 先将当前节点保存到二维数组中 // res[rowIndex][columnIndex] = String.valueOf(currNode.value); //加颜色 res[rowIndex][columnIndex] = String.valueOf(currNode.value + "-" + (currNode.color ? "红" : "黑") + ""); // 计算当前位于树的第几层 int currLevel = ((rowIndex + 1) / 2); // 若到了最后一层,则返回 if (currLevel == treeDepth) return; // 计算当前行到下一行,每个元素之间的间隔(下一行的列索引与当前元素的列索引之间的间隔) int gap = treeDepth - currLevel - 1; // 对左儿子进行判断,若有左儿子,则记录相应的"/"与左儿子的值 if (currNode.left != null) { res[rowIndex + 1][columnIndex - gap] = "/"; writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth); } // 对右儿子进行判断,若有右儿子,则记录相应的"\"与右儿子的值 if (currNode.right != null) { res[rowIndex + 1][columnIndex + gap] = "\\"; writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth); } } public static void show(Node 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 myredblacktree; /** * @author chaird * @create 2021-01-03 13:50 */ public class Main { public static void main(String[] args) { RBTree<Integer, Object> tree = new RBTree(); tree.insert(1, 1); tree.insert(2, 2); tree.insert(3, 3); tree.insert(4, 4); tree.insert(5, 5); tree.insert(6, 6); tree.insert(7, 7); tree.insert(8, 8); TreeOperation.show(tree.getRoot()); } }