红黑树算是一种二叉搜索树的升级版，解决了顺序插入时不会像二叉搜索树那样形成链式的结构，增加了左旋右旋的机制，使二叉树基于平衡。
1. 红黑树的特点- 每个结点不是红色就是黑色。
- 不可能有连在一起的红色结点。
- 根结点一定为黑色。
- 每个红色结点的两个子结点都是黑色。
当前结点的父亲是红色，且叔叔结点也是红色时：
- 把父结点设为黑色
- 把叔叔结点设为黑色
- 把爷爷结点设为红色
- 把指针定义到爷爷结点上，当有违红黑树和特点时再进行变色或旋转
当前父结点是红色，叔叔结点为黑色，且当前结点为右子树，以父结点作为左旋。
2.3 右旋当前父结点是红色，叔叔结点为黑色，且当前结点为左子树，把父结点变为黑色，把爷爷结点变为红色，以爷爷结点旋转。
3. 代码实现红黑树（并获取前中后序）import java.util.ArrayList;
import java.util.List;
public class RedBlackTree {
private final int R = 0;
private final int B = 1;
private Node root;
private class Node {
int data;
int color;
Node left;
Node right;
Node parent;
Node(int data) {
this.data = data;
color = R;
}
@Override
public String toString() {
return "Node{data=" + data + ", color=" + (color == R ? "red" : "black") + '}';
}
}
public Node getInstanceNode(int data) {
return new Node(data);
}
public void insert(int data) {
Node node = new Node(data);
//插入根结点
if (root == null) {
node.color = B;
root = node;
return;
}
Node parent = root;
Node son ;
//左子树
if (data < parent.data) {
son = parent.left;
}else {
son = parent.right;
}
//递归
while (son != null) {
parent = son;
if (data < parent.data) {
son = parent.left;
}else {
son = parent.right;
}
}
if (data < parent.data) {
parent.left = node;
}else {
parent.right = node;
}
node.parent = parent;
//颜色变换
colorConvert(node);
}
public void colorConvert(Node node) {
Node parent;
Node grandpa;
//当父结点不为空且颜色为红色
while ((parent = node.parent) != null && parent.color == R) {
grandpa = parent.parent;
//如果父亲是爷爷的左子树
if (grandpa.left == parent) {
//获取叔叔结点
Node uncle = grandpa.right;
//如果叔叔结点不为空且颜色为红色
if (uncle != null && uncle.color == R) {
parent.color = B;
uncle.color = B;
grandpa.color = R;
continue;
}
if (node == parent.right) {
//左旋
leftRotate(parent);
//左旋后父子身份互换
Node temp = node;
node = parent;
parent = temp;
}
parent.color = B;
grandpa.color = R;
//右旋
rightRotate(grandpa);
}else {
//如果父亲是爷爷的右子树
Node uncle = grandpa.left;
if (uncle != null && uncle.color == R) {
parent.color = B;
uncle.color = B;
grandpa.color = R;
node = grandpa;
continue;
}
if (node != parent.left) {
//右旋
rightRotate(parent);
//右旋后父子身份互换
Node temp = node;
node = parent;
parent = temp;
}
parent.color = B;
grandpa.color = R;
//左旋
leftRotate(grandpa);
}
}
root.color = B;
}
private void leftRotate(Node node) {
Node right = node.right;
Node parent = node.parent;
if (parent == null) {
root = right;
right.parent = null;
}else {
if (parent.left != null && parent.left == node) {
parent.left = right;
}else {
parent.right = right;
}
right.parent = parent;
}
node.parent = right;
node.right = right.left;
if (right.left != null) {
right.left.parent = node;
}
right.left = node;
}
private void rightRotate(Node node) {
Node left = node.left;
Node parent = node.parent;
if (parent == null) {
root = left;
left.parent = null;
}else {
if (parent.left != null && parent.left == node) {
parent.left = left;
}else {
parent.right = left;
}
left.parent = parent;
}
node.parent = left;
node.left = left.right;
if (left.right != null) {
left.right.parent = node;
}
left.right = node;
}
private List beforeList = new ArrayList<>();
private void beforeTraversal(Node node) {
if (node != null) {
beforeList.add(node.data + "-" + (node.color == R ? "red" : "black"));
beforeTraversal(node.left);
beforeTraversal(node.right);
}
}
public List getBeforeList(RedBlackTree tree) {
tree.beforeTraversal(tree.getRoot());
return beforeList;
}
private List inList = new ArrayList<>();
private void inTraversal(Node node) {
if (node != null) {
inTraversal(node.left);
inList.add(node.data + "-" + (node.color == R ? "red" : "black"));
inTraversal(node.right);
}
}
public List getInList(RedBlackTree tree) {
tree.inTraversal(tree.getRoot());
return inList;
}
private List afterList = new ArrayList<>();
private void afterTraversal(Node node) {
if (node != null) {
afterTraversal(node.left);
if (node.right != null) {
afterTraversal(node.right);
}
afterList.add(node.data + "-" + (node.color == R ? "red" : "black"));
}
}
public List getAfterList(RedBlackTree tree) {
tree.afterTraversal(tree.getRoot());
return afterList;
}
//省略getter/setter...
}
测试：测试：将数组{10,8,12,5,9,1,6,7,6}转换为二叉搜索树并获取前中后序遍历。
public static void main(String[] args) {
int[] nums = {10,8,12,5,9,1,6,7,6};
RedBlackTree tree = new RedBlackTree();
for (int num : nums) {
tree.insert(num);
}
System.out.println("前序遍历：" + tree.getBeforeList(tree));
System.out.println("中序遍历：" + tree.getInList(tree));
System.out.println("后序遍历：" + tree.getAfterList(tree));
}
输出结果：
前序遍历：[8-black, 5-red, 1-black, 6-black, 6-red, 7-red, 10-red, 9-black, 12-black] 中序遍历：[1-black, 5-red, 6-red, 6-black, 7-red, 8-black, 9-black, 10-red, 12-black] 后序遍历：[1-black, 6-red, 7-red, 6-black, 5-red, 9-black, 12-black, 10-red, 8-black]
