目錄
- 紅黑樹
- 1. 2-3-4樹
- 2.紅黑樹實作
- 2.1.概述
- 2.2.右旋
- 2.3.左旋
- 2.4.插入
- 2.5.洗掉
- 3.總代碼
紅黑樹
要想真正的學會紅黑樹，不應該是無腦背判斷啊條件什么的，而是應該沿著紅黑樹的前身2-3-4樹來真正學會這種資料結構，當然我也只是認為加上2-3-4樹可以對紅黑樹的理解，不喜勿噴(●ˇ?ˇ●)
1. 2-3-4樹
2-3-4樹是四階的 B樹(Balance Tree)，他屬于一種多路查找樹，2-3-4樹是對完美平衡二叉樹的擴展，它的結構有以下限制：
- 所有葉子節點都擁有相同的深度，
- 節點只能是 2-節點、3-節點、4-節點之一，
- 2-節點：包含 1 個元素的節點，有 2 個子節點；
- 3-節點：包含 2 個元素的節點，有 3 個子節點；
- 4-節點：包含 3 個元素的節點，有 4 個子節點；
- 所有節點必須至少包含1個元素，元素始終保持排序順序，整體上保持二叉查找樹的性質，即父結點大于左子結點，小于右子結點； 而且結點有多個元素時，每個元素必須大于它左邊的和它的左子樹中元素，
2-3-4樹的查詢操作像普通的二叉搜索樹一樣，非常簡單，但由于其結點元素數不確定，在一些編程語言中實作起來并不方便，所以一般使用它的等同——紅黑樹
2-3-4樹可以說是一種規范，一種標準，而紅黑樹就是實作了2-3-4樹這個模型，所以紅黑樹的操作都可以追溯到2-3-4樹上
2-3-4樹的插入
對應關系
每個紅黑樹都會對應一個2-3-4樹，而一個2-3-4樹會對應多個紅黑樹，就是因為3結點有兩種表現形式
每一個紅色結點都是和上面的黑色結點是一起的，只有黑色結點在2-3-4樹中才會貢獻層數，紅色結點只是掛在黑色結點上，所以在實作了2-3-4樹模型的紅黑樹中，也是只需要黑色平衡就可以了
紅黑樹和 2-3-4樹的結點添加和洗掉都有一個基本規則：避免子樹高度變化，因為無論是 2-3-4樹還是紅 黑樹，一旦子樹高度有變動，勢必會影響其他子樹進行調整，所以我們在插入和洗掉結點時盡量通過子 樹內部調整來達到平衡，2-3-4樹實作平衡是通過結點元素數變化，紅黑樹是通過結點旋轉和變色，
2.紅黑樹實作
2.1.概述
紅黑樹是一種結點帶有顏色屬性的二叉查找樹，但它在二叉查找樹之外，還有以下5大性質：
- 節點是紅色或黑色， （2-3-4樹中三種結點對應紅黑樹都是紅色加黑色的形式）
- 根是黑色， （2結點是黑色，3結點和4結點都可以通過旋轉保持上黑下紅的形式）
- 所有葉子都是黑色（葉子是NIL節點）， （感覺這一條是為了迎合性質四的，反正我是沒咋看懂，，，）
- 每個紅色節點必須有兩個黑色的子節點，（從每個葉子到根的所有路徑上不能有兩個連續的紅色節 點，） （2-3-4樹模型中紅色和黑色是一個結點，每一個紅色結點都是掛在黑色結點上的，4結點的兩個紅色分配在左右，也不可能有兩個紅色結點出現）
- 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點（黑色平衡），（2-3-4樹葉子結點都在同一層中，每個結點都只有一個黑色結點，所有對應紅黑樹就是黑色結點才會貢獻層數，也就是黑色平衡）
紅黑樹的實作情況比較多，建議畫圖來實作代碼，防止混淆加忘記，我在最后加了我寫的可以直接運行的代碼，所以篇幅比較大，不想看的可以直接拿代碼跑一跑(●ˇ?ˇ●)，
2.2.右旋
以某個節點作為旋轉點，其左子節點變為旋轉節點的父節點，左子節點的右子節點變為旋轉節點 的左子節點，右子節點保持不變，
代碼實作
/**
* 右旋
* gn gn
* / /
* n rn
* / \ / \
* rn ln --> rr n
* / \ / \
* rr rl rl ln
*/
private void rightRotate(RBNode n){
if (n != null){
// 獲取左孩子
RBNode rn = n.left;
// 1、將rl放到n的左孩子上
// rn.right為null不影響賦值
n.left = rn.right;
if (rn.right != null){
rn.right.parent = n;
}
// 2、將rn放的n的位置
rn.parent = n.parent;
// 如果父節點為空，就將rn指向根節點
if (n.parent == null){
this.root = rn;
}
// 判斷rn該插入到父節點的左右哪個孩子結點
else if (n == n.parent.left){
n.parent.left = rn;
}else {
n.parent.right = rn;
}
// 3、將換好位置的rn與n互相系結
rn.right = n;
n.parent = rn;
}
}
2.3.左旋
以某個節點作為旋轉點，其右子節點變為旋轉節點的父節點，右子節點的左子節點變為旋轉節點 的右子節點，左子節點保持不變，
/**
* 左旋就是將右旋反過來
* @param n
*/
private void leftRotate(RBNode n){
if (n != null){
RBNode rl = n.right;
n.right = rl.left;
if (rl.left != null){
rl.left.parent = n;
}
rl.parent = n.parent;
if (n.parent == null){
this.root = rl;
} else if (n == n.parent.left){
n.parent.left = rl;
}else {
n.parent.right = rl;
}
rl.left = n;
n.parent = rl;
}
}
2.4.插入
2-3-4樹的新增一定是在葉子結點上的，那么實作了2-3-4樹的紅黑樹，插入也一定是在葉子結點上的，所有也就只有四種情況（按照2-3-4樹進行分的情況，然后轉化為對應的紅黑樹情況）：
- 沒有結點，插入第一個結點為根節點
- 插入與二節點結合成一個三節點
- 插入與三節點結合成一個四節點
- 插入與四結點結合，四節點往上分裂
情況一
情況二
情況三
情況四
代碼實作
插入一定會插入在二叉樹的葉子結點上，所以需要先遍歷要插入結點的父節點，然后將結點插入上去，最后才是紅黑樹的調整，
步驟：
-
判斷根節點是否存在
-
查詢插入結點的父節點
-
將新插入結點與父節點關聯
-
紅黑樹平衡調整
-
2-3-4樹：插入第一個結點，將當前結點設為根節點，
紅黑樹：將插入結點變成黑色，新創建的結點默認就是黑色，所有也不需要調整
-
2-3-4樹：插入一個結點與2結點結合，變成一個三節點
紅黑樹：插入到黑色結點下面，不需要調整
-
2-3-4樹：插入一個結點與3結點結合，變成一個四節點
紅黑樹：這里有四種情況（左三，右三，左中右，右中左），這里只有左三和右三需要調整，也就是父節點為紅色，爺爺結點為黑色，左中右和右中左都是父節點是黑色結點不需要調整
新增結點+上黑下紅 --> 旋轉變色 --> 中間結點為黑色，左右兩個結點為紅色（爺爺結點下來變紅，父親結點上去變黑）
-
2-3-4樹：插入一個結點與4結點結合，4結點分裂，中間結點上去待合并，新增結點與左右兩個2結點結合
紅黑樹：父節點和叔叔結點是紅色，爺爺結點是黑色（判斷條件是叔叔結點是紅色） --> 變色 --> 父親和叔叔變黑，爺爺變紅，以爺爺結點繼續往上遞回進行判斷
-
public void put(K key,V value){
RBNode node = this.root;
// 1、判斷根節點是否存在
if (node == null){
// 如果不存在，則直接將當前結點設定為根節點，新創建結點默認是黑色
root = new RBNode<K, V>(null, key, value =https://www.cnblogs.com/MuggleP/p/= null? (V) key :value);
return;
}
// 2、查找插入結點的父節點
RBNode parent = node;
int cmp;
if (key == null){
throw new NullPointerException();
}
do {
parent = node;
// 如果key值大于父節點，往右子樹進行尋找
// 如果key值小于父節點，往左子樹進行尋找
// 如果key值命中，直接替換值然后回傳
cmp = key.compareTo(parent.key);
if (cmp > 0){
node = node.right;
}else if (cmp < 0){
node = node.left;
}else {
node.value = value;
return;
}
}while (node != null);
node = new RBNode(parent, key, value == null? (V) key :value);
// 3、將新插入結點與父節點關聯
node.parent = parent;
if (cmp > 0){
parent.right = node;
}else {
parent.left = node;
}
// 上面三步插入是二叉樹與紅黑樹通用的插入方法，下面調整才是紅黑樹平衡的重點
// 插入完之后，調整
fixAfterPut(node);
}
private void fixAfterPut(RBNode node){
// 插入結點都為紅色
setColor(node,RED);
// 只有3、4情況才需要調整，這里的回圈是遞回操作情況4，并且插入的父節點都是紅色
while (node != null && node != this.root && parentOf(node).color == RED){
// 插入結點在左邊,也就是叔叔結點在右邊
if (parentOf(node) == parentOf(parentOf(node)).left){
// 獲取爺爺結點和叔叔結點
RBNode gParent = parentOf(parentOf(node));
RBNode uncle = rightOf(gParent);
// 情況4
if (colorOf(uncle) == RED){
setColor(parentOf(node),BLACK);
setColor(uncle,BLACK);
setColor(gParent,RED);
// 在當前子樹進行調整完之后，以爺爺結點為當前結點，繼續遞回往上進行調整
// 如果遞回到根節點就退出，然后將根節點染色，層數加一
// 如果遞回到當前結點的父節點為黑色，那么調整成功，直接退出回圈
node = gParent;
}else { // 情況3
// 這是情況3的一種特殊情況，插入到父節點的右孩子
// 需要進行一次左旋，就調整成正宗的左3
if (node == rightOf(parentOf(node))){
// 這是將父節點為當前結點，因為左旋后父節點會下來到子節點的位置
// 如果不這樣那左旋之后當前結點就會變成原來的父節點
node = parentOf(node);
leftOf(node);
}
setColor(parentOf(node),BLACK);
setColor(gParent,RED);
rightRotate(gParent);
}
}else { // 插入結點在右邊
RBNode gParent = parentOf(parentOf(node));
RBNode uncle = leftOf(gParent);
// 情況4
if (colorOf(uncle) == RED){
setColor(parentOf(node),BLACK);
setColor(uncle,BLACK);
setColor(gParent,RED);
node = gParent;
}else { // 情況3
if (node == leftOf(parentOf(node))){
node = parentOf(node);
rightOf(node);
}
setColor(parentOf(node),BLACK);
setColor(gParent,RED);
leftRotate(gParent);
}
}
}
// 情況4，如果遞回到根節點，就把樹的層數加一
setColor(this.root,BLACK);
}
2.5.洗掉
紅黑樹的洗掉與二叉樹的洗掉很相似，就是多了一步調整的步驟，所有先來研究二叉樹的洗掉，然后再擴展到紅黑樹的洗掉，當然2-3-4樹也類似，在這里用二叉樹是比較方便，也可以自己想想2-3-4樹的洗掉操作，
二叉樹
洗掉操作的情況只有三種：
- 洗掉結點是葉子結點，那么直接洗掉
- 洗掉結點有一個子節點，那么用子節點來替代洗掉結點
- 洗掉結點有兩個子節點，直接洗掉情況太復雜，可以找到待洗掉結點的前驅結點和后繼結點來替代洗掉
- 找到前驅結點或后繼結點后，復制前驅結點或后繼結點的值，覆寫掉待洗掉結點的值，然后洗掉前驅結點或后繼結點，也就是說洗掉該節點不是真正的洗掉，而是拿前驅或后繼結點的值來覆寫，
- 將洗掉有兩個孩子的情況轉化為洗掉只有一個孩子或沒有孩子的情況，也就是將復雜的情況3轉化為較簡單的情況1和2，復雜的問題簡單化，
找前驅和后繼代碼
/**
* 找前驅結點
* 方法：找該節點的左子樹，找到后從左子樹的右孩子一直往下找
*/
private RBNode<K,V> predecessor(RBNode<K,V> node){
if (node == null){
return null;
}
// 如果有左孩子，那么就從左孩子的右孩子一直往下找
else if (leftOf(node) != null){
RBNode<K,V> lNode = leftOf(node);
// 如果右孩子為空，那么就說明找到了，直接退出回傳
while (rightOf(lNode) !=null){
lNode = rightOf(lNode);
}
return lNode;
}else {
// 在洗掉操作中是不會出現這種情況的，這種情況一般是葉子結點或者只有一個孩子的情況來找前驅
// 在洗掉操作中如果是這種情況就直接洗掉了，不用廢這力氣
// 這里是找前驅結點的情況，所有把這種情況也一塊寫下來了
// 獲取父節點
RBNode<K, V> parent = parentOf(node);
// 獲取自己
RBNode<K,V> child = node;
// 判斷當前結點是否是父節點的左結點，如果是就說明找到了，退出回傳
// 如果父節點為空，也就是找到根節點還沒有找到，那么說明當前結點沒有前驅結點，回傳null
while (parent!=null&&child==leftOf(parent)){
child = parent;
parent = parentOf(parent);
}
// 當然如果沒有前驅結點也可以回傳自己，作為自己的前驅結點，我的選擇的回傳了null
// if (parent == null){
// return node;
// }
return parent;
}
}
/**
* 找后繼結點
* 與找前驅相反
* @param node
* @return
*/
private RBNode<K,V> successor(RBNode<K,V> node){
if (node == null){
return null;
}
else if (rightOf(node) != null){
RBNode<K,V> rNode = rightOf(node);
while (leftOf(rNode) !=null){
rNode = leftOf(rNode);
}
return rNode;
}else {
RBNode<K, V> parent = parentOf(node);
RBNode<K,V> child = node;
while (parent!=null&&child==rightOf(parent)){
child = parent;
parent = parentOf(parent);
}
// if (parent == null){
// return node;
// }
return parent;
}
}
洗掉結點
// 按照key找到該節點
private RBNode<K,V> getNode(K key) {
RBNode<K,V> node = this.root;
// 從根節點開始遍歷，如果大于往右走，小于往左走，等于則回傳
// 出回圈則說明沒有找到
while (node != null){
// int cmp = node.key.compareTo(key); // 這個不能反著來，不知道為啥，，，
int cmp = key.compareTo(node.key);
if (cmp > 0 ){
node = node.right;
}else if (cmp < 0 ){
node = node.left;
}else {
return node;
}
}
return null;
}
// 對外公開的方法
public V remove(K key){
// 先找到待洗掉的結點
RBNode<K,V> node = getNode(key);
if (node == null){
return null;
}
// 獲取要回傳的值
V oldValue = https://www.cnblogs.com/MuggleP/p/node.value;
// 洗掉結點
deleteNode(node);
return oldValue;
}
/**
* 1. 洗掉結點是葉子結點，那么直接洗掉
* 2. 洗掉結點有一個子節點，那么用子節點來替代洗掉結點
* 3. 洗掉結點有兩個子節點，直接洗掉情況太復雜，可以找到待洗掉結點的前驅結點和后繼結點來替代洗掉
* @param node
*/
private void deleteNode(RBNode node) {
// 洗掉結點有兩個孩子的情況，先把洗掉的結點替換為前驅或者后繼結點
if (leftOf(node)!=null && rightOf(node)!= null){
// 這是使用的是后繼結點
RBNode rep = successor(node);
// 使用前驅結點
// RBNode rep = predecessor(node);
node.key = rep.key;
node.value = rep.value;
// 把前驅或者后繼結點指向node
// 前驅或者后繼結點一定是葉子結點或只有一個孩子的結點，把問題簡單化
node = rep;
}
// 替換結點，如果左孩子不存在就回傳右孩子，當然如果右孩子也不存在那么就是null，也就是葉子結點了，也就是兩種情況:1.有一個孩子，2.沒有孩子
RBNode replacement = leftOf(node)!=null?leftOf(node):rightOf(node);
// 替換節點有一個孩子的情況
if (replacement != null){
// 這里的待洗掉結點可能是前驅也可能是后繼，兩種情況都判斷了，調整代碼時比較方便
// 將洗掉結點的父親給替代結點，也就是將子節點給關聯起來
replacement.parent = parentOf(node);
// 如果洗掉結點是只有一個孩子的根節點，那么把替代結點設定為跟結點
if (parentOf(node) == null){
this.root=replacement;
}
// 當前洗掉結點是后繼結點，treemap使用的
else if (node == leftOf(parentOf(node))){
node.parent.left = replacement;
}
// 當前洗掉結點是前驅結點
else {
node.parent.right = replacement;
}
// 參考全部為null，等待虛擬機回收垃圾
node.parent = node.left = node.right = null;
// 只有洗掉結點為黑色才有調整的必要，（如果是紅色的話，子節點一定是黑色，把子節點替換上了不會影響黑色結點的層數，所以也就不需要紅黑樹調整了
if (node.color == BLACK){
// replacement一定是紅色
fixAfterRemove(replacement);
}
}
// 如果洗掉結點是根節點，直接洗掉，這里的根節點是沒有孩子的根節點，
// 也就是樹上只有一個結點，也就是根節點，直接把樹清空
else if (parentOf(node) == null){
this.root = null;
}
// 替換結點是葉子結點的情況
else {
// 只有洗掉結點為黑色才有調整的必要
if (node.color == BLACK){
fixAfterRemove(replacement);
}
//先調整，再洗掉
if(node.parent!=null){
if(node==node.parent.left){
node.parent.left=null;
}
else if(node==node.parent.right){
node.parent.right=null;
}
node.parent=null;
}
}
}
紅黑樹洗掉后調整
/**
* 調整
* 情況一：自己能搞定的，也就是三節點和四節點，
* 如果是三節點，那么洗掉后將替代結點變色就可以了
* 如果是四結點，那么只可能洗掉四節點的兩邊結點，也就是兩個的紅色子節點
* 情況二：自己搞不定，找兄弟借，兄弟不借，父親下來，然后兄弟上去一個，
* 兄弟不能直接給，會破壞樹的順序，判斷條件就是沒有孩子的黑色結點，
* 父親下來了，那么父親的位置就會空一個，會破壞2-3-4樹的完整性，兄弟結點需要找一個上去
* 情況三：兄弟沒得借，強行洗掉，兄弟受到牽連，也就是2-3-4樹中，自己、兄弟、父親都是二節點，父親也不能向下融合洗掉
* 兄弟變紅，以父親為當前結點向上遞回進行判斷，進行按照情況二、三繼續進行判斷
*
* @param node
*/
private void fixAfterRemove(RBNode<K,V> node) {
while (node != root && colorOf(node)==BLACK){
// 洗掉結點是左孩子的情況
if(node == leftOf(parentOf(node))){
// 獲取叔叔結點，但是不一定是真正的叔叔結點（這個叔叔結點如果是紅色就不是真正的叔叔結點），需要進行判斷
RBNode<K,V> uncle = rightOf(parentOf(node));
// 獲取真正的叔叔結點
if (colorOf(uncle)==RED){
setColor(uncle,BLACK);
setColor(parentOf(node),RED);
leftRotate(parentOf(node));
// 更新叔叔結點
uncle = rightOf(parentOf(node));
}
// 情況三，兄弟也沒有，那么兄弟情同手足，自損變成紅色，并且向父親求助，也就是向上遞回，
// 如果父親是紅色那么變成黑色就平衡了，也就是回圈判斷里面，如果是紅色就退出回圈，在回圈下面機械能變色，如果不是那么繼續自損并且向上求助
// 對應2-3-4樹就是兄弟結點借不到， 如果父親是三節點，那么就向下融合一個變成四節點然后洗掉，如果父節點也是二結點，那么以父節點為當前結點繼續向上遞回判斷
// 這兩個判斷是兄弟結點的左右孩子都為空，black在colorOf方法中是null的替換
if (colorOf(leftOf(uncle))==BLACK&&colorOf(rightOf(uncle))==BLACK){
setColor(uncle,RED);
// 向上回圈，如果遞回到根節點，那么直接退出
node = parentOf(node);
}
// 情況二，找兄弟借，兄弟有的借，兄弟結點上去，父親結點下來，這樣滿足二叉樹的順序
else {
// 兄弟結點是三節點和四節點的情況類似
// 如果是三節點，孩子在右邊直接旋轉就行，在左邊算是例外，需要把左孩子旋轉到右邊然后在旋轉
// 如果是四節點，那么有兩種情況，第一種是給一個孩子，第二種是給兩個孩子，
// 第一種需要旋轉兩次（正常的紅黑樹），先按叔叔結點進行一次右旋，把三個結點放在一條線上，在按父節點左旋
// 第二種是旋轉一次（treemap中使用的，我在這也用這種），直接按照父節點左旋，減少了旋轉次數，優化了效率
// 三節點把孩子旋轉到右邊后，與四節點操作一樣了，不再需要判斷了
// 如果右孩子為空，那么兄弟的孩子一定是在左邊，因為洗掉的這個肯定是一個三節點
if (colorOf(rightOf(uncle))==BLACK){
// 不能直接進行旋轉，父節點是一個三節點，所以一定要有三個孩子，直接旋轉會破壞2-3-4樹定義
// 要先把兄弟結點的左孩子旋轉到右邊，然后在借出去
setColor(leftOf(uncle),BLACK);
setColor(uncle,RED);
// 這個時候叔叔結點下去了，需要更新叔叔結點
uncle = rightOf(parentOf(node));
}
// 將叔叔結點變成和父節點一樣的顏色
setColor(uncle, colorOf(parentOf(node)));
setColor(rightOf(uncle),BLACK);
setColor(parentOf(node),BLACK);
// 左孩子如果有的話，不用變色
leftRotate(parentOf(node));
// 將洗掉結點設為root，也就是退出回圈的意思
node = root;
}
}
// 洗掉結點是右孩子的情況，和左孩子正好相反
else {
RBNode<K,V> uncle = leftOf(parentOf(node));
// 獲取真正的叔叔結點
if (colorOf(uncle)==RED){
setColor(uncle,BLACK);
setColor(parentOf(node),RED);
rightRotate(parentOf(node));
uncle = leftOf(parentOf(node));
}
// 情況三，兄弟也沒有，那么兄弟情同手足，都自損變成紅色，并且向父親求助，也就是向上遞回，
if (colorOf(leftOf(uncle))==BLACK&&colorOf(rightOf(uncle))==BLACK){
setColor(uncle,RED);
// 向上回圈
node = parentOf(node);
}
// 情況二，找兄弟借，兄弟有的借，兄弟結點上去，父親結點下來，這樣滿足二叉樹的順序
else {
if (colorOf(leftOf(uncle))==BLACK){
setColor(rightOf(uncle),BLACK);
setColor(uncle,RED);
uncle = leftOf(parentOf(node));
}
setColor(uncle, colorOf(parentOf(node)));
setColor(leftOf(uncle),BLACK);
setColor(parentOf(node),BLACK);
leftRotate(parentOf(node));
node = root;
}
}
}
// 情況一，洗掉的結點有一個孩子，而且這個孩子肯定是紅色的，直接變色成黑色
// 情況三，根節點變為黑色
setColor(node,BLACK);
}
洗掉總結
- 按照key值找到該節點，并獲取洗掉結點的value值進行洗掉成功后的回傳
- 開始洗掉結點，先判斷該節點是否是最麻煩的情況（有兩個孩子），如果是就找到該節點的前驅節點或者后繼結點，我這里選擇后繼結點，這里洗掉并不是真正的洗掉，只是把后繼結點的值覆寫待洗掉結點的值，然后洗掉后繼結點即可
- 然后按照只有一個結點或者是葉子結點的情況進行洗掉操作（洗掉有一個孩子結點的情況，就用這個孩子進行替代，然后按孩子結點進行紅黑樹調整，如果洗掉的是葉子結點就先按葉子結點調整，然后再洗掉），只有洗掉結點為黑色才有調整的必要，如果是紅色直接洗掉就可以了，不影響紅黑樹，洗掉有一個孩子的情況，替代之后的這個孩子一定是紅色，所以可能會對紅黑樹的平衡有影響，洗掉葉子結點的話，被洗掉結點是黑色結點的情況，對紅黑樹肯定有影響需要調整再洗掉，
- 下邊是對2-3-4樹洗掉對應到紅黑樹中的調整：
- 自己能搞定的，也就是2-3-4樹中的三節點或者四節點
- 如果是三節點，那么洗掉后將替代結點變色就可以了，要洗掉的結點在洗掉階段就已經洗掉了，只需要在調整中將移上來的孩子結點變為黑色就行了
- 如果是四節點，不會進入調整中，因為洗掉的肯定是四節點的兩個紅色孩子結點，不影響紅黑樹
- 自己搞不定的，也就是2-3-4樹中的二節點，兄弟結點能借，但兄弟結點不借，父節點下來，兄弟節點上去
- 兄弟不能直接給，會破壞樹的順序，判斷條件就是沒有孩子的黑色結點（不是三、四結點），
- 父親下來了，那么父親的位置就會空一個，會破壞2-3-4樹的完整性，兄弟結點需要找一個上去
- 兄弟沒得借，那么當前結點強行洗掉，兄弟受到牽連，也就是2-3-4樹中，自己、兄弟、父親都是二節點，父親也不能向下融合洗掉，如果向下融合的話在2-3-4樹中就會少一層，破壞性質
- 兄弟變紅，以父親為當前結點向上遞回進行判斷，進行按照情況二、三繼續進行判斷，如果迭代到了根部還沒有解決，那么就結束迭代，紅黑樹就會少一層黑色結點
- 自己能搞定的，也就是2-3-4樹中的三節點或者四節點
洗掉結點模擬
3.總代碼
紅黑樹代碼
public class RBTree<K extends Comparable<K>,V> {
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;
}
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 boolean colorOf(RBNode node){
// 如果該結點為空，就回傳BLACK，就是一個判空操作
// treeMap原始碼就是這樣寫的
return node== null ?BLACK:node.color;
}
private void setColor(RBNode node,boolean color){
if (node != null){
node.color = color;
}
}
/**
* 右旋
* gn gn
* / /
* n rn
* / \ / \
* rn ln --> rr n
* / \ / \
* rr rl rl ln
*/
private void rightRotate(RBNode n){
if (n != null){
// 獲取左孩子
RBNode rn = n.left;
// 1、將rl放到n的左孩子上
// rn.right為null不影響賦值
n.left = rn.right;
if (rn.right != null){
rn.right.parent = n;
}
// 2、將rn放的n的位置
rn.parent = n.parent;
// 如果父節點為空，就將rn指向根節點
if (n.parent == null){
this.root = rn;
}
// // 判斷rn該插入到父節點的左右哪個孩子結點
else if (n == n.parent.left){
n.parent.left = rn;
}else {
n.parent.right = rn;
}
// 3、將換好位置的rn與n互相系結
rn.right = n;
n.parent = rn;
}
}
/**
* 左旋就是將右旋反過來
* @param n
*/
private void leftRotate(RBNode n){
if (n != null){
RBNode rl = n.right;
n.right = rl.left;
if (rl.left != null){
rl.left.parent = n;
}
rl.parent = n.parent;
if (n.parent == null){
this.root = rl;
} else if (n == n.parent.left){
n.parent.left = rl;
}else {
n.parent.right = rl;
}
rl.left = n;
n.parent = rl;
}
}
/**
* 插入
* @param key
* @param value
*/
public void put(K key,V value){
RBNode node = this.root;
// 1、判斷根節點是否存在
if (node == null){
// 如果不存在，則直接將當前結點設定為根節點，新創建結點默認是黑色
root = new RBNode<K, V>(null, key, value =https://www.cnblogs.com/MuggleP/p/= null? (V) key :value);
return;
}
// 2、查找插入結點的父節點
RBNode parent = node;
int cmp;
if (key == null){
throw new NullPointerException();
}
do {
parent = node;
// 如果key值大于父節點，往右子樹進行尋找
// 如果key值小于父節點，往左子樹進行尋找
// 如果key值命中，直接替換值然后回傳
cmp = key.compareTo(parent.key);
if (cmp > 0){
node = node.right;
}else if (cmp < 0){
node = node.left;
}else {
node.value = value;
return;
}
}while (node != null);
node = new RBNode(parent, key, value == null? (V) key :value);
// 3、將新插入結點與父節點關聯
node.parent = parent;
if (cmp > 0){
parent.right = node;
}else {
parent.left = node;
}
// 上面三步插入是二叉樹與紅黑樹通用的插入方法，下面調整才是紅黑樹平衡的重點
// 插入完之后，調整
fixAfterPut(node);
}
/**
* 1.2-3-4樹：插入第一個結點，將當前結點設為根節點
* 紅黑樹：將插入結點變成黑色，新創建的結點默認就是黑色，所有也不需要調整
* 2.2-3-4樹：插入一個結點與2結點結合，變成一個三節點
* 紅黑樹：插入到黑色結點下面，不需要調整
* 3.2-3-4樹：插入一個結點與3結點結合，變成一個四節點
* 紅黑樹：父節點為紅色，爺爺結點為黑色，這里有四種情況（左三，右三，左中右，右中左），這里只有左三和右三需要調整
* 新增結點+上黑下紅 --> 旋轉變色 --> 中間結點為黑色，左右兩個結點為紅色（爺爺結點下來變紅，父親結點上去變黑）
* 4.2-3-4樹：插入一個結點與4結點結合，4結點分裂，中間結點上去待合并，新增結點與左右兩個2結點結合
* 紅黑樹：父節點和叔叔結點是紅色，爺爺結點是黑色 --> 變色 --> 父親和叔叔變黑，爺爺變紅，以爺爺結點繼續進行這四種判斷
* @param node
*/
private void fixAfterPut(RBNode node){
// 插入結點都為紅色
setColor(node,RED);
// 只有3、4情況才需要調整，這里的回圈是遞回操作情況4
while (node != null && node != this.root && parentOf(node).color == RED){
// 插入結點在左邊,也就是叔叔結點在右邊
if (parentOf(node) == parentOf(parentOf(node)).left){
RBNode gParent = parentOf(parentOf(node));
RBNode uncle = rightOf(gParent);
// 情況4
if (colorOf(uncle) == RED){
setColor(parentOf(node),BLACK);
setColor(uncle,BLACK);
setColor(gParent,RED);
// 在當前子樹進行調整完之后，以爺爺結點為當前結點，繼續遞回往上進行調整
// 如果遞回到根節點就退出，然后將根節點染色，層數加一
// 如果遞回到當前結點的父節點為黑色，那么調整成功，直接退出回圈
node = gParent;
}else { // 情況3
// 這是情況3的一種特殊情況，插入到父節點的右孩子
// 需要進行一次左旋，就調整成正宗的左3
if (node == rightOf(parentOf(node))){
node = parentOf(node);
leftOf(node);
}
setColor(parentOf(node),BLACK);
setColor(gParent,RED);
rightRotate(gParent);
}
}else { // 插入結點在右邊
RBNode gParent = parentOf(parentOf(node));
RBNode uncle = leftOf(gParent);
// 情況4
if (colorOf(uncle) == RED){
setColor(parentOf(node),BLACK);
setColor(uncle,BLACK);
setColor(gParent,RED);
node = gParent;
}else { // 情況3
if (node == leftOf(parentOf(node))){
node = parentOf(node);
rightOf(node);
}
setColor(parentOf(node),BLACK);
setColor(gParent,RED);
leftRotate(gParent);
}
}
}
setColor(this.root,BLACK);
}
/**
* 找前驅結點
* 方法：找該節點的左子樹，找到后從左子樹的右孩子一直往下找
* @param node
* @return
*/
private RBNode predecessor(RBNode node){
if (node == null){
return null;
}
// 如果有左孩子，那么就從左孩子的右孩子一直往下找
else if (leftOf(node) != null){
RBNode lNode = leftOf(node);
// 如果右孩子為空，那么就說明找到了，直接退出回傳
while (rightOf(lNode) !=null){
lNode = rightOf(lNode);
}
return lNode;
}else {
// 在洗掉操作中是不會出現這種情況的，這種情況一般是葉子結點或者只有一個孩子
// 在洗掉操作中如果是這種情況就直接洗掉了
// 這里是找前驅結點的情況，所有把這種情況也一塊寫下來了
// 獲取父節點
RBNode parent = parentOf(node);
// 獲取自己
RBNode child = node;
// 判斷當前結點是否是父節點的左結點，如果是就說明找到了，退出回傳
// 如果父節點為空，也就是找到根節點還沒有找到，那么說明當前結點沒有前驅結點，回傳null
while (parent!=null&&child==leftOf(parent)){
child = parent;
parent = parentOf(parent);
}
// if (parent == null){
// return node;
// }
return parent;
}
}
/**
* 找后繼結點
* 與找前驅相反
* @param node
* @return
*/
private RBNode successor(RBNode node){
if (node == null){
return null;
}
else if (rightOf(node) != null){
RBNode rNode = rightOf(node);
while (leftOf(rNode) !=null){
rNode = leftOf(rNode);
}
return rNode;
}else {
RBNode parent = parentOf(node);
RBNode child = node;
while (parent!=null&&child==rightOf(parent)){
child = parent;
parent = parentOf(parent);
}
// if (parent == null){
// return node;
// }
return parent;
}
}
/**
* 洗掉結點，回傳洗掉結點的值
* @param key
* @return
*/
public V remove(K key){
// 先找到待洗掉的結點
RBNode node = getNode(key);
if (node == null){
return null;
}
// 獲取要回傳的值
V oldValue = node.value;
// 洗掉結點
deleteNode(node);
return oldValue;
}
/**
* 1. 洗掉結點是葉子結點，那么直接洗掉
* 2. 洗掉結點有一個子節點，那么用子節點來替代洗掉結點
* 3. 洗掉結點有兩個子節點，直接洗掉情況太復雜，可以找到待洗掉結點的前驅結點和后繼結點來替代洗掉
* @param node
*/
private void deleteNode(RBNode node) {
// 洗掉結點有兩個孩子的情況，先把洗掉的結點替換為前驅或者后繼結點
if (leftOf(node)!=null && rightOf(node)!= null){
// 這是使用的是后繼結點
RBNode rep = successor(node);
// 使用前驅結點
// RBNode rep = predecessor(node);
node.key = rep.key;
node.value = rep.value;
// 把前驅或者后繼結點指向node
// 前驅或者后繼結點一定是葉子結點或只有一個孩子的結點
node = rep;
}
// 替換結點，如果左孩子不存在就回傳右孩子，當然如果右孩子也不存在那么就是null，也就是葉子結點了
RBNode replacement = leftOf(node)!=null?leftOf(node):rightOf(node);
// 替換節點有一個孩子的情況
if (replacement != null){
// 這里的待洗掉結點可能是前驅也可能是后繼，兩種情況都判斷了，調整代碼時比較方便
// 將洗掉結點的父親給替代結點，也就是將子節點給關聯起來
replacement.parent = parentOf(node);
// 如果洗掉結點是只有一個孩子的根節點，那么把替代結點設定為跟結點
if (parentOf(node) == null){
this.root=replacement;
}
// 當前洗掉結點是后繼結點
else if (node == leftOf(parentOf(node))){
node.parent.left = replacement;
}
// 當前洗掉結點是前驅結點
else {
node.parent.right = replacement;
}
// 參考全部為null，等待虛擬機回收垃圾
node.parent = node.left = node.right = null;
// 只有洗掉結點為黑色才有調整的必要
if (node.color == BLACK){
// 替代結點一定是紅色
fixAfterRemove(replacement);
}
}
// 如果洗掉結點是根節點，直接洗掉，這里的根節點是沒有孩子的根節點，
// 也就是樹上只有一個結點，也就是根節點，直接把樹清空
else if (parentOf(node) == null){
this.root = null;
}
// 替換結點是葉子結點的情況
else {
// 只有洗掉結點為黑色才有調整的必要
if (node.color == BLACK){
fixAfterRemove(node);
}
//這里調整完之后，把與父親的指標斷掉，變成垃圾等待回收
if(node.parent!=null){
if(node==node.parent.left){
node.parent.left=null;
}
else if(node==node.parent.right){
node.parent.right=null;
}
node.parent=null;
}
}
}
/**
* 調整
* 情況一：自己能搞定的，也就是三節點和四節點，
* 如果是三節點，那么洗掉后將替代結點變色就可以了
* 如果是四結點，那么只可能洗掉四節點的兩邊結點，也就是兩個的紅色子節點
* 情況二：自己搞不定，找兄弟借，兄弟不借，父親下來，然后兄弟上去一個，
* 兄弟不能直接給，會破壞樹的順序，判斷條件就是沒有孩子的黑色結點，
* 父親下來了，那么父親的位置就會空，會破壞2-3-4樹的完整性，兄弟結點需要找一個上去
* 情況三：兄弟沒得借，都自損，也就是2-3-4樹中，自己、兄弟、父親都是二節點，也就是父親也不能向下融合洗掉了
* 兄弟變紅，以父親為當前結點向上遞回進行判斷，進行按照情況二、三進行判斷
*
* @param node
*/
private void fixAfterRemove(RBNode node) {
while (node != root && colorOf(node)==BLACK){
// 洗掉結點是左孩子的情況
if(node == leftOf(parentOf(node))){
// 獲取叔叔結點，但是不一定是真正的叔叔結點（這個叔叔結點如果是紅色就不是真正的叔叔結點），需要進行判斷
RBNode uncle = rightOf(parentOf(node));
// 獲取真正的叔叔結點
if (colorOf(uncle)==RED){
setColor(uncle,BLACK);
setColor(parentOf(node),RED);
leftRotate(parentOf(node));
uncle = rightOf(parentOf(node));
}
// 情況三，兄弟也沒有，那么兄弟情同手足，都自損變成紅色，并且向父親求助，也就是向上遞回，
// 如果父親是紅色那么變成黑色就平衡了，也就是回圈判斷里面，如果是紅色就退出回圈然后變色，如果不是那么繼續自損并且向上求助
// 對應2-3-4樹就是兄弟結點借不到， 如果父親是三節點，那么就向下融合一個變成四節點然后洗掉，
// 如果父節點也是二結點，那么以父節點為當前結點繼續向上遞回判斷
// 這兩個判斷是兄弟結點的左右孩子都為空，black在colorOf方法中是null的替換
if (colorOf(leftOf(uncle))==BLACK&&colorOf(rightOf(uncle))==BLACK){
// 情況復雜
setColor(uncle,RED);
// 向上回圈，如果遞回到根節點，那么直接退出
node = parentOf(node);
}
// 情況二，找兄弟借，兄弟有的借，兄弟結點上去，父親結點下來，這樣滿足二叉樹的順序
else {
// 兄弟結點是三節點還是四節點的情況類似
// 如果是三節點，孩子在右邊直接旋轉就行，在左邊算是例外，需要把左孩子旋轉到右邊然后在旋轉
// 如果是四節點，那么有兩種情況，第一種是給一個孩子，第二種是給兩個孩子，
// 第一種需要旋轉兩次（正常的紅黑樹），先按叔叔結點進行一次右旋，把三個結點放在一條線上，在按父節點左旋
// 第二種是旋轉一次（treemap中使用的，我在這也用這種），直接按照父節點左旋，減少了旋轉次數，優化了效率
// 三節點把孩子旋轉到右邊后，與四節點操作一樣了，不再需要判斷了
// 如果右孩子為空，那么兄弟的孩子一定是在左邊，因為洗掉的這個肯定是一個三節點
if (colorOf(rightOf(uncle))==BLACK){
// 不能直接進行旋轉，父節點是一個三節點，所以一定要有三個孩子，直接旋轉會破壞2-3-4樹
// 要先把兄弟結點的左孩子旋轉到右邊，然后在借出去
setColor(leftOf(uncle),BLACK);
setColor(uncle,RED);
// 這個時候叔叔結點下去了，需要在進行賦值
uncle = rightOf(parentOf(node));
}
// 將叔叔結點變成和父節點一樣的顏色
setColor(uncle, colorOf(parentOf(node)));
setColor(rightOf(uncle),BLACK);
setColor(parentOf(node),BLACK);
// 左孩子如果有的話，不用變色
leftRotate(parentOf(node));
// 將洗掉結點設為root，也就是退出回圈的意思
node = root;
}
}
// 洗掉結點是右孩子的情況，和左孩子正好相反
else {
RBNode uncle = leftOf(parentOf(node));
// 獲取真正的叔叔結點
if (colorOf(uncle)==RED){
setColor(uncle,BLACK);
setColor(parentOf(node),RED);
rightRotate(parentOf(node));
uncle = leftOf(parentOf(node));
}
// 情況三，兄弟也沒有，那么兄弟情同手足，都自損變成紅色，并且向父親求助，也就是向上遞回，
if (colorOf(leftOf(uncle))==BLACK&&colorOf(rightOf(uncle))==BLACK){
// 情況復雜
setColor(uncle,RED);
// 向上回圈
node = parentOf(node);
}
// 情況二，找兄弟借，兄弟有的借，兄弟結點上去，父親結點下來，這樣滿足二叉樹的順序
else {
if (colorOf(leftOf(uncle))==BLACK){
setColor(rightOf(uncle),BLACK);
setColor(uncle,RED);
uncle = leftOf(parentOf(node));
}
setColor(uncle, colorOf(parentOf(node)));
setColor(leftOf(uncle),BLACK);
setColor(parentOf(node),BLACK);
leftRotate(parentOf(node));
node = root;
}
}
}
// 情況一，洗掉的結點有一個孩子，而且這個孩子肯定是紅色的，直接變色成黑色
// 情況三，父親變為黑色
setColor(node,BLACK);
}
private RBNode getNode(K key) {
RBNode node = this.root;
// 從根節點開始遍歷，如果大于往右走，小于往左走，等于則回傳
// 出回圈則說明沒有找到
while (node != null){
int cmp = key.compareTo(node.key);
if (cmp > 0 ){
node = node.right;
}else if (cmp < 0 ){
node = node.left;
}else {
return node;
}
}
return null;
}
static class RBNode,V>{
private RBNode parent;
private RBNode left;
private RBNode right;
private K key;
private V value;
private boolean color = BLACK;
public RBNode() {
}
public RBNode(RBNode parent, K key, V value) {
this.parent = parent;
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 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;
}
public boolean isColor() {
return color;
}
public void setColor(boolean color) {
this.color = color;
}
}
}
控制臺列印紅黑樹
public class TreeOperation {
/*
樹的結構示例：
1
/ \
2 3
/ \ / \
4 5 6 7
*/
// 用于獲得樹的層數
public static int getTreeDepth(RBTree.RBNode root) {
return root == null ? 0 : (1 + Math.max(getTreeDepth(root.getLeft()), getTreeDepth(root.getRight())));
}
private static void writeArray(RBTree.RBNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
// 保證輸入的樹不為空
if (currNode == null) return;
// 0、默認無色
// res[rowIndex][columnIndex] = String.valueOf(currNode.getValue());
//1、顏色表示
if(currNode.isColor()){//黑色，加色后錯位比較明顯
res[rowIndex][columnIndex] = ("\033[30;3m" + currNode.getValue()+"\033[0m") ;
}else {
res[rowIndex][columnIndex] = ("\033[31;3m" + currNode.getValue()+"\033[0m") ;
}
//2、R,B表示
// res[rowIndex][columnIndex] = String.valueOf(currNode.getValue()+"-"+(currNode.isColor()?"B":"R")+"");
// 計算當前位于樹的第幾層
int currLevel = ((rowIndex + 1) / 2);
// 若到了最后一層，則回傳
if (currLevel == treeDepth) return;
// 計算當前行到下一行，每個元素之間的間隔（下一行的列索引與當前元素的列索引之間的間隔）
int gap = treeDepth - currLevel - 1;
// 對左兒子進行判斷，若有左兒子，則記錄相應的"/"與左兒子的值
if (currNode.getLeft() != null) {
res[rowIndex + 1][columnIndex - gap] = "/";
writeArray(currNode.getLeft(), rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
}
// 對右兒子進行判斷，若有右兒子，則記錄相應的"\"與右兒子的值
if (currNode.getRight() != null) {
res[rowIndex + 1][columnIndex + gap] = "\\";
writeArray(currNode.getRight(), rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
}
}
public static void show(RBTree.RBNode root) {
if (root == null) System.out.println("EMPTY!");
// 得到樹的深度
int treeDepth = getTreeDepth(root);
// 最后一行的寬度為2的（n - 1）次方乘3，再加1
// 作為整個二維陣列的寬度
int arrayHeight = treeDepth * 2 - 1;
int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
// 用一個字串陣列來存盤每個位置應顯示的元素
String[][] res = new String[arrayHeight][arrayWidth];
// 對陣列進行初始化，默認為一個空格
for (int i = 0; i < arrayHeight; i ++) {
for (int j = 0; j < arrayWidth; j ++) {
res[i][j] = " ";
}
}
// 從根節點開始，遞回處理整個樹
// res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
writeArray(root, 0, arrayWidth/2, res, treeDepth);
// 此時，已經將所有需要顯示的元素儲存到了二維陣列中，將其拼接并列印即可
for (String[] line: res) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < line.length; i ++) {
sb.append(line[i]);
if (line[i].length() > 1 && i <= line.length - 1) {
i += line[i].length() > 4 ? 2: line[i].length() - 1;
}
}
System.out.println(sb.toString());
}
}
}
測驗紅黑樹
import java.util.Scanner;
public class RBTreeTest {
public static void main(String[] args) {
//新增節點
// insertOpt();
//洗掉節點
deleteOpt();
}
/**
* 插入操作
*/
public static void insertOpt(){
Scanner scanner=new Scanner(System.in);
RBTree<String,Object> rbt=new RBTree<>();
while (true){
System.out.println("請輸入你要插入的節點:");
String key=scanner.next();
System.out.println();
//這里代碼最多支持3位數，3位以上的話紅黑樹顯示太錯位了，這里就不重構代碼了,大家可自行重構
if(key.length()==1){
key="00"+key;
}else if(key.length()==2){
key="0"+key;
}
rbt.put(key,null);
TreeOperation.show(rbt.getRoot());
}
}
/**
* 洗掉操作
*/
public static void deleteOpt(){
RBTree<String,Object> rbt=new RBTree<>();
// 測驗1：預先造10個節點（1-10）
String keyA=null;
for (int i = 1; i <11 ; i++) {
if((i+"").length()==1){
keyA="00"+i;
}else if((i+"").length()==2){
keyA="0"+i;
}
rbt.put(keyA,null);
}
TreeOperation.show(rbt.getRoot());
//以下開始洗掉
Scanner scanner=new Scanner(System.in);
while (true){
System.out.println("請輸入你要洗掉的節點:");
String key=scanner.next();
System.out.println();
//這里代碼最多支持3位數，3位以上的話紅黑樹顯示太錯位了，這里就不重構代碼了,大家可自行重構
if(key.length()==1){
key="00"+key;
}else if(key.length()==2){
key="0"+key;
}
//1 2 3 88 66 77 100 5 4 101
rbt.remove(key);
TreeOperation.show(rbt.getRoot());
}
}
}
作者： .Muggle
出處： https://www.cnblogs.com/MuggleP/p/15418613.html
關于作者：.Muggle
本文著作權歸作者和博客園共有，歡迎轉載，但未經作者同意必須保留此段宣告，且在文章頁面明顯位置給出, 原文鏈接 如有問題， 可郵件（[email protected]）咨詢.
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/320817.html
標籤：Java