2020-10-08目前代码只记录了插入过程和插入之后的恢复过程代码，删除过程代码还在整理.
package com.lsx.tree; public class RedBlackTree { //红色，默认用红色 private final int R = 0; //黑色 private final int B = 1; private Node root = null; // 红黑树的根节点 class Node { //存储数据 int data; //颜色 int color = R; //左 Node left; //右 Node right; //父节点 Node parent; public Node(int data) { this.data = data; } } /** * 插入数据 * * @param newNode */ public void inset(Node newNode) { Node r = this.root; //新节点的父节点 Node py = null; //定位新节点要插入到那个位置 while (r != null) { //存储找到了位置的父节点信息 py = r; if (r.data < newNode.data) { r = r.right; } else if (r.data > newNode.data) { r = r.left; } else { //节点值相等，替新出的节点替换掉老的节点，为啥：如果节点值是一个对象， // 如果使用ID来判断对象是否是同一个的时候，可能对象某个数据发生了变化。 if (r.parent == null) { this.root = newNode; } else { if (r.parent.left == r) { r.parent.left = newNode; } else { r.parent.right = newNode; } r = null; newNode.parent = r.parent; } return; } } newNode.parent = py; if (py != null) { if (py.data < newNode.data) { py.right = newNode; } else { py.left = newNode; } } //插入的新节点默认是红色。 //修正为一颗二叉查找树 insertFixUp(newNode); } /** * 修正为一颗红黑树，节点插入正确位置之后，需要把树进行整理 * 1.变色 * 2.看看要怎么旋转 * * @param newNode */ private void insertFixUp(Node newNode) { Node parent, gparent; //诺父节点存在，并且父节点的颜色都是红色. //如果父节点是黑色，则不用修正 while ((parent = newNode.parent) != null && isRed(parent)) { //获取祖父结点 gparent = parent.parent; //检查父节点是左子树还是右子树 if (gparent.left == parent) { //父节点是左子树 // Case 1条件：叔叔节点是红色 // 黑 // 红(p) 红（u） //红 Node uncle = gparent.right; //case 1 if (uncle != null && isRed(uncle)) { setBlack(uncle); setBlack(parent); setRead(gparent); newNode = gparent; continue; } //case 2 // 此时uncle是null或者颜色是黑色（null也是黑色），且当前插入节点是右孩子， //旋转成插入节点在父节点的左边，形成pg ->p->newnode都是在左边 if (parent.right == newNode) { leftRotate2(parent); Node tmp; //旋转完成之后，把newNode的引用改成parent tmp = parent; parent = newNode; newNode = tmp; } //case 2.1 //叔叔全是黑色，当前节点是左孩子，进行一下右旋 setRead(gparent); setBlack(parent); rightRotate2(gparent); //处理完这个之后，while会在isRed(parent)不成立而结束循环 } else { //右子树 // Case 1条件：叔叔节点是红色 // 黑 // 红(u) 红（p） //红 Node uncle = gparent.left; //caes 1 if (uncle != null && isRed(uncle)) { //变色 setBlack(uncle); setBlack(parent); setRead(gparent); newNode = gparent; continue; } //case 2 //此时uncle是null或者颜色是黑色（null也是黑色） //线程pg -p->newNode都是在右边 if (parent.left == newNode) { //旋转成插入节点在父节点的左边 rightRotate2(parent); Node tmp; //旋转完成之后，把newNode的引用改成parent tmp = parent; parent = newNode; newNode = tmp; } //case 2.1 setRead(gparent); setBlack(parent); rightRotate2(gparent); //处理完这个之后，while会在isRed(parent)不成立而结束循环 } } //这行代码处理的是树为空的时候，插入的第一个节点 setBlack(this.root); } /** * 单独写出来是方便后期如果01表示的含义不是红黑，好方便修改 * * @param node * @return */ private boolean isRed(Node node) { return node.color == R; } private void setRead(Node node) { node.color = R; } private void setBlack(Node node) { node.color = B; } /* * 对红黑树的节点(x)进行左旋转 * * 左旋示意图(对节点x进行左旋)： * px px * / / * x y * / \ --(左旋)-. / \ # * lx y x ry * / \ / \ * ly ry lx ly * * */ public void leftRotate2(Node node) { //获取它的右边节点 Node y = node.right; //新数据，把y的左节点处理 node.right = y.left; if (y.left != null) { y.left.parent = node; } //处理node节点的父节点 if (node.parent.left == node) { //当前node节点是左边的 node.parent.left = y; } else if (node.parent.right == node) { //右边的 node.parent.right = y; } else { //如果父节点是空，就把新的根节点设置为树的根节点 root = y; } //处理y节点 y.left = node; node.parent = y; } /* * 对红黑树的节点(y)进行右旋转 * * 右旋示意图(对节点y进行左旋)： * py py * / / * y x * / \ --(右旋)-. / \ * x ry lx y * / \ / \ * lx rx rx ry * */ public void rightRotate2(Node node) { Node x = node.left; node.left = x.right; if (x.right != null) { node.left.parent = node; } if (node.parent.left != null) { node.parent.left = x; } else if (node.parent.right != null) { node.parent.right = x; } else { root = x; } x.right = node; node.parent = x; } }
