資料結構~基礎2~樹【《二叉樹、二叉搜尋樹、AVL樹、B樹、紅黑樹》的設計】~紅黑樹
一、 紅黑樹：
☼ 紅黑樹之介紹：
-----------形态上是特殊的二叉搜尋樹【特殊展現在顔色上，同時在邏輯上它是等價于4階B樹的】
❀ 紅黑樹是怎麼等價于4 階B 樹的？ ---------紅黑樹要變成B樹：需要将紅結點和黑結點進行合并（黑色作為根【也是中間元素】）。
✿ 紅黑-->B 樹： 結點有四種情況是：①紅-黑-紅、②紅-黑、③黑-紅、④黑
❀ 紅黑樹的通用接口：二叉搜尋樹的通用接口 + 增加之後、删掉之後、
旋轉【左旋、右旋】、旋轉之後的處理【更新父結點的關系】（旋轉、旋轉之後跟AVL 樹一樣）
■ 插入的所有位置情況：
| ❀ 總結紅黑樹的添加之後的調整 ❀ ： 1，分類：（具體過程需要根據父結點作為左結點、右結點進行對稱） （1）不需要調整： ■ 目前結點是根，染黑即可； ■ 父結點是黑，不用處理。 （2）需要調整：（根據叔父結點是否為紅色進行劃分） ■ case1：叔父是紅色，目前結點x 可左可右，染黑 父、叔，染紅爺，回溯到結點爺處。 ■ case2：叔父是黑色，目前結點x 是右孩子【紅紅是LR型】，先進行左旋，轉化成case3； （先考慮目前結點是右孩子，因為它處理一下就變成了case3）【小細節，目前結點x 指向 父結點時，旋轉x(其實旋轉的是原先的父結點的位置)】； ■ case3：叔父是黑色，目前結點x 是左孩子【紅紅是LL型】，染黑父，染紅爺，然後右旋。 |
@Override
protected void afterAdd(Node<E> node) {
// 判斷父結點
Node<E> parent = node.parent;
// 添加的是根【當添加第一個結點時】/ 或者上溢到了根結點時
if (parent == null) {
black(node);
return;
}
// 若父結點是黑色時，不用處理，直接傳回
if (isBlack(parent))
return;
// 若叔父結點是紅色的[B 樹的上溢]
Node<E> uncle = parent.sibling();
Node<E> grand = red(parent.parent);
if (isRed(uncle)) {
// 染黑爸爸、叔叔，把祖父染成紅色，相當于新插入的結點
black(uncle);
black(parent);
// ① 上溢時，也要染紅祖父結點
afterAdd(grand);
return;
}
// 觀察一下，對代碼進行優化，共同擁有的抽到外部之類的
// 來到這裡叔父不是紅色
if (parent.isLeftChild()) { // L
// ② 旋轉時，也要 染紅結點
if (node.isLeftChild()) { // LL
// 染黑父結點，染紅祖父結點
black(parent);
// 右旋
} else { // LR
// 染紅自己、染黑祖父結點
black(node);
// 左旋後右旋
rotateLeft(parent);
}
rotateRight(grand);
} else { // R
// ② 旋轉時，也要 染紅結點
if (node.isLeftChild()) { // RL
// 染紅自己、染黑祖父結點
black(node);
// 左旋後右旋
rotateRight(parent);
} else { // RR
// 染黑父結點，染紅祖父結點
black(parent);
// 左旋
}
rotateLeft(grand);
}
} ■ 删除的所有位置情況：
■ 删除之後：
| ❀ 總結紅黑樹的删除之後的調整 ❀ ： 1，删除結點是紅色，（完美），不用處理； 2，删除結點是黑色：【看替代結點--前驅/後驅結點】 （1）替代結點是紅色，染黑替代結點【前驅/後驅結點】 （2）替代結點是黑色，（若是根，完美，不用處理），黑色結點： ● 黑色葉子結點：【看兄弟】：----- 站在B樹角度，發生了下溢 【B樹中的處理，找兄弟借，兄弟借不了，找父結點下來合并】 [1] 兄弟是黑色，且能借（至少有一個子紅色結點），旋轉借出去。 【直接借的話，不符合二叉搜尋樹的特點，根大于左子樹，根小于右子樹（需要旋轉交換一下結點，（符合二叉搜尋樹特點）然後再借）】。 [2] 兄弟是黑色，不能借（沒有紅色結點），看父結點： ① 父結點是紅色：染黑父結點，染紅兄弟，進行合并。 ② 父結點是黑色，下溢處理。 [3] 兄弟是紅色，通過旋轉，把侄子(黑色結點)變成兄弟【又變成了删除的結點的兄弟結點是黑色結點】 |
● 黑色葉子結點：【看兄弟】：
[3] 兄弟是紅色，通過旋轉，把侄子(黑色結點)變成兄弟【又變成了删除的結點的兄弟結點是黑色結點】：
隻能是圖示：（兄弟跟父結點在同一個B樹的子結點上（同一層上），且紅色兄弟有兩個黑色的子結點）
❀ 删除黑色葉子結點時，發生了下溢，而顯然不在同一層上的兄弟肯定是不能借出結點，
隻能考慮跟自己處于同一層【兄弟的兒子】，向兄弟的兒子進行借。【但是在B樹中借的前提，兩者是兄弟關系】
是以目标就是要将兄弟的兒子，變成我的兄弟才能順利成章的借。
[1] 兄弟是黑色，且能借（至少有一個子紅色結點），旋轉借出去。【旋轉的結果是變成了根（成為獨立的B樹結點），就需要将其染黑】
protected void afterRemove2(Node<E> node, Node<E> replacement) {
//删除結點是紅色 或者 替代結點【前驅/後驅】是紅色
if(isRed(node)) return;
if (isRed(replacement)) {
black(replacement);
return;
}
//接下來考慮删除結點是黑色【排除掉根的情況】
Node<E> parent = node.parent;
// 删除的是根節點
if (parent == null)
return;
// 删除黑色葉子節點【下溢】
boolean left = parent.left == null || node.isLeftChild();// 判斷被删除的node是左還是右
Node<E> sibling = left ? parent.right : parent.left;
if (left) { // 被删除的節點在左邊，兄弟節點在右邊
//看兄弟【兄弟是紅色，染黑兄弟，通過左旋，讓兄弟成為根，更新一下兄弟位置】
if (isRed(sibling)) { // 兄弟節點是紅色
black(sibling);
red(parent);
rotateLeft(parent);
// 重新指一下兄弟（更新一下兄弟位置）
sibling = parent.right;
}
// 【兄弟結點是黑色，兄弟沒有紅色子結點，不能借】~下溢情況
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟節點借不出，父節點要向下跟兄弟節點合并【父結點作為下來結點的根】
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {//若是父結點原先是黑色，導緻塌陷，遞歸
afterRemove2(parent, null);
}
// 【兄弟結點是黑色，兄弟有紅色子結點可以借】
} else {
// 兄弟節點的左結點是黑色，兄弟要先旋轉
if (isBlack(sibling.right)) {
rotateRight(sibling);
//更新一下兄弟結點
sibling = parent.right;
}
//旋轉之後，旋轉之後的中心節點繼承 parent 的顔色；
//旋轉之後的左右節點染為 BLACK ----【成為獨立的B樹結點】
color(sibling, colorOf(parent));
black(sibling.right);
black(parent);
rotateLeft(parent);
}
} else { // 被删除的節點在右邊，兄弟節點在左邊
if (isRed(sibling)) { // 兄弟節點是紅色
black(sibling);
red(parent);
rotateRight(parent);
// 更換兄弟
sibling = parent.left;
}
// 兄弟節點必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟節點沒有1個紅色子節點，父節點要向下跟兄弟節點合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove2(parent,null);
}
} else { // 兄弟節點至少有1個紅色子節點，向兄弟節點借元素
// 兄弟節點的左邊是黑色，兄弟要先旋轉
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
}