上篇文章詳細的給大家介紹了2-3-4樹,本文就詳細的介紹下紅黑樹的内容
紅黑樹
紅黑樹,Red-Black Tree 「RBT」是一個自平衡(不是絕對的平衡)的二叉查找樹(BST),樹上的每個節點都遵循下面的規則:
- 每個節點要麼是黑色,要麼是紅色。
- 根節點是黑色。
- 每個葉子節點(NIL)是黑色。
- 每個紅色結點的兩個子結點一定都是黑色。
- 任意一結點到每個葉子結點的路徑都包含數量相同的黑結點。
紅黑樹能自平衡,它靠的是什麼?三種操作:左旋、右旋和變色
操作 | 描述 |
左旋 | 以某個結點作為支點(旋轉結點),其右子結點變為旋轉結點的父結點, 右子結點的左子結點變為旋轉結點的右子結點,左子結點保持不變。 |
右旋 | 以某個結點作為支點(旋轉結點),其左子結點變為旋轉結點的父結點, 左子結點的右子結點變為旋轉結點的左子結點,右子結點保持不變。 |
變色 | 結點的顔色由紅變黑或由黑變紅。 |
1 旋轉操作
1.1 概念講解
左旋:以某個節點作為旋轉點,其右子節點變為旋轉節點的父節點,右子節點的左子節點變為旋轉節點的右子節點,左子節點保持不變。
右旋:以某!個節點作為旋轉點,其左子節點變為旋轉節點的父節點,左子節點的右子節點變為旋轉節點的左子節點,右子節點保持不變。
1.2 代碼實作
先進行類結構定義
package com.bobo.util.treemap;
public class BRTree {
private static final boolean RED = false;
private static final boolean BLACK = true;
private RBNode root;
public RBNode getRoot() {
return root;
}
public void setRoot(RBNode root) {
this.root = root;
}
/**
* 表示 節點
* @param <K>
* @param <V>
*/
static class RBNode<K extends Comparable<K>,V>{
// 節點是雙向的
private RBNode parent;
private RBNode left;
private RBNode right;
private boolean color;
private K key;
private V value;
public RBNode() {
}
public RBNode(RBNode parent, RBNode left, RBNode right, boolean color, K key, V value) {
this.parent = parent;
this.left = left;
this.right = right;
this.color = color;
this.key = key;
this.value = value;
}
public RBNode getParent() {
return parent;
}
public void setParent(RBNode parent) {
this.parent = parent;
}
public RBNode getLeft() {
return left;
}
public void setLeft(RBNode left) {
this.left = left;
}
public RBNode getRight() {
return right;
}
public void setRight(RBNode right) {
this.right = right;
}
public boolean isColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
}
左旋代碼實作
/**
* 圍繞p左旋
* p pr(r)
* / | / \
* pl pr(r) => p rr
* / \ / \
* rl rr pl rl
*
* 左旋的時候
* p-pl 和 pr-rr的關系不變
* pr-rl 要變為 p-rl
* 也就是 rl要變為 p的右子節點
* 同時 p要成為 rl 的父節點
* 還有就是要判斷 p 是否有父節點
* 如果沒有
* r 變為 root 節點
* 如果有
* r.parent = p.parent
* 還要設定 r為 p.parent 的子節點(可能左也可能右)
* 如果 p.parent.left == p
* p.parent.left = r;
* 否則
* p.parent.right = r;
* 最後
* p.parent = r;
* r.left = p;
* @param p
*/
private void leftRotate(RBNode p){
if(p != null){
RBNode r = p.right;
// 1.設定 pr-rl 要變為 p-rl
// 把rl設定到p的右子節點
p.right = r.left;
if(r.left != null){
// 設定rl的父節點為p
r.left.parent = p;
}
// 2.判斷p的父節點情況
r.parent = p.parent; // 不管 p是否有父節點,都把這個父節點設定為 r的父節點
if(p.parent == null){
root = r; // p沒有父節點 則r為root節點
}else if(p.parent.left == p){
p.parent.left = r; // 如果p為 p.parent的左子節點 則 r 也為 p.parent的左子節點
}else{
p.parent.right = r; // 反之設定 r 為 p.parent的右子節點
}
// 最後 設定 p 為 r 的左子節點
r.left = p;
p.parent = r;
}
}
右旋實作:
/**
* 圍繞p右旋
* @param p
*/
public void rightRotate(RBNode p){
if(p != null){
RBNode r = p.left;
p.left = r.right;
if(r.right != null){
r.right.parent = p;
}
r.parent = p.parent;
if(p.parent == null){
root = r;
}else if(p.parent.left == p){
p.parent.left = r;
}else{
p.parent.right = r;
}
r.right = p;
p.parent = r;
}
}
2 新增節點
https://www.processon.com/view/link/60c21e25e401fd34a1514d25
2-3-4樹中結點添加需要遵守以下規則:
- 插入都是向最下面一層插入
- 升元:将插入結點由 2-結點更新成 3-結點,或由 3-結點更新成 4-結點;
- 向 4-結點插入元素後,需要将中間元素提到父結點升元,原結點變成兩個 2-結點,再把元素插入2-結點中,如果父結點也是 4-結點,則遞歸向上層升元,至到根結點後将樹高加1;
而将這些規則對應到紅黑樹裡,就是:
- 新插入的結點顔色為 紅色 ,這樣才可能不會對紅黑樹的高度産生影響。
- 2-結點對應紅黑樹中的單個黑色結點,插入時直接成功(對應 2-結點升元)。
- 3-結點對應紅黑樹中的 黑+紅 子樹,插入後将其修複成 紅+黑+紅 子樹(對應 3-結點升元);
- 4-結點對應紅黑樹中的 紅+黑+紅 子樹,插入後将其修複成 紅色祖父+黑色父叔+紅色孩子 子樹,然後再把祖父結點當成新插入的紅色結點遞歸向上層修複,直至修複成功或遇到 root 結點;
公式:紅黑樹+新增一個節點(紅色)**=**對等的2-3-4樹+新增一個節點
2.1 新增節點示例
我們通過新增2-3-4樹的過程來映射對應的紅黑樹的節點新增
2-3-4樹的新增(全部在葉子節點完成)
1.新增一個節點,2 節點
2.新增一個節點,與2節點合并,直接合并
3.新增一個節點,與3節點合并,直接合并
插入的值的位置會有3種情況
對應的紅黑樹為:
4.新增一個節點,與4節點合并,此時需要分裂
插入值的位置可能是
對應的紅黑樹的結構為
2.2 新增代碼實作
紅黑樹的新增規則我們理清楚了,接下來就可以通過Java代碼來具體的實作了。
先實作插入節點,這就是一個普通的二叉樹的插入
/**
* 新增節點
* @param key
* @param value
*/
public void put(K key , V value){
RBNode t = this.root;
if(t == null){
// 說明之前沒有元素,現在插入的元素是第一個
root = new RBNode<>(key , value == null ? key : value,null);
return ;
}
int cmp ;
// 尋找插入位置
// 定義一個雙親指針
RBNode parent;
if(key == null){
throw new NullPointerException();
}
// 沿着跟節點找插入位置
do{
parent = t;
cmp = key.compareTo((K)t.key);
if(cmp < 0){
// 左側找
t = t.left;
}else if(cmp > 0){
// 右側找
t = t.right;
}else{
// 插入節點的值==比較的節點。值替換
t.setValue(value==null?key:value);
return;
}
}while (t != null);
// 找到了插入的位置 parent指向 t 的父節點 t為null
// 建立要插入的節點
RBNode<K, Object> e = new RBNode<>(key, value == null ? key : value, parent);
// 然後判斷要插入的位置 是 parent的 左側還是右側
if(cmp < 0){
parent.left = e;
}else{
parent.right = e;
}
// 調整 變色 旋轉
fixAfterPut(e);
}
然後再根據紅黑樹的特點來實作調整(旋轉,變色)
private boolean colorOf(RBNode node){
return node == null ? BLACK:node.color;
}
private RBNode parentOf(RBNode node){
return node != null ? node.parent:null;
}
private RBNode leftOf(RBNode node){
return node != null ? node.left:null;
}
private RBNode rightOf(RBNode node){
return node != null ? node.right:null;
}
private void setColor(RBNode node ,boolean color){
if(node != null){
node.setColor(color);
}
}
/**
* 插入節點後的調整處理
* 1. 2-3-4樹 新增元素 2節點添加一個元素将變為3節點 直接合并,節點中有兩個元素
* 紅黑樹:新增一個紅色節點,這個紅色節點會添加在黑色節點下(2節點) --- 這種情況不需要調整
* 2. 2-3-4樹 新增元素 3節點添加一個元素變為4節點合并 節點中有3個元素
* 這裡有6中情況,( 根左左 根左右 根右右 根右左)這四種要調整 (左中右的兩種)不需要調整
* 紅黑樹:新增紅色節點 會添加到 上黑下紅的節點中 = 排序後中間節點是黑色,兩邊節點是紅色
*
* 3. 2-3-4樹:新增一個元素 4節點添加一個元素需要裂變:中間元素更新為父節點,新增元素與剩下的其中一個合并
* 紅黑樹:新增節點是紅色+爺爺節點是黑色,父親節點和叔叔節點為紅色 調整為
* 爺爺節點變紅色,父親和叔叔節點變為黑色,如果爺爺節點為root節點則調整為黑色
* @param x
*/
private void fixAfterPut(RBNode<K, Object> x) {
x.color = RED;
// 本質上就是父節點是黑色的就不需要調整,對應的 2 3的情況
while(x != null && x != root && x.parent.color == RED){
// 1. x 的父節點是爺爺的 左孩子
if(parentOf(x) == parentOf(parentOf(x)).left){
// 擷取目前節點的叔叔節點
RBNode y = rightOf(parentOf(parentOf(x)));
// 情況3
if(colorOf(y) == RED){
// 說明是 上3的情況 變色處理
// 父親節點和叔叔節點設定為黑色
setColor(parentOf(x),BLACK);
setColor(y,BLACK);
// 爺爺節點設定為 紅色
setColor(parentOf(parentOf(x)),RED);
// 遞歸處理
x = parentOf(parentOf(x));
}else{
// 情況 2
if(x == parentOf(x).right){
// 如果x是父節點的右節點那麼我們需要先根據 父節點 左旋
x = parentOf(x);
leftRotate(x);
}
// 叔叔節點為空 對應于 上面的情況2
// 将父節點變為黑色
setColor(parentOf(x),BLACK);
// 将爺爺節點變為紅色
setColor(parentOf(parentOf(x)),RED);
// 右旋轉 根據爺爺節點右旋轉
rightRotate(parentOf(parentOf(x)));
}
}else{
// x 的父節點是爺爺是右孩子
// 擷取父親的叔叔節點
RBNode y = leftOf(parentOf(parentOf(x)));
if(colorOf(y) == RED){
// 情況3
setColor(parentOf(x),BLACK);
setColor(y,BLACK);
setColor(parentOf(parentOf(x)),RED);
x = parentOf(parentOf(x));
}else{
// 情況2
if( x == parentOf(x).left){
x = parentOf(x);
rightRotate(x);
}
setColor(parentOf(x),BLACK);
setColor(parentOf(parentOf(x)),RED);
leftRotate(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
2.3 插入節點
不通過2-3-4樹來實作添加節點的分析,看大家是否能了解哦
插入的場景
插入場景1:紅黑樹為空樹
最簡單的一種情景,直接把插入結點作為根結點就行,但注意,根據紅黑樹性質2:根節點是黑色。還需要把插入結點設為黑色。
處理:把插入結點作為根結點,并把結點設定為黑色。
插入場景2:插入結點的父結點為黑結點
由于插入的結點是紅色的,且父節點為黑色節點,并不會影響紅黑樹的平衡,直接插入即可,無需做自平衡。
處理:直接插入。
插入場景3:插入結點的父結點為紅結點
再次回想下紅黑樹的性質2:根結點是黑色。如果插入的父結點為紅結點,那麼該父結點不可能為根結點,是以插入結點總是存在祖父結點。這點很重要,因為後續的旋轉操作肯定需要祖父結點的參與。
插入場景3.1:叔叔結點存在并且為紅結點
從紅黑樹性質4可以,祖父結點肯定為黑結點,因為不可以同時存在兩個相連的紅結點。那麼此時該插入子樹的紅黑層數的情況是:黑紅紅。顯然最簡單的處理方式是把其改為:紅黑紅。
實際案例:
祖父節點為根節點:紅黑黑
祖父節點不為根節點:
插入場景3.2**:叔叔結點不存在或為黑結點,并且插入結點的父親結點是祖父結點的左子結點
單純從插入前來看,也即不算情景3.1自底向上處理時的情況,叔叔結點非紅即為葉子結點(Nil)。因為如果叔叔結點為黑結點,而父結點為紅結點,那麼叔叔結點所在的子樹的黑色結點就比父結點所在子樹的多了,這不滿足紅黑樹的性質5。後續情景同樣如此,不再多做說明了。
前文說了,需要旋轉操作時,肯定一邊子樹的結點多了或少了,需要租或借給另一邊。插入顯然是多的情況,那麼把多的結點租給另一邊子樹就可以了。
插入場景3.2.1:插入結點是其父結點的左子結點
插入場景3.2.2:叔叔結點不存在或為黑結點,并且插入結點的父親結點是祖父結點的右子結點