歷史上最負盛名的樹，紅黑樹(是二分搜索樹)
紅黑樹與2-3樹的等價性
學習2-3樹秕衙，不僅對于理解紅黑樹有幫助蠢甲，對于理解B類樹，也是大有幫助的据忘！
2-3樹的絕對平衡性
滿足二分搜索樹的基本性質
2-3樹特性：
- 新添加節(jié)點永遠不會講節(jié)點添加到一個空的位置
2-3樹絕對平衡的原理如下情況分析(4種情況)
- 插入2節(jié)點
- 插入3節(jié)點
- 插入3節(jié)點鹦牛，父節(jié)點為2節(jié)點
- 插入3節(jié)點，父節(jié)點為3節(jié)點
$$$$$作業(yè)：實現(xiàn)一個2-3樹勇吊！$$$$$$$$
紅黑樹與2-3樹的等價性
紅色的節(jié)點左傾斜是人為定義的
紅黑樹的基本性質和復雜性分析
由于紅黑樹和2-3樹是等價的曼追，所以能夠很直觀的確定紅黑樹的特點！
基本性質：
紅節(jié)點一定屬于一個黑節(jié)點的左孩子,2-3中對應的3節(jié)點對應紅黑樹中的黑節(jié)點和黑節(jié)點左下角的紅節(jié)點
每個節(jié)點或者是紅色的汉规，或者是黑色的礼殊。
根節(jié)點是一定是黑色的,2-3樹中，當根節(jié)點是二節(jié)點的時候明顯對應為黑色针史，當跟節(jié)點是三節(jié)點的時候晶伦，紅黑樹中對應的紅節(jié)點就跑到坐下角了。
每一個葉子節(jié)點(指最后的空節(jié)點啄枕，并不指左右節(jié)點都為空的那個節(jié)點)是黑色的相當于定義了空節(jié)點本身就是一個黑色的節(jié)點
-
如果一個節(jié)點是紅色的婚陪，那么他的孩子節(jié)點都是黑色的2-3樹中，紅色節(jié)點對應的部分就是3節(jié)點频祝，如果3節(jié)點的孩子是一個二節(jié)點泌参，那當然沒話說，是一個黑色節(jié)點常空，如果3節(jié)點的下面也是一個三節(jié)點及舍，對應到紅黑樹中，就變成了一個黑節(jié)點以及黑節(jié)點左孩子紅節(jié)點窟绷！
注意：這個結論對于黑節(jié)點不成立，黑節(jié)點的右孩子一定是黑色的咐柜，但是左孩子可能為黑兼蜈，可能為紅攘残！
(核心)從任意一個節(jié)點到葉子結點，經過的黑色節(jié)點個數(shù)是一樣的在2-3樹中为狸，保持著絕對的平衡性歼郭，說明這是一顆滿二叉樹，所有葉子節(jié)點的深度都是一樣的辐棒，對應到紅黑樹中病曾，也就對應著所有的黑節(jié)點。
紅黑樹是保持“黑平衡”的二叉樹漾根，嚴格意義上講泰涂，不是平衡二叉樹,最大高度為 2logn -- 高度的復雜度為O(logn)
紅黑樹的查詢操作比AVL樹稍微要慢一些，但是添加和刪除要優(yōu)于AVL樹
保持根節(jié)點為黑色和左旋轉
紅黑樹添加新元素(紅節(jié)點是參與融合的節(jié)點)
以 2-3樹添加元素的過程來理解紅黑樹,如果添加進2-節(jié)點辐怕，形成一個3-節(jié)點,如果添加進3-及誒單逼蒙，咱叔形成一個4-節(jié)點，再進行變形處理
在2-3樹中寄疏，添加一個節(jié)點首先不能添加到一個空的位置是牢，而是與已經有的節(jié)點進行融合，那么陕截，對應到紅黑樹中添加一個新的節(jié)點永遠的都是紅色的節(jié)點驳棱！
2-3的融合過程永遠對應的紅節(jié)點
- 要保持最終的根節(jié)點為黑色，顏色翻轉和左旋轉
leftRotate
添加的節(jié)點為42紅农曲，翻轉之后相當于添加的節(jié)點37紅
- 向紅黑樹中的3節(jié)點添加元素
- 添加的節(jié)點在父節(jié)點的右子樹上
flipColors
- 添加的節(jié)點在父節(jié)點的右子樹上
添加的節(jié)點66紅社搅，然后進行顏色翻轉，讓父節(jié)點去融合
- 添加的節(jié)點在父節(jié)點的左子樹上 右旋轉 朋蔫，父節(jié)點的顏色的保持原來父節(jié)點的顏色
翻轉后罚渐，右子節(jié)點相當于新添加的紅節(jié)點
添加元素情況總結
紅黑樹代碼的實現(xiàn)
import java.util.ArrayList;
import java.util.concurrent.BlockingDeque;
public class RBTree<K extends Comparable<K>, V> {
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;
this.left = null;
this.right = null;
this.color = RED;
}
}
private Node root;
private int size;
public RBTree(){
root = null;
size = 0;
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
// 判斷節(jié)點node的顏色
private boolean isRed(Node node){
if(node == null) // 當跟節(jié)點為空的時候，默認為黑節(jié)點
return BLACK;
return node.color;
}
/**左旋轉
* node x
* / \ 左旋轉 / \
* t1 x ---------> node t3
* / \ / \
* t2 t3 t1 t2
* */
private Node leftRotate(Node node) {
Node x = node.right;
Node t2 = x.right;
// 左旋轉
x.left = node;
node.right = t2;
x.color = node.color; // x等于原來樹的根節(jié)點
// 2-3樹中驯妄，添加節(jié)點都是紅節(jié)點荷并，旋轉交換之后，也必須
// 保證這個特性青扔。所以要把node變?yōu)榧t色源织！(以2-3樹舉個例子：
// 一顆樹先只有根節(jié)點為黑2，現(xiàn)在添加節(jié)點紅4微猖，對應到紅黑樹谈息，
// 根節(jié)點就要變成黑4,左子樹就要變成紅2！)
node.color = RED;
return x;
}
/**右旋轉
* node x
* / \ 右旋轉 / \
* x t2 -------> y node
* / \ / \
* y t1 t1 t2
* */
private Node rightRotate(Node node) {
Node x = node.left;
// 右旋轉
node.left = x.right;
x.right = node;
// 維護顏色
x.color = node.color;
node.color = RED;
return x;
}
// 顏色翻轉凛剥，向3節(jié)點添加一個節(jié)點(節(jié)點對應的位置在右子樹侠仇，
// 子節(jié)點變黑，父節(jié)點變紅和上層進行融合)
private void flipColors(Node node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
// 向紅黑樹中添加新的元素(key, value)
public void add(K key, V value){
root = add(root, key, value);
root.color = BLACK; // 保持最終的根節(jié)點為黑色
}
// 向以node為根的紅黑樹中插入元素(key, value)，遞歸算法
// 返回插入新節(jié)點后紅黑樹的根
private Node add(Node node, K key, V value){
if(node == null){
size ++;
return new Node(key, value);
}
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;
// 維護紅黑樹Ｂ叽丁；チ痢！余素！
// 左旋轉(對應兩種情況豹休！)
if(isRed(node.right) && !isRed(node.left))
node = this.leftRotate(node.left);
// 右旋轉
if(isRed(node.left) && isRed(node.left.left))
node = this.rightRotate(node.left);
// 顏色翻轉
if(isRed(node.left) && isRed(node.right))
this.flipColors(node);
return node;
}
// 返回以node為根節(jié)點的二分搜索樹中，key所在的節(jié)點
private Node getNode(Node node, K key){
if(node == null)
return null;
if(key.equals(node.key))
return node;
else if(key.compareTo(node.key) < 0)
return getNode(node.left, key);
else // if(key.compareTo(node.key) > 0)
return getNode(node.right, key);
}
public boolean contains(K key){
return getNode(root, key) != null;
}
public V get(K key){
Node node = getNode(root, key);
return node == null ? null : node.value;
}
public void set(K key, V newValue){
Node node = getNode(root, key);
if(node == null)
throw new IllegalArgumentException(key + " doesn't exist!");
node.value = newValue;
}
// 返回以node為根的二分搜索樹的最小值所在的節(jié)點
private Node minimum(Node node){
if(node.left == null)
return node;
return minimum(node.left);
}
// 刪除掉以node為根的二分搜索樹中的最小節(jié)點
// 返回刪除節(jié)點后新的二分搜索樹的根
private Node removeMin(Node node){
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
// 從二分搜索樹中刪除鍵為key的節(jié)點
public V remove(K key){
Node node = getNode(root, key);
if(node != null){
root = remove(root, key);
return node.value;
}
return null;
}
private Node remove(Node node, K key){
if( node == null )
return null;
if( key.compareTo(node.key) < 0 ){
node.left = remove(node.left , key);
return node;
}
else if(key.compareTo(node.key) > 0 ){
node.right = remove(node.right, key);
return node;
}
else{ // key.compareTo(node.key) == 0
// 待刪除節(jié)點左子樹為空的情況
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
// 待刪除節(jié)點右子樹為空的情況
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}
// 待刪除節(jié)點左右子樹均不為空的情況
// 找到比待刪除節(jié)點大的最小節(jié)點, 即待刪除節(jié)點右子樹的最小節(jié)點
// 用這個節(jié)點頂替待刪除節(jié)點的位置
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
public static void main(String[] args){
System.out.println("Pride and Prejudice");
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile("pride-and-prejudice.txt", words)) {
System.out.println("Total words: " + words.size());
RBTree<String, Integer> map = new RBTree<>();
for (String word : words) {
if (map.contains(word))
map.set(word, map.get(word) + 1);
else
map.add(word, 1);
}
System.out.println("Total different words: " + map.getSize());
System.out.println("Frequency of PRIDE: " + map.get("pride"));
System.out.println("Frequency of PREJUDICE: " + map.get("prejudice"));
}
System.out.println();
}
}
紅黑樹更多的相關內容
紅黑樹中刪除節(jié)點：過程特別復雜桨吊！連紅黑樹的發(fā)明人Robert Sedgewick 在其經典著作《算法4》中都沒有詳細介紹具體的實現(xiàn)邏輯威根；以后有時間可以好好研究研究！
-
紅黑樹的傾斜
- 左傾紅黑樹：紅節(jié)點在左子樹视乐，標準紅黑樹
- 右傾紅黑樹：紅節(jié)點在右子樹洛搀。
- 同時存在左傾和右傾：與2-4樹等價，任何不平衡在三系旋轉內解決
紅黑樹是一種統(tǒng)計性能優(yōu)秀的樹炊林，另一種統(tǒng)計性優(yōu)秀的樹結構：Splay Tree(伸展樹局部性原理：剛被訪問的內容下次高概率被再次訪問姥卢。)：
Java中的treeMap、treeSet這些有序的映射集合底層用的紅黑樹
紅黑樹的其他實現(xiàn)方式有很多渣聚，也有很多可以優(yōu)化的地方,推薦看看《算法導論》中的紅黑樹的實現(xiàn)（添加和刪除独榴，用2-4樹去理解！）
紅黑樹與其他樹的性能總結：
對于完全隨機的數(shù)據(jù)奕枝，普通的二分搜索樹很好用棺榔！，缺點極端情況下回退化成鏈表（高度不平衡）
對于查詢較多的使用情況隘道，AVL樹很好用
紅黑樹犧牲了平衡性（2logn大高度）症歇，統(tǒng)計性更優(yōu)（綜合增刪改查所有的操作）
