Node（4000） and parent Node（3000） are both red。
RotateLeft（4000）：以Node（4000）为支点，左旋
public void leftRotate(TreeNode x) {
TreeNode y = x.right;
x.right = y.left;
if(y.left != this.NIL) {
y.left.parent = x;
}
y.parent = x.parent;
if(x.parent == this.NIL) { //x is root
this.root = y;
}
else if(x == x.parent.left) { //x is left child
x.parent.left = y;
}
else { //x is right child
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
Node(3000) and Node(4000) are both red, Node(3000) is left child, parent Node(4000) is left child of Node(5000), can fix with a single rotation. LR(4000).
x is Node(4000), y=x.left is Node(3000)
public void rightRotate(TreeNode x) {
TreeNode y = x.left;
x.left = y.right;
if(y.right != this.NIL) {
y.right.parent = x;
}
y.parent = x.parent;
if(x.parent == this.NIL) { //x is root
this.root = y;
}
else if(x == x.parent.right) { //x is left child
x.parent.right = y;
}
else { //x is right child
x.parent.left = y;
}
y.right = x;
x.parent = y;
}
完整源代码
enum Color {
Red, Black
}
class TreeNode {
public int data;
public TreeNode right;
public TreeNode left;
public TreeNode parent;
public Color color;
public TreeNode(int data) {
this.left = null;
this.right = null;
this.parent = null;
this.data = data;
this.color = Color.Red;
}
}
class RedBlackTree {
TreeNode root;
TreeNode NIL;
public RedBlackTree() {
TreeNode nilNode = new TreeNode(0);
nilNode.color = Color.Black;
this.NIL = nilNode;
this.root = this.NIL;
}
public void leftRotate(TreeNode x) {
TreeNode y = x.right;
x.right = y.left;
if(y.left != this.NIL) {
y.left.parent = x;
}
y.parent = x.parent;
if(x.parent == this.NIL) { //x is root
this.root = y;
}
else if(x == x.parent.left) { //x is left child
x.parent.left = y;
}
else { //x is right child
x.parent.right = y;
}
y.left = x;
x.parent = y;
}
public void rightRotate(TreeNode x) {
TreeNode y = x.left;
x.left = y.right;
if(y.right != this.NIL) {
y.right.parent = x;
}
y.parent = x.parent;
if(x.parent == this.NIL) { //x is root
this.root = y;
}
else if(x == x.parent.right) { //x is left child
x.parent.right = y;
}
else { //x is right child
x.parent.left = y;
}
y.right = x;
x.parent = y;
}
public void insertFixup(TreeNode z) {
while(z.parent.color == Color.Red) {
if(z.parent == z.parent.parent.left) { //z.parent is the left child
TreeNode y = z.parent.parent.right; //uncle of z
if(y.color == Color.Red) { //case 1
z.parent.color = Color.Black;
y.color = Color.Black;
z.parent.parent.color = Color.Red;
z = z.parent.parent;
}
else { //case2 or case3
if(z == z.parent.right) { //case2
z = z.parent; //marked z.parent as new z
leftRotate(z);
}
//case3
z.parent.color = Color.Black; //made parent black
z.parent.parent.color = Color.Red; //made parent red
rightRotate(z.parent.parent);
}
}
else { //z.parent is the right child
TreeNode y = z.parent.parent.left; //uncle of z
if(y.color == Color.Red) {
z.parent.color = Color.Black;
y.color = Color.Black;
z.parent.parent.color = Color.Red;
z = z.parent.parent;
}
else {
if(z == z.parent.left) {
z = z.parent; //marked z.parent as new z
rightRotate(z);
}
z.parent.color = Color.Black; //made parent black
z.parent.parent.color = Color.Red; //made parent red
leftRotate(z.parent.parent);
}
}
}
this.root.color = Color.Black;
}
public void insert(TreeNode z) {
TreeNode y = this.NIL; //variable for the parent of the added node
TreeNode temp = this.root;
while(temp != this.NIL) {
y = temp;
if(z.data < temp.data)
temp = temp.left;
else
temp = temp.right;
}
z.parent = y;
if(y == this.NIL) { //newly added node is root
this.root = z;
}
else if(z.data < y.data) //data of child is less than its parent, left child
y.left = z;
else
y.right = z;
z.right = this.NIL;
z.left = this.NIL;
insertFixup(z);
}
public void inorder(TreeNode n) {
if(n != this.NIL) {
inorder(n.left);
System.out.println(n.data);
inorder(n.right);
}
}
public static void main(String[] args) {
RedBlackTree t = new RedBlackTree();
TreeNode a, b, c, d, e, f, g, h, i, j, k, l, m;
a = new TreeNode(10);
b = new TreeNode(20);
c = new TreeNode(30);
d = new TreeNode(100);
e = new TreeNode(90);
f = new TreeNode(40);
g = new TreeNode(50);
h = new TreeNode(60);
i = new TreeNode(70);
j = new TreeNode(80);
k = new TreeNode(150);
l = new TreeNode(110);
m = new TreeNode(120);
t.insert(a);
t.insert(b);
t.insert(c);
t.insert(d);
t.insert(e);
t.insert(f);
t.insert(g);
t.insert(h);
t.insert(i);
t.insert(j);
t.insert(k);
t.insert(l);
t.insert(m);
t.inorder(t.root);
}
}
参考资料：
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
https://www.codesdope.com/course/data-structures-red-black-trees-insertion/
专注分享 Java、 Kotlin、Spring/Spring Boot、MySQL、redis、neo4j、NoSQL、Android、JavaScript、React、Node、函数式编程、编程思想、"高可用，高性能，高实时"大型分布式系统架构设计主题。
网友评论