2-3樹
2-3樹
- 滿足二分搜索樹的基本性質(zhì)
- 節(jié)點(diǎn)可以存放一個元素或者兩個元素
- 每個節(jié)點(diǎn)可以有2個孩子(二節(jié)點(diǎn)) 或者3個孩子(三節(jié)點(diǎn))
- 絕對平衡的樹(從根節(jié)點(diǎn)到任意一個葉子節(jié)點(diǎn)所通過的節(jié)點(diǎn)數(shù)量一定是相同的)
2-3樹保持平衡
添加節(jié)點(diǎn)永遠(yuǎn)不會去空的節(jié)點(diǎn)颜矿，會和最后找到的葉子節(jié)點(diǎn)做融合搬瑰。
添加12
添加2
添加4
添加4
紅黑樹
等價于2-3樹
- 保持黑平衡的二叉樹莺丑，左右子樹的黑色節(jié)點(diǎn)的高度差保持絕對平衡猜揪，2-3樹本身是保持絕對平衡的
- 每個節(jié)點(diǎn)或者是紅色的闪幽，后者是黑色的
- 根節(jié)點(diǎn)是黑色的
- 每一個葉子節(jié)點(diǎn)(最后的空節(jié)點(diǎn))是黑色的
- 如果一個節(jié)點(diǎn)是紅色贱枣，它的孩子節(jié)點(diǎn)都是黑色月洛，黑色節(jié)點(diǎn)的右孩子一定是黑色的
- 從任意一個節(jié)點(diǎn)出發(fā)到葉子節(jié)點(diǎn)藏研，經(jīng)過的黑色節(jié)點(diǎn)是一樣的
- 所有的紅色節(jié)點(diǎn)向左傾斜
- 最大高度：2logn
紅黑樹與2-3樹
//紅黑樹基于二分搜索樹
public class RedBlackTree <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;
left = null;
right = null;
color = RED;//因?yàn)樵?-3樹中添加的節(jié)點(diǎn)永遠(yuǎn)都是要融合到已有的節(jié)點(diǎn)中
}
}
private Node root;
private int size;
public RedBlackTree(){
root = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
//判斷node顏色
private boolean isRed(Node node) {
if (node == null)
return Black;
return node.color;
}
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;
}
}
添加元素相關(guān)操作
- 左旋轉(zhuǎn)，當(dāng)添加的元素大于節(jié)點(diǎn)時咐汞，進(jìn)行左旋轉(zhuǎn)盖呼。(紅色節(jié)點(diǎn)需要向左傾斜)
添加42
左旋轉(zhuǎn)
左旋轉(zhuǎn)代碼
// node x
// / \ 左旋轉(zhuǎn) / \
// T1 x -----------> node T3
// / \ / \
// T2 T3 T1 T2
//左旋轉(zhuǎn)
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; //是2-3樹中的三節(jié)點(diǎn)
return x;
}
- 顏色翻轉(zhuǎn)，添加66化撕，因?yàn)?2需要繼續(xù)向上融合(向紅黑樹中的3節(jié)點(diǎn)添加元素)
添加66
顏色翻轉(zhuǎn)
顏色翻轉(zhuǎn)代碼
private void flipColors(Node node) {
node.color = RED; //由于需要繼續(xù)向上融合 所以是紅色
node.left.color = Black; // 三個二節(jié)點(diǎn) 是黑色
node.right.color = Black; // 三個二節(jié)點(diǎn) 是黑色
}
- 右旋轉(zhuǎn)几晤，需要翻轉(zhuǎn)顏色
添加12
右旋轉(zhuǎn)
顏色翻轉(zhuǎn)
右旋轉(zhuǎn)代碼
//右旋轉(zhuǎn)
// node x
// / \ 右旋轉(zhuǎn) / \
// x T2 --------------> y node
// / \ / \
// y T1 T1 T2
private Node rightRotate(Node node) {
Node x = node.left;
//右旋轉(zhuǎn)
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
-
先左旋轉(zhuǎn)在右旋轉(zhuǎn)在翻轉(zhuǎn)顏色
添加中間值元素
先左旋轉(zhuǎn)
再右旋轉(zhuǎn)
顏色翻轉(zhuǎn)
添加元素過程總結(jié)
添加元素維護(hù)邏輯
//向紅黑樹中添加元素
public void add(K key, V value) {
root = add(root, key, value);
root.color = Black; //最終的根節(jié)點(diǎn)為黑色節(jié)點(diǎn)
}
//以向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 // ==
node.value = value;
//右孩子是紅色 左孩子不是紅色的
if (isRed(node.right) && !isRed(node.left))
node = leftRotate(node);
//左孩子 以及 左孩子的左孩子都是紅色的
if (isRed(node.left) && isRed(node.left.left))
node = rightRotate(node);
//左孩子 與 右孩子 都是紅色的
if (isRed(node.left) && isRed(node.right))
flipColors(node);
return node;
}
性能總結(jié)
對于完全隨機(jī)的數(shù)據(jù)，普通的二分搜索樹很好用
缺點(diǎn)：極端情況下退化成鏈表(或者高度不平衡)
對于查詢較多的使用情況植阴，AVL樹很好用
紅黑樹犧牲了平衡性(2logn的高度)
紅黑樹統(tǒng)計性能更優(yōu)(綜合增刪改查所有的操作)蟹瘾，平均性能優(yōu)于AVL樹。
數(shù)據(jù)結(jié)構(gòu)中經(jīng)常發(fā)生添加掠手，刪除的情況時憾朴，紅黑樹更合適。查詢并不占優(yōu)勢喷鸽。
如果數(shù)據(jù)近乎不會動的話众雷，只查詢，AVL樹性能更好做祝。
