一撞秋、《算法—深入淺出》N叉樹(shù)的介紹
二拱层、《算法—深入淺出》紅黑樹(shù)的旋轉(zhuǎn)
三抽减、《算法—深入淺出》紅黑樹(shù)的插入
四、《算法—深入淺出》紅黑樹(shù)的刪除
一、前言
紅黑樹(shù)（R-B Tree）佳簸，它是二叉樹(shù)中，最經(jīng)典也是最復(fù)雜的數(shù)據(jù)結(jié)構(gòu)颖变。
- 廣泛應(yīng)用于 C++ 的 STL 中生均， map 和 set 是用紅黑樹(shù)實(shí)現(xiàn)的；
- Linux 的進(jìn)程調(diào)度腥刹，使用紅黑樹(shù)管理進(jìn)程控制塊马胧，進(jìn)程的虛擬內(nèi)存空間都存儲(chǔ)在一顆紅黑樹(shù)上，每個(gè)虛擬內(nèi)存空間都對(duì)應(yīng)紅黑樹(shù)的一個(gè)結(jié)點(diǎn)衔峰，左指針指向相鄰的虛擬內(nèi)存空間佩脊，右指針指向相鄰的高地址虛擬內(nèi)存空間；
- IO 多路復(fù)用的 epoll 采用紅黑樹(shù)組織管理 sockfd朽色，以支持快速的增刪改查邻吞；
- Nginx 中采用紅黑樹(shù)管理定時(shí)器，因?yàn)榧t黑樹(shù)是有序的葫男，可以很快的得到距離當(dāng)前最小的定時(shí)器抱冷；
- Java 中的 TreeMap 和 TreeSet 也是采用紅黑樹(shù)實(shí)現(xiàn)；JDK8開(kāi)始梢褐，HashMap 也新增了紅黑樹(shù)旺遮，鏈表與紅黑樹(shù)可以互轉(zhuǎn)；
- 每個(gè)節(jié)點(diǎn)或者是黑色盈咳，或者是紅色耿眉；
- 根節(jié)點(diǎn)是黑色；
- 每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色鱼响； 【注意：這里葉子節(jié)點(diǎn)鸣剪，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)！】
- 如果一個(gè)節(jié)點(diǎn)是紅色的丈积，則它的子節(jié)點(diǎn)必須是黑色的筐骇；
- 從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)；
它的復(fù)雜在于：
- 插入節(jié)點(diǎn)時(shí)江滨，可能違反規(guī)定铛纬，從而需要遞歸來(lái)【旋轉(zhuǎn)+重新著色】；
- 刪除節(jié)點(diǎn)時(shí)唬滑，與插入節(jié)點(diǎn)類似的調(diào)整告唆，只是在調(diào)整前棺弊，需要先找到一個(gè)后繼節(jié)點(diǎn)來(lái)替換；
因此擒悬，我們可以看到模她，最復(fù)雜的調(diào)整，是刪除節(jié)點(diǎn)后的操作茄螃！
本篇不談插入與刪除菜秦，而是先打基礎(chǔ)：绰寞！
無(wú)論是插入還是刪除起愈，當(dāng)要調(diào)整時(shí)麸恍，都會(huì)旋轉(zhuǎn)子樹(shù)，然后再向上遞歸拼弃，直至最終滿足紅黑樹(shù)的特性夏伊。
二、旋轉(zhuǎn)
左旋是基于某個(gè)節(jié)點(diǎn)吻氧，整體（該節(jié)點(diǎn)連同其左溺忧、右子樹(shù)）向左旋轉(zhuǎn)；
右旋是基于某個(gè)節(jié)點(diǎn)盯孙，整體（該節(jié)點(diǎn)連同其左鲁森、右子樹(shù)）向右旋轉(zhuǎn)；
2.1振惰、數(shù)據(jù)結(jié)構(gòu)
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歌溉、生成二叉樹(shù)
{
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())
// 打印輸出（前序遍歷: 根 -> 左子樹(shù) -> 右子樹(shù)）
// 10, 5, 2, 8, 20, 16, 22
如下圖（我們后面的旋轉(zhuǎn)都基于 10 這個(gè)根節(jié)點(diǎn)來(lái)旋轉(zhuǎn)）
R-B Tree.png
2.3、左旋（算法只考慮旋轉(zhuǎn)骑晶，暫不管著色）
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
//【右子左節(jié)點(diǎn)】掛到【父的右節(jié)點(diǎn)】
parent.right = right.left; // g.右節(jié)點(diǎn) = y
if (right.left != null) {
right.left.parent = parent; // y.父節(jié)點(diǎn) = g
}
// 【祖父】與【左子 or 右子】
right.parent = parent.parent; // u.父節(jié)點(diǎn) = g.父節(jié)點(diǎn)
if (parent.parent != null) {
if (parent.parent.left == parent) {
parent.parent.left = right; // 祖父節(jié)點(diǎn).左節(jié)點(diǎn) = u
} else {
parent.parent.right = right;
}
} else {
root = right;
}
// 【父】與【右子】替換
parent.parent = right; // g.父節(jié)點(diǎn) = u
right.left = parent; // u.左節(jié)點(diǎn) = g
}
}
2.4痛垛、右旋（算法只考慮旋轉(zhuǎn)，暫不管著色）
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
// 【左子右節(jié)點(diǎn)】掛到【父的左節(jié)點(diǎn)】
parent.left = left.right; // g.左節(jié)點(diǎn) = x
if (left.right != null) {
left.right.parent = parent; // x.父節(jié)點(diǎn) = g
}
// 【祖父】與【左子 or 右子】
left.parent = parent.parent; // p.父節(jié)點(diǎn) = g.父節(jié)點(diǎn)
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.父節(jié)點(diǎn) = p
left.right = parent; // p.右節(jié)點(diǎn) = g
}
}
詳細(xì)請(qǐng)查看 Github 源碼：《紅黑樹(shù)完整的源碼》
