史上最負(fù)盛名的平衡二叉樹–紅黑樹，但其實(shí)就是2-3樹的一種實(shí)現(xiàn)
一、紅黑樹性質(zhì)
也是BST，每一個節(jié)點(diǎn)都有顏色
性質(zhì) 看 后面推導(dǎo)出來的結(jié)論
二、紅黑樹性質(zhì)推導(dǎo)過程
2-3樹
2-3樹：和紅黑樹是等價的
滿足BST的基本性質(zhì)，但不是一種二叉樹
有兩種節(jié)點(diǎn)：
2-3 絕對平衡：根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 一定相同
2.3.1 如何維護(hù)絕對平衡2-3樹
add 2點(diǎn)會變3節(jié)點(diǎn)
再添加，3節(jié)點(diǎn)會 先融合 形成4節(jié)點(diǎn)
再對這個4節(jié)點(diǎn)分裂成 BST
再添加 18 ，會直接在12上形成3節(jié)點(diǎn)
再添加節(jié)點(diǎn)6
- 先形成4節(jié)點(diǎn)，再拆分
但是這樣就不是決定平衡了
因此需要向上融合
再添加11, 直接在6上融合成3節(jié)點(diǎn)
再添加5，融合在分裂
還需要向上融合
這次還需要向下分裂了
2.3.2 紅黑樹&2-3樹
b - c 之間的邊用紅色表示，代表b & c是在2-3樹的同一個節(jié)點(diǎn)的
BST中對于邊是沒有特殊標(biāo)識的，紅色如何標(biāo)識？
所以就用節(jié)點(diǎn)的顏色
b標(biāo)記為紅色，標(biāo)識代表 紅色的b 和 黑色的c是在同一個節(jié)點(diǎn)上的
因?yàn)榘裝當(dāng)做子節(jié)點(diǎn)來看待的，是人為定義的
2.3.3 再來看紅黑樹的性質(zhì)
1.每個節(jié)點(diǎn)為 Black or Red
2.根節(jié)點(diǎn)是Black
紅色的是往下的
3.每一個葉子節(jié)點(diǎn)(最后的空節(jié)點(diǎn))是黑色的
其實(shí)這不是性質(zhì) 而是定義，定義空節(jié)點(diǎn)是黑色的
4.if 節(jié)點(diǎn) 是紅色的，so 他的孩子節(jié)點(diǎn)都是黑色的
4.2 黑色節(jié)點(diǎn)的右孩子一定是黑色的
因?yàn)橛疫呉彩羌t色的話，就會分裂了
5.從任意一個節(jié)點(diǎn)到葉子節(jié)點(diǎn)，經(jīng)過的黑色節(jié)點(diǎn)是一樣的
2-3樹是絕對平衡的：從2-3數(shù)任意節(jié)點(diǎn)出發(fā)到葉子節(jié)點(diǎn)是相同的
在紅黑樹中就是 經(jīng)過的黑色的節(jié)點(diǎn)，
所以也就說，紅黑樹是一種保持 黑平衡 的二叉樹(不是平衡二叉樹)
紅黑樹 最大高度：2long(n) O(logn)
三、紅黑樹實(shí)現(xiàn)
添加 紅黑 標(biāo)記 ，用Boolean實(shí)現(xiàn)就可以
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node{
public K key;
public V value;
public Node left, right;
public boolean color;
public Node(K key, V value){
this.key = key;
this.value = value;
left = null;
right = null;
color = RED;
}
}
判斷是否是紅節(jié)點(diǎn)，主要處理空節(jié)點(diǎn)
// 判斷節(jié)點(diǎn)node的顏色
private boolean isRed(Node node){
if(node == null)
return BLACK;
return node.color;
}
3.2 紅黑樹add
添加到2-節(jié)點(diǎn)，形成3-節(jié)點(diǎn)
添加到3-節(jié)點(diǎn)，暫時形成4-節(jié)點(diǎn)，再分裂
新添加的節(jié)點(diǎn)首先應(yīng)該是紅節(jié)點(diǎn)(2-3中先融合進(jìn)節(jié)點(diǎn))，后續(xù)再調(diào)整
保持根節(jié)點(diǎn)為黑色的
// 向紅黑樹中添加新的元素(key, value)
public void add(K key, V value){
root = add(root, key, value);
root.color = BLACK; // 最終根節(jié)點(diǎn)為黑色節(jié)點(diǎn)
}
3.2.1 左旋
文章來源：http://www.zghlxwxcb.cn/news/detail-416138.html
// node x
// / \ 左旋轉(zhuǎn) / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
private Node leftRotate(Node node){
Node x = node.right;
// 左旋轉(zhuǎn)
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
// 向以node為根的紅黑樹中插入元素(key, value)，遞歸算法
// 返回插入新節(jié)點(diǎn)后紅黑樹的根
private Node add(Node node, K key, V value){
if(node == null){
size ++;
return new Node(key, value); // 默認(rèn)插入紅色節(jié)點(diǎn)
}
if(key.compareTo(node.key) < 0)
node.left = add(node.left, key, value);
else if(key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else // key.compareTo(node.key) == 0
node.value = value;
return node;
}
…文章來源地址http://www.zghlxwxcb.cn/news/detail-416138.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)入門-11-紅黑樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
