044：手写Java红黑树（未变色旋转）
1 二叉搜索树存在那些问题
课程内容：
1.为什么二叉树不用？用红黑树树结构？
2.为什么都觉得红黑树非常难？到底难在那里？
3.实现红黑树基本特征到底有那些？
4.细谈红黑树如果规则被破坏？如何实现修复
二叉搜索树存在的问题：不平衡。使用第一次添加的节点作为根节点，如果后面添加节点值都大于根节点值的情况下，会形成链表。查找时间复杂度变为O(n)。平衡二叉树会通过旋转解决以上问题，红黑树是平衡二叉树的一种实现方案。
2 红黑树的数据结构基本介绍
平衡二叉树旋转过程：
红黑树旋转过程（左旋）：
3 红黑树基本的特征介绍
基本特征：
- 每个节点不是红色就是黑色
- 不允许两红相连
- 根节点都是黑色
- 每个红色节点的两个子节点都是黑色
- 默认情况下添加的节点为红色节点
备注：如果产生了红色相连如何解决：变色或者旋转。
红黑树变换规则：
1.改变节点颜色
2.左旋转
3.右旋转
4 红黑树变换颜色的规则要求
变色或者旋转都是插入节点后修复平衡的实现。
改变颜色和旋转
变色：当前节点父亲是红色，叔叔节点（祖父节点的另一个子节点）也是红色：
1.将父亲节点设置为黑色
2.将叔叔节点设为黑色
3.将祖父也就是父亲的父亲设为红色
4.把指针定义到祖父节点设为当前操作
左旋转：当父亲节点为红色情况，叔叔的节点为黑色的情况，且当前的节点是右子树，左旋转以父节点作为左旋；
右旋转：当父亲节点为红色情况，叔叔的节点为黑色的情况，且当前的节点是左子树，右旋转以
- 父节点作为右旋；
- 将父节点变为黑色
- 将祖父节点变为红色(爷爷)
- 以祖父节点开始旋转
5 红黑树左右旋转基本的规则
6 手写红黑树环境代码实现（未变色旋转）
public enum NodeColor {
red(1, "red"),
black(2, "black");
int color;
String desc;
NodeColor(int color, String desc) {
this.color = color;
this.desc = desc;
}
}
public class RedBlackTree {
/**
* 记录根节点
*/
private Node root;
class Node {
/**
* 节点内容值
*/
private int value;
/**
* 左节点
*/
private Node left;
/**
* 右子树
*/
private Node right;
/**
* 节点颜色
*/
private NodeColor color;
/**
* 记录当前节点父节点
*/
private Node parent;
}
public void insert(int value) {
if (root == null) {
// 封装根节点
Node newNode = new Node();
newNode.parent = null;
// 根节点一定为黑色
newNode.color = NodeColor.black;
// 设置节点值
newNode.value = value;
root = newNode;
} else {
// 根节点存在，二叉搜索数形式插入节点
Node node = insertValue(value);
// 红黑树修复
repairTree(node);
}
}
private void repairTree(Node newNode) {
if (newNode.parent.color.equals(NodeColor.red)) {
if (newNode.color.equals(NodeColor.red)) {
// 红黑树变色或者旋转
}
}
}
private Node insertValue(int value) {
return getPosition(root, value);
}
private Node getPosition(Node node, int value) {
if (value > node.value) {
// 右子树
if (node.right == null) {
// 右边第一次赋值
Node newNode = new Node();
// 新增节点颜色默认红色
newNode.color = NodeColor.red;
// 节点赋值
newNode.value = value;
// 节点指向关系
newNode.parent = node;
node.right = newNode;
return newNode;
} else {
// 递归调用
return getPosition(node.right, value);
}
} else {
// 左子树
if (node.left == null) {
// 左边第一次赋值
Node newNode = new Node();
// 新增节点颜色默认红色
newNode.color = NodeColor.red;
// 节点赋值
newNode.value = value;
// 节点指向关系
newNode.parent = node;
node.left = newNode;
return newNode;
} else {
return getPosition(node.left, value);
}
}
}
}
public class Test {
public static void main(String[] args) {
RedBlackTree redBlackTree = new RedBlackTree();
redBlackTree.insert(1);
redBlackTree.insert(2);
redBlackTree.insert(3);
}
}
断点调试：