一、《算法—深入浅出》N叉树的介绍
二、《算法—深入浅出》红黑树的旋转
三、《算法—深入浅出》红黑树的插入
四、《算法—深入浅出》红黑树的删除
一、前言
红黑树（R-B Tree），它是二叉树中，最经典也是最复杂的数据结构。
- 广泛应用于 C++ 的 STL 中， map 和 set 是用红黑树实现的；
- Linux 的进程调度，使用红黑树管理进程控制块，进程的虚拟内存空间都存储在一颗红黑树上，每个虚拟内存空间都对应红黑树的一个结点，左指针指向相邻的虚拟内存空间，右指针指向相邻的高地址虚拟内存空间；
- IO 多路复用的 epoll 采用红黑树组织管理 sockfd，以支持快速的增删改查；
- Nginx 中采用红黑树管理定时器，因为红黑树是有序的，可以很快的得到距离当前最小的定时器；
- Java 中的 TreeMap 和 TreeSet 也是采用红黑树实现；JDK8开始，HashMap 也新增了红黑树，链表与红黑树可以互转；
- 每个节点或者是黑色，或者是红色；
- 根节点是黑色；
- 每个叶子节点（NIL）是黑色； 【注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！】
- 如果一个节点是红色的，则它的子节点必须是黑色的；
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点；
它的复杂在于：
- 插入节点时，可能违反规定，从而需要递归来【旋转+重新着色】；
- 删除节点时，与插入节点类似的调整，只是在调整前，需要先找到一个后继节点来替换；
因此，我们可以看到，最复杂的调整，是删除节点后的操作！
本篇不谈插入与删除，而是先打基础：！
无论是插入还是删除，当要调整时，都会旋转子树，然后再向上递归，直至最终满足红黑树的特性。
二、旋转
左旋是基于某个节点，整体（该节点连同其左、右子树）向左旋转；
右旋是基于某个节点，整体（该节点连同其左、右子树）向右旋转；
2.1、数据结构
public class RBTree {
private TreeNode root;
public RBTree(TreeNode root) {
this.root = root;
}
public static class TreeNode {
public static final int BLACK = 0;
public static final int RED = 1;
public int value;
public int color = BLACK;
public TreeNode parent;
public TreeNode left;
public TreeNode right;
public TreeNode(int value) {
this.value = value;
}
public TreeNode(int value, TreeNode parent) {
this.value = value;
this.parent = parent;
}
}
}
2.2、生成二叉树
{
private TreeNode getTree() {
TreeNode head = new TreeNode(10);
head.left = new TreeNode(5, head);
head.left.left = new TreeNode(2, head.left);
head.left.right = new TreeNode(8, head.left);
head.right = new TreeNode(20, head);
head.right.left = new TreeNode(16, head.right);
head.right.right = new TreeNode(22, head.right);
return head;
}
// 前序打印方法
private void doPreTravel(TreeNode node) {
if (node == null) {
return;
}
System.out.println((node.parent == null ? "(root)" : "") + node.value);
doPreTravel(node.left);
doPreTravel(node.right);
}
}
// doPreTravel(getTree())
// 打印输出（前序遍历: 根 -> 左子树 -> 右子树）
// 10, 5, 2, 8, 20, 16, 22
如下图（我们后面的旋转都基于 10 这个根节点来旋转）
R-B Tree.png
2.3、左旋（算法只考虑旋转，暂不管着色）
R-B Tree Rotate Left.png
public class RBTree {
private TreeNode root;
/*****************************************************************************************************************
* (1) | (2)
* g(10) u(20) | g g
* / \ / \ | / /
* p(5) u(20) => g(10) z(22) | p => u
* / \ / \ / \ | \ /
* c(2) x(8) y(16) z(22) p(5) y(16) | u p
* / \ |
* c(2) x(8) |
* |
*****************************************************************************************************************/
public void rotateLeft(TreeNode parent) {
TreeNode right = parent.right; // u
//【右子左节点】挂到【父的右节点】
parent.right = right.left; // g.右节点 = y
if (right.left != null) {
right.left.parent = parent; // y.父节点 = g
}
// 【祖父】与【左子 or 右子】
right.parent = parent.parent; // u.父节点 = g.父节点
if (parent.parent != null) {
if (parent.parent.left == parent) {
parent.parent.left = right; // 祖父节点.左节点 = u
} else {
parent.parent.right = right;
}
} else {
root = right;
}
// 【父】与【右子】替换
parent.parent = right; // g.父节点 = u
right.left = parent; // u.左节点 = g
}
}
2.4、右旋（算法只考虑旋转，暂不管着色）
R-B Tree Rotate Right.png
public class RBTree {
private TreeNode root;
/*****************************************************************************************************************
* (1) | (2)
* g(10) p(5) | p g
* / \ / \ | / / \
* p(5) u(20) => c(2) g(10) | g => x p
* / \ / \ / \ | /
* c(2) x(8) y(16) z(22) x(8) u(20) | x
* / \ |
* y(16) z(22) |
* |
*****************************************************************************************************************/
private void rotateRight(TreeNode parent) {
TreeNode left = parent.left; // p
// 【左子右节点】挂到【父的左节点】
parent.left = left.right; // g.左节点 = x
if (left.right != null) {
left.right.parent = parent; // x.父节点 = g
}
// 【祖父】与【左子 or 右子】
left.parent = parent.parent; // p.父节点 = g.父节点
if (parent.parent != null) {
if (parent.parent.left == parent) {
parent.parent.left = left;
} else {
parent.parent.right = left;
}
} else {
root = left;
}
// 【父】与【左子】替换
parent.parent = left; // g.父节点 = p
left.right = parent; // p.右节点 = g
}
}
详细请查看 Github 源码：《红黑树完整的源码》
网友评论