红黑树的原理_Linux内核-红黑树的实现原理及应用
一、红黑树简介
什么是红黑树
红黑树(R-B Tree, 全称 Red-Black Tree)是一种特殊的二叉查找树, 其中每个节点都有颜色, 红色或者黑色.
红黑树的特性:
- 树的节点是黑色或者红色
- 树的根节点和指向null的叶子节点都是黑色
- 不能有两个红色节点是连续的
- 每个节点至为null的子节点的任何路径, 都含有相同数量的黑色节点
示例:
8B
/
4R 9B
/
2B 6B
/ /
1R 3R 5R 7R
二、红黑树的应用和时间复杂度
- 主要是 Java 中的 TreeMap 和 TreeSet. jdk1.8 之后, HashMap 的table中的链表长度大于8的时候也是用 红黑树.
- 时间复杂度: 查找, 插入, 删除都可以在 O(log n) 内完成. 且节点数为 n 的数高度最大为 2log(n+1).
红色树的操作
节点的基本定义
//节点定义
public class RBTNode<T extends Comparable<T>> {
public boolean isBlack;
public T key;
public RBTNode<T> parent;
public RBTNode<T> left;
public RBTNode<T> right;
public RBTNode(T key, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right, boolean isBlack) {
this.isBlack = isBlack;
this.key = key;
this.parent = parent;
this.left = left;
this.right = right;
}
public String toString() {
return "key: " + key + (isBlack ? " B " : " R ") +
(parent != null ? (
((parent.left != null && parent.left == this) ?
parent.key + " Left" :
(parent.right != null && parent.right == this) ?
parent.key + " Right" : ""))
: "");
}
}
旋转 - 左旋转的两种情况
旋转的中心思想是: 从新设置 x 节点, y 节点的 左 父 右 节点, 并设置关联变化的节点的父节点.
px px | px px
| / /
x y | x -> y
/ -> / | / /
lx y x ry | lx y x ry
/ / | / /
ly ry lx ly | ly ry lx ly
// 对 x 进行左旋转, 将 x 是 y 的父节点变成, y 是 x 的父节点.
private void rotateLeft(RBTNode<T> x) {
RBTNode<T> y = x.right;
// 1. 设置x 的 左 父 右 节点
// 1-1 x的左节点无变化
// 1-2 x的右节点, 设置x右节点的父节点
x.right = y.left;
if(y.left != null) y.left.parent = x;
// 1-3 x的父节点无变化
//2. 设置y 的 左 父 右 节点
//2-1: 设置y的父节点
y.parent = x.parent;
if (x.parent == null) this.root = y;
else if (x.parent.left == x) x.parent.left = y;
else x.parent.right = y;
//2-2: 设置y 的左节点
y.left = x;
x.parent = y;
//2-3: y节点的右节点无变化
}
旋转 - 右旋转的两种情况
py py | py py
/ / |
y x | y -> x
/ -> / | / /
x ry lx y | x ry lx y
/ / | / /
lx rx rx ry | lx rx rx ry
// 对 y 进行右旋转, 将 y 是 x 的父节点 变成 x 是 y 的父节点
private void rotateRight(RBTNode<T> y) {
RBTNode<T> x = y.left;
//1: 设置y 的左 父 右 节点
//1-1: 设置y 的左节点, 并设置其父节点
y.left = x.right;
if (x.right != null) x.right.parent = y;
//2-2: 设置x的父节点
x.parent = y.parent;
//1-3: y的右节点无变化
//2: 设置x 的左 右 父节点
//2-2: 设置x 的父节点, 及其父节点的子节点
if (y.parent == null) this.root = x;
else if (y == y.parent.right) y.parent.right = x;
else y.parent.left = x;
//2-1: 设置 x的右节点, 并设置其父节点
x.right = y;
//1-2: 设置y 的父节点
y.parent = x;
//2-3 x的左节点无变化
}
插入并修正
- 若root 是null , 则插入节点就是root 节点.
- 若root 不是null, 则向下查找node 的父节点, 并根据与父节点的大小关系, 写入待插入节点. 插入的节点都是红色
- 修正插入的树.
- 修正过程, 修正的核心思想是: 将红色节点移动到根节点, 将根节点设为黑色.
// 插入修正
private void insertFix(RBTNode<T> node) {
RBTNode<T> parent;
RBTNode<T> grandParent;
while (isRed(parentOf(node))) {
parent = parentOf(node);
grandParent = parentOf(parent);
RBTNode<T> uncle;
if (parent == grandParent.left) {
uncle = grandParent.right;
if (isRed(uncle)) { // 情况 1
setBlack(parent);
setBlack(uncle);
setRed(grandParent);
node = grandParent;
continue;
}
if (isBlack(uncle)) {
if (parent.right == node) { // 情况 4
node = parent;
rotateLeft(grandParent);
} else { // 情况 5
setBlack(parent);
setRed(grandParent);
rotateRight(grandParent);
}
}
} else {
uncle = grandParent.left;
if (isRed(uncle)) { // 情况 1
setBlack(uncle);
setBlack(parent);
setRed(grandParent);
node = grandParent;
continue;
}
if (isBlack(uncle)) {
if (parent.left == node) { // 情况 2
node = parent;
rotateRight(node);
} else { // 情况 3
setBlack(parent);
setRed(grandParent);
rotateLeft(grandParent);
}
}
}
}
}
// 插入
public void insert(RBTNode<T> node) {
if (this.root == null) {
this.root = node;
} else {
int compare = 0;
RBTNode<T> temp = null;
RBTNode<T> current = this.root;
//1. 先查找二叉树, 确定node的插入位置
while (current != null) {
temp = current;
compare = node.getKey().compareTo(current.getKey());
if (compare < 0) current = current.getLeft();
else current = current.getRight();
}
node.setParent(temp);
compare = node.getKey().compareTo(temp.getKey());
if (compare < 0) temp.setLeft(node);
else temp.setRight(node);
}
insertFix(node);
setBlack(root);
}
删除并修正
- 核心思想: 将被删节点所包含的额外黑色节点(右节点)不断往根节点方向移动并按照情况修正
- 修正的方法
完整实现
public class RBTree<T extends Comparable<T>> {
private RBTNode<T> root;
public void preOrder() {
preOrder(root);
}
private void preOrder(RBTNode<T> node) {
if (node != null) {
System.out.println(node + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public void inOrder() {
inOrder(root);
}
private void inOrder(RBTNode<T> node) {
if (node != null) {
inOrder(node.left);
System.out.println(node.toString());
inOrder(node.right);
}
}
public void postOrder() {
postOrder(root);
}
private void postOrder(RBTNode<T> node) {
if (node != null) {
preOrder(node.left);
preOrder(node.right);
System.out.println(node + " ");
}
}
public void insert(T key) {
insert(new RBTNode<T>(key, null, null, null, false));
}
private void insert(RBTNode<T> node) {
}
private RBTNode<T> parentOf(RBTNode<T> x) {
return (x == null ? null : x.parent);
}
private boolean isRed(RBTNode<T> x) {
if (x == null) return false;
return !x.isBlack;
}
private boolean isBlack(RBTNode<T> x) {
return (x == null || x.isBlack);
}
private void setRed(RBTNode<T> x) {
if (x != null)
x.isBlack = false;
}
private void setBlack(RBTNode<T> x) {
if (x != null)
x.isBlack = true;
}
private void insertFix(RBTNode<T> node) {
}
private void rotateRight(RBTNode<T> y) {
}
private void rotateLeft(RBTNode<T> x) {
}
public void remove(RBTNode<T> node) {
}
}
//测试代码
public static void main(String[] args) {
RBTree<Integer> tree = new RBTree<>();
int[] arr = new int[]{9, 8, 3, 5, 4, 2, 7, 6, 1};
for (int item : arr)
tree.insert(9);
System.out.println("前序");
tree.preOrder();
System.out.println("----------------------");
System.out.println("中序");
tree.inOrder();
System.out.println("----------------------");
System.out.println("后序");
tree.postOrder();
}
// 前序
// key: 8 B
// key: 4 R 8 Left
// key: 2 B 4 Left
// key: 1 R 2 Left
// key: 3 R 2 Right
// key: 6 B 4 Right
// key: 5 R 6 Left
// key: 7 R 6 Right
// key: 9 B 8 Right
// ----------------------
// 中序
// key: 1 R 2 Left
// key: 2 B 4 Left
// key: 3 R 2 Right
// key: 4 R 8 Left
// key: 5 R 6 Left
// key: 6 B 4 Right
// key: 7 R 6 Right
// key: 8 B
// key: 9 B 8 Right
// ----------------------
// 后序
// key: 4 R 8 Left
// key: 2 B 4 Left
// key: 1 R 2 Left
// key: 3 R 2 Right
// key: 6 B 4 Right
// key: 5 R 6 Left
// key: 7 R 6 Right
// key: 9 B 8 Right
// key: 8 B
【linux内核】大牛教你学Linux内核红黑树应用(上)
【linux内核】大牛教你学Linux内核红黑树应用(中)
【linux内核】大牛教你学Linux内核红黑树应用(下)
首先恭喜您，能够认真的阅读到这里，如果对部分理解不太明白，建议先将文章收藏起来，然后对不清楚的知识点进行查阅，然后在进行阅读，相应你会有更深的认知。如果您喜欢这篇文章，就点个赞或者【关注我】吧！！