• 数据结构与算法【红黑树】的Java实现+图解

    前言

    建议先阅读普通二叉搜索树与平衡二叉搜索树的文章。理解一些基本的二叉树知识数据结构与算法【二叉搜索树】Java实现-CSDN博客

    介绍

    红黑树也是一种自平衡的二叉搜索树，较之 AVL，插入和删除时旋转次数更少。

    首先介绍代码实现会用到的概念

    • 兄弟节点：具有同一个父结点的一对节点可以互称为兄弟节点
    • 叔叔节点：父结点的兄弟节点

    红黑树特性

    1. 所有节点都有两种颜色：红🔴、黑⚫️

    2. 所有 null 视为黑色⚫️

    3. 红色🔴节点不能相邻

    4. 根节点是黑色⚫️

    5. 从根到任意一个叶子节点，路径中的黑色⚫️节点数一样

    根据该特性，我们可以总结出

    红色节点要么没有孩子要么有两个黑孩子

    举例

    以下情况均不属于红黑树

    红红相邻

    不满足从根节点到任意叶子节点路径中的黑色节点个数相同，到达1、3节点黑色节点个数为2，而到7、9的黑色节点个数为3。

    当叶子节点不存在兄弟节点这种情况时。需要加入null值，而null值充当黑色节点。

    因此，将该图补充完整后如下

    节点2的叶子节点与其他叶子节点路径上的黑色个数不同。因此也不能称为红黑树。

    但是下图就属于红黑树

    这种情况下，即使将null值加上，也满足红黑树

    实现

    大体框架

    1. public class RedBlackTree {
    2.     //需要红黑两种颜色
    3.     enum Color {
    4.         RED, BLACK;
    5.     }
    6.  
    7.     Node root;
    8.  
    9.     static class Node {
    10.         int key;
    11.         Object value;
    12.         Node left;
    13.         Node right;
    14.         Node parent;        // 父节点
    15.         Color color = RED;  // 颜色
    16.  
    17.         public Node(int key, Object value) {
    18.             this.key = key;
    19.             this.value = value;
    20.         }
    21.  
    22.         public Node(int key, Color color) {
    23.             this.key = key;
    24.             this.color = color;
    25.         }
    26.  
    27.         public Node(int key, Color color, Node left, Node right) {
    28.             this.key = key;
    29.             this.color = color;
    30.             this.left = left;
    31.             this.right = right;
    32.             if (left != null) {
    33.                 left.parent = this;
    34.             }
    35.             if (right != null) {
    36.                 right.parent = this;
    37.             }
    38.         }
    39.  
    40.         // 对于父结点来说，自己是否是左孩子
    41.         boolean isLeftChild() {
    42.             return parent != null && parent.left == this;
    43.         }
    44.  
    45.         // 获取叔叔节点
    46.         Node uncle() {
    47.             //根节点与根节点的左右孩子均不存在叔叔节点
    48.             if (parent == null || parent.parent == null) {
    49.                 return null;
    50.             }
    51.             //如果父亲节点是左孩子
    52.             if (parent.isLeftChild()) {
    53.                 //返回父亲节点的兄弟节点
    54.                 return parent.parent.right;
    55.             } else {
    56.                 return parent.parent.left;
    57.             }
    58.         }
    59.  
    60.         // 获取兄弟
    61.         Node sibling() {
    62.             //根节点不存在兄弟节点
    63.             if (parent == null) {
    64.                 return null;
    65.             }
    66.             //如果该节点是左孩子
    67.             if (this.isLeftChild()) {
    68.                 //返回右孩子
    69.                 return parent.right;
    70.             } else {
    71.                 return parent.left;
    72.             }
    73.         }
    74.     }
    75.  
    76.     // 判断红
    77.     boolean isRed(Node node) {
    78.         return node != null && node.color == RED;
    79.     }
    80.  
    81.     // 判断黑
    82.     boolean isBlack(Node node) {
    83.         return node == null || node.color == BLACK;
    84.     }
    85.  
    86.     //与平衡二叉搜索树的旋转相比，多了一步修改各个节点的parent属性修改
    87.     private void rightRotate(Node node) {
    88.         //被旋转节点的父结点
    89.         Node parent = node.parent;
    90.         //获取新的子树父结点
    91.         Node newNode = node.left;
    92.         //将新的子树父结点的右孩子充当旋转节点的左孩子，腾出新父节点的右孩子位置给被旋转节点
    93.         Node rightChild = newNode.right;
    94.         if (rightChild != null) {
    95.             //如果右孩子不是null，那么将右孩子的父结点设置为被旋转节点
    96.             rightChild.parent = node;
    97.         }
    98.         node.left = rightChild;
    99.         //将新的子树节点的右孩子设置为被旋转节点
    100.         newNode.right = node;
    101.         //将新父节点的parent属性设置为被旋转节点的parent
    102.         newNode.parent = parent;
    103.         //将被旋转节点的parent属性设置为新的父结点
    104.         node.parent = newNode;
    105.  
    106.         //修改被旋转节点的父结点的孩子属性
    107.         if (parent == null) {
    108.             //说明被旋转的节点为根节点
    109.             root = newNode;
    110.         } else if (parent.left == node) {//如果被旋转节点是父结点的左孩子
    111.             //将新的左孩子设置为新的子树父结点
    112.             parent.left = newNode;
    113.         } else {
    114.             parent.right = newNode;
    115.         }
    116.     }
    117.  
    118.     // 左旋
    119.     private void leftRotate(Node node) {
    120.         Node parent = node.parent;
    121.         Node newNode = node.right;
    122.         Node leftChild = newNode.left;
    123.         if (leftChild != null) {
    124.             leftChild.parent = node;
    125.         }
    126.         newNode.left = node;
    127.         newNode.parent = parent;
    128.         node.right = leftChild;
    129.         node.parent = newNode;
    130.         if (parent == null) {
    131.             root = newNode;
    132.         } else if (parent.left == node) {
    133.             parent.left = newNode;
    134.         } else {
    135.             parent.right = newNode;
    136.         }
    137.     }
    138.     
    139. }

    展示一下右旋的流程

    旋转不需要进行变色，只需要修改移动节点的parent属性以及left或是right属性。

    接下来针对红黑树特性，实现插入和删除代码

    实现插入的功能

    1. /**
    2.  * 新增或更新
    3.  * 正常增、遇到红红不平衡进行调整
    4.  *
    5.  * @param key   键
    6.  * @param value 值
    7.  */
    8. public void put(int key, Object value) {
    9.     Node p = root;
    10.     Node parent = null;
    11.     //找到新增位置与父结点位置
    12.     while (p != null) {
    13.         parent = p;
    14.         if (key < p.key) {
    15.             p = p.left;
    16.         } else if (p.key < key) {
    17.             p = p.right;
    18.         } else {
    19.             p.value = value; // 更新
    20.             return;
    21.         }
    22.     }
    23.     Node inserted = new Node(key, value);
    24.     if (parent == null) {
    25.         //说明向根节点更新数据
    26.         root = inserted;
    27.     } else if (key < parent.key) {
    28.         parent.left = inserted;
    29.         inserted.parent = parent;
    30.     } else {
    31.         parent.right = inserted;
    32.         inserted.parent = parent;
    33.     }
    34.     //新增完成后，进行修正红黑树
    35.     fixRedRed(inserted);
    36. }

    修正红黑树方法fixRedRed()存在四种情况：

    首先需要知道的是插入节点均视为红色🔴

    case 1：插入节点为根节点，将根节点变黑⚫️

    case 2：插入节点的父亲若为黑色⚫️，树的红黑性质不变，无需调整

    插入节点的父亲为红色🔴，触发红红相邻，红红相邻又分为case 3与case 4两种情况

    case 3：叔叔为红色🔴

    • 父亲变为黑色⚫️，为了保证黑色平衡，连带的叔叔也变为黑色⚫️

    • 祖父如果是黑色不变，会造成这颗子树黑色过多，因此祖父节点变为红色🔴

    • 祖父如果变成红色，可能会接着触发红红相邻，因此对将祖父进行递归调整

    图示如下

    接下来需要插入节点 1

    触发红红相邻，且叔叔节点 4 也为红色

    此时，不满足从根节点到任意叶子节点路径上黑色节点个数相同的条件，因此，需要把祖父节点 3变成红色

    此时又触发了红红相邻，因此再次执行相同操作。

    到达根节点时，将根节点变色就是实现了红黑树调整

    case 4：叔叔为黑色⚫️

    1、父亲为左孩子，插入节点也是左孩子，此时即 LL 不平衡

    • 让父亲变黑⚫️，为了保证这颗子树黑色不变，将祖父变成红🔴，但叔叔子树少了一个黑色
    • 祖父右旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻

    2、父亲为左孩子，插入节点是右孩子，此时即 LR 不平衡

    • 父亲左旋，变成 LL 情况，按 1. 来后续处理

    3、父亲为右孩子，插入节点也是右孩子，此时即 RR 不平衡

    • 让父亲变黑⚫️，为了保证这颗子树黑色不变，将祖父变成红🔴，但叔叔子树少了一个黑色

    • 祖父左旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻

    4、父亲为右孩子，插入节点是左孩子，此时即 RL 不平衡

    • 父亲右旋，变成 RR 情况，按 3. 来后续处理

    图示如下

    接下来去添加节点2

    触发红红相邻，经过调整后如下图所示

    此时不平衡，需要进行一次右旋，旋转后结果如下

    1. private void fixRedRed(Node x) {
    2.     // case 1 插入节点是根节点，变黑即可
    3.     if (x == root) {
    4.         x.color = BLACK;
    5.         return;
    6.     }
    7.     // case 2 插入节点父亲是黑色，无需调整
    8.     if (isBlack(x.parent)) {
    9.         return;
    10.     }
    11.     // case 3 当红红相邻，叔叔为红时
    12.     // 需要将父亲、叔叔变黑、祖父变红，然后对祖父做递归处理
    13.     Node parent = x.parent;
    14.     Node uncle = x.uncle();
    15.     Node grandparent = parent.parent;
    16.     if (isRed(uncle)){
    17.         parent.color = BLACK;
    18.         uncle.color = BLACK;
    19.         grandparent.color = RED;
    20.         //如果祖父与祖父的父亲也触发了红红相邻，那么递归修改祖父,直到不再触发红红相邻
    21.         fixRedRed(grandparent);
    22.         return;
    23.     }
    24.  
    25.     // case 4 当红红相邻，叔叔为黑时
    26.     if (parent.isLeftChild() && x.isLeftChild()) { // LL
    27.         parent.color = BLACK;
    28.         grandparent.color = RED;
    29.         rightRotate(grandparent);
    30.     } else if (parent.isLeftChild()) { // LR
    31.         leftRotate(parent);
    32.         x.color = BLACK;
    33.         grandparent.color = RED;
    34.         rightRotate(grandparent);
    35.     } else if (!x.isLeftChild()) { // RR
    36.         parent.color = BLACK;
    37.         grandparent.color = RED;
    38.         leftRotate(grandparent);
    39.     } else { // RL
    40.         rightRotate(parent);
    41.         x.color = BLACK;
    42.         grandparent.color = RED;
    43.         leftRotate(grandparent);
    44.     }
    45. }

    实现删除的功能

    删之前我们需要清楚红黑树一个特性：删黑色会失衡，删红色不会失衡

    一共存在下面几种情况：

    一；如果删除的是叶子节点

    如果是红色节点，直接删除就好

    case0：如果删除节点有两个孩子

    • 交换删除节点和后继节点的 key，value，递归删除后继节点，直到该节点没有孩子或只剩一个孩子

    图示如下

    比如说要删除节点 8，那么找到 8 的后继节点 9，并交换 8 与 9 的key与value

    接下来就相当于删除叶子节点了。

    case 1：

    • 删的是根节点

      • 删完了，直接将 root = null

      • 用剩余节点替换了根节点的 key，value，根节点孩子 = null，颜色保持黑色⚫️不变

    case 2：删的是黑⚫️，剩下的是红🔴，剩下这个红节点变黑⚫️

    图示如下

    接下来去删除节点 2。

    节点 3 顶替节点 2 的位置，但此时违背从根节点到叶子节点的黑色节点个数相同。因此，需要将剩下的这个节点修改为黑色

    调整节点和剩下节点都是黑⚫️，触发双黑，双黑意思是，少了一个黑

    case 3：被调整节点的兄弟为红🔴，此时两个侄子定为黑 ⚫️

    • 删除节点是左孩子，父亲左旋

    • 删除节点是右孩子，父亲右旋

    • 父亲和兄弟要变色，保证旋转后颜色平衡

    • 旋转的目的是让黑侄子变为删除节点的黑兄弟，对删除节点再次递归，进入 case 4 或 case 5

    图示如下

    接下来要删除节点 4。父亲节点 6 左旋。

    旋转过后颜色不平衡，需要修改被删除节点的原兄弟节点 8 与原父结点 6 的颜色。

    此时删除节点 4 时，仍然会触发双黑，但是此时触发双黑走的是另一个逻辑case4或case5

    case 4：被调整节点的兄弟为黑⚫️，两个侄子都为黑 ⚫️

    • 将兄弟变红🔴，目的是将删除节点和兄弟那边的黑色高度同时减少 1

    • 如果父亲是红🔴，则需将父亲变为黑，避免红红，此时路径黑节点数目不变

    • 如果父亲是黑⚫️，说明这条路径还是少黑，再次让父节点触发双黑

    当父结点为红色的情况，图示如下

    将被调整节点 4 的兄弟节点 7 变色为红色，但此时节点6，7不调整的话触发双红，因此需要将父结点修改为黑色

    修改过后，可以直接将删除节点去除。

    以上情况是父结点为红色的情况，如果父结点为黑色，那么调整父结点颜色也无法使红黑树平衡。下面是父结点为黑色的情况。

    需要删除节点 1。将兄弟节点 3 变红。但时父结点为黑色节点，那么将父结点作为调整节点再次执行双黑代码

    被调整节点 2 仍满足case4的情况，因此将兄弟节点修改为红色。但父结点 4 依然是黑色节点，那么将父结点 4 作为新的被调整节点，执行双黑代码

    此时被调整节点 4 仍满足case4的情况，因此将兄弟节点修改为红色。虽然父结点8仍然是黑色节点，但由于已经是根节点，因此结束触发双黑的代码。最后调整结果如下

    case 5：被调整节点的兄弟为黑⚫️，至少一个红🔴侄子

    • 如果兄弟是左孩子，左侄子是红🔴，LL 不平衡

      • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑⚫️，平衡起见，左侄子也是黑⚫️

      • 原来兄弟要成为父亲，需要保留父亲颜色

    • 如果兄弟是左孩子，右侄子是红🔴，LR 不平衡

      • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑⚫️

      • 右侄子会取代原来父亲，因此它保留父亲颜色

      • 兄弟已经是黑了⚫️，无需改变

    • 如果兄弟是右孩子，右侄子是红🔴，RR 不平衡

      • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑⚫️，平衡起见，右侄子也是黑⚫️

      • 原来兄弟要成为父亲，需要保留父亲颜色

    • 如果兄弟是右孩子，左侄子是红🔴，RL 不平衡

      • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑⚫️

      • 左侄子会取代原来父亲，因此它保留父亲颜色

      • 兄弟已经是黑了⚫️，无需改变

    接下来查看一种LL的情况，图示如下

    首先要删除的节点为 4。删除后LL不平衡，因此对节点 3 进行一次右旋。

    旋转过后，需要对节点颜色进行修改，首先是原来的兄弟节点 2 ，修改为原来的父亲节点 3 的颜色。新的两个孩子节点1 ，3修改为黑色。

    再来看一种LR的情况，图示如下

    要删除节点 4 ，需要将兄弟节点 1 进行一次左旋。

    然后再将父结点 3 进行一次右旋

    旋转过后，可以看到，原本兄弟节点 1 的右孩子 2 变成了新的父结点，因此，需要将 2 的颜色修改为原本的父结点 3 的颜色，将原本的父结点 3 的颜色修改为黑色。

    具体实现代码如下

    1. 	public void remove(int key) {
    2.         //得到被删除节点
    3.         Node deleted = find(key);
    4.         if (deleted == null) {
    5.             return;
    6.         }
    7.         doRemove(deleted);
    8.     }
    9.  
    10.     private void doRemove(Node deleted) {
    11.         //替代被删除节点的节点
    12.         Node replaceNode = findReplaced(deleted);
    13.         Node parent = deleted.parent;
    14.         //首先进行判断，如果要删除的节点是叶子节点
    15.         if (replaceNode == null) {
    16.             //如果是根节点
    17.             if (deleted == root) {
    18.                 root = null;
    19.             } else {
    20.                 if (isBlack(deleted)) {
    21.                     //需要进行调整
    22.                     fixDoubleBlack(deleted);
    23.                 }
    24.                 //如果不是根节点，判断是父结点的左孩子还是右孩子
    25.                 if (deleted.isLeftChild()) {
    26.                     parent.left = null;
    27.                 } else {
    28.                     parent.right = null;
    29.                 }
    30.             }
    31.             return;
    32.         }
    33.         //如果被删除节点存在一个孩子
    34.         if (deleted.left == null || deleted.right == null) {
    35.             if (deleted == root) {
    36.                 //如果是根节点，那么让该子节点直接顶替root节点即可
    37.                 root.key = replaceNode.key;
    38.                 root.value = replaceNode.value;
    39.                 replaceNode.parent = root.left = root.right = null;
    40.             } else {
    41.                 if (deleted.isLeftChild()) {
    42.                     //如果被删除节点是父结点的左孩子
    43.                     parent.left = replaceNode;
    44.                 } else {
    45.                     parent.right = replaceNode;
    46.                 }
    47.                 replaceNode.parent = parent;
    48.                 deleted.left = deleted.parent = deleted.right = null;
    49.                 //将被删除节点删除后，判断是否需要进行调整
    50.                 if (isBlack(deleted) && isBlack(replaceNode)) {
    51.                     //如果删除节点与后驱节点都为黑色，那么删除一个黑色会导致黑色节点个数不同(这种情况不存在)
    52.                     fixDoubleBlack(replaceNode);
    53.                 } else {
    54.                     //如果被删除节点与后驱节点是一红一黑，那么都只需要将后驱节点颜色设置为黑色即可
    55.                     replaceNode.color = BLACK;
    56.                 }
    57.             }
    58.             return;
    59.         }
    60.         //说明有两个孩子,replaceNode是该节点的后驱节点,这里我们采用值交换的方法来实现删除节点
    61.         int t = deleted.key;
    62.         deleted.key = replaceNode.key;
    63.         replaceNode.key = t;
    64.  
    65.         Object value = deleted.value;
    66.         deleted.value = replaceNode.value;
    67.         replaceNode.value = value;
    68.         //经过交换后，此时被删除节点只有一个孩子或是没有孩子。再次执行删除操作
    69.         doRemove(replaceNode);
    70.     }
    71.  
    72.     /**
    73.      * 触发双黑的调整
    74.      * @param node 被调整的节点
    75.      */
    76.     private void fixDoubleBlack(Node node) {
    77.         if (node == root){
    78.             return;
    79.         }
    80.         //被调整节点的父亲节点
    81.         Node parent = node.parent;
    82.         //被调整节点的兄弟节点
    83.         Node sibling = node.sibling();
    84.         //case 3代码，目的是调整红黑树为case4或case5的情况
    85.         if (isRed(sibling)){
    86.             if (node.isLeftChild()){
    87.                 leftRotate(parent);
    88.             }else {
    89.                 rightRotate(parent);
    90.             }
    91.             parent.color = RED;
    92.             sibling.color =BLACK;
    93.             fixDoubleBlack(node);
    94.             return;
    95.         }
    96.         if (sibling!=null){
    97.             //case 4
    98.             if (isBlack(sibling.left) && isBlack(sibling.right)){
    99.                 sibling.color = RED;
    100.                 if (isRed(parent)){
    101.                     parent.color = BLACK;
    102.                 }else {
    103.                     fixDoubleBlack(parent);
    104.                 }
    105.             }else {
    106.                 //case 5
    107.                 // LL
    108.                 if (sibling.isLeftChild() && isRed(sibling.left)) {
    109.                     rightRotate(parent);
    110.                     sibling.left.color = BLACK;
    111.                     sibling.color = parent.color;
    112.                 }
    113.                 // LR
    114.                 else if (sibling.isLeftChild() && isRed(sibling.right)) {
    115.                     sibling.right.color = parent.color;
    116.                     leftRotate(sibling);
    117.                     rightRotate(parent);
    118.                 }
    119.                 // RL
    120.                 else if (!sibling.isLeftChild() && isRed(sibling.left)) {
    121.                     sibling.left.color = parent.color;
    122.                     rightRotate(sibling);
    123.                     leftRotate(parent);
    124.                 }
    125.                 // RR
    126.                 else {
    127.                     leftRotate(parent);
    128.                     sibling.right.color = BLACK;
    129.                     sibling.color = parent.color;
    130.                 }
    131.                 parent.color = BLACK;
    132.             }
    133.  
    134.         }
    135.     }
    136.  
    137.     private Node find(int key) {
    138.         Node p = root;
    139.         while (p != null) {
    140.             if (p.key > key) {
    141.                 p = p.left;
    142.             } else if (key > p.key) {
    143.                 p = p.right;
    144.             } else {
    145.                 return p;
    146.             }
    147.         }
    148.         return null;
    149.     }
    150.  
    151.     // 查找剩余节点或是后继节点
    152.     private Node findReplaced(Node deleted) {
    153.         if (deleted.left == null && deleted.right == null) {
    154.             return null;
    155.         }
    156.         if (deleted.left == null) {
    157.             return deleted.right;
    158.         }
    159.         if (deleted.right == null) {
    160.             return deleted.left;
    161.         }
    162.         Node s = deleted.right;
    163.         while (s.left != null) {
    164.             s = s.left;
    165.         }
    166.         return s;
    167.     }

    完整代码

    1. public class RedBlackTree {
    2.     enum Color {
    3.         RED, BLACK;
    4.     }
    5.  
    6.     Node root;
    7.  
    8.     static class Node {
    9.         int key;
    10.         Object value;
    11.         Node left;
    12.         Node right;
    13.         Node parent;        // 父节点
    14.         Color color = RED;  // 颜色
    15.  
    16.         public Node(int key, Object value) {
    17.             this.key = key;
    18.             this.value = value;
    19.         }
    20.  
    21.         public Node(int key, Color color) {
    22.             this.key = key;
    23.             this.color = color;
    24.         }
    25.  
    26.         public Node(int key, Color color, Node left, Node right) {
    27.             this.key = key;
    28.             this.color = color;
    29.             this.left = left;
    30.             this.right = right;
    31.             if (left != null) {
    32.                 left.parent = this;
    33.             }
    34.             if (right != null) {
    35.                 right.parent = this;
    36.             }
    37.         }
    38.  
    39.         // 是否是左孩子
    40.         boolean isLeftChild() {
    41.             return parent != null && parent.left == this;
    42.         }
    43.  
    44.         // 获取叔叔节点
    45.         Node uncle() {
    46.             //根节点与根节点的左右孩子均不存在叔叔节点
    47.             if (parent == null || parent.parent == null) {
    48.                 return null;
    49.             }
    50.             //如果父亲节点是左孩子
    51.             if (parent.isLeftChild()) {
    52.                 //返回父亲节点的兄弟节点
    53.                 return parent.parent.right;
    54.             } else {
    55.                 return parent.parent.left;
    56.             }
    57.         }
    58.  
    59.         // 获取兄弟
    60.         Node sibling() {
    61.             //根节点不存在兄弟节点
    62.             if (parent == null) {
    63.                 return null;
    64.             }
    65.             //如果该节点是左孩子
    66.             if (this.isLeftChild()) {
    67.                 //返回右孩子
    68.                 return parent.right;
    69.             } else {
    70.                 return parent.left;
    71.             }
    72.         }
    73.     }
    74.  
    75.     // 判断红
    76.     boolean isRed(Node node) {
    77.         return node != null && node.color == RED;
    78.     }
    79.  
    80.     // 判断黑
    81.     boolean isBlack(Node node) {
    82.         return node == null || node.color == BLACK;
    83.     }
    84.  
    85.     //需要处理的是，被旋转节点的孩子节点的parent属性修改，以及被旋转节点的父结点的孩子属性修改
    86.     private void rightRotate(Node node) {
    87.         //被旋转节点的父结点
    88.         Node parent = node.parent;
    89.         //获取新的子树父结点
    90.         Node newNode = node.left;
    91.         //将新的子树父结点的右孩子充当旋转节点的左孩子，腾出新父节点的右孩子位置给被旋转节点
    92.         Node rightChild = newNode.right;
    93.         if (rightChild != null) {
    94.             //如果右孩子不是null，那么将右孩子的父结点设置为被旋转节点
    95.             rightChild.parent = node;
    96.         }
    97.         node.left = rightChild;
    98.         //将新的子树节点的右孩子设置为被旋转节点
    99.         newNode.right = node;
    100.         //将新父节点的parent属性设置为被旋转节点的parent
    101.         newNode.parent = parent;
    102.         //将被旋转节点的parent属性设置为新的父结点
    103.         node.parent = newNode;
    104.  
    105.         //修改被旋转节点的父结点的孩子属性
    106.         if (parent == null) {
    107.             //说明被旋转的节点为根节点
    108.             root = newNode;
    109.         } else if (parent.left == node) {//如果被旋转节点是父结点的左孩子
    110.             //将新的左孩子设置为新的子树父结点
    111.             parent.left = newNode;
    112.         } else {
    113.             parent.right = newNode;
    114.         }
    115.     }
    116.  
    117.     // 左旋
    118.     private void leftRotate(Node node) {
    119.         Node parent = node.parent;
    120.         Node newNode = node.right;
    121.         Node leftChild = newNode.left;
    122.         if (leftChild != null) {
    123.             leftChild.parent = node;
    124.         }
    125.         newNode.left = node;
    126.         newNode.parent = parent;
    127.         node.right = leftChild;
    128.         node.parent = newNode;
    129.         if (parent == null) {
    130.             root = newNode;
    131.         } else if (parent.left == node) {
    132.             parent.left = newNode;
    133.         } else {
    134.             parent.right = newNode;
    135.         }
    136.     }
    137.  
    138.  
    139.     /**
    140.      * 新增或更新
    141.      * 正常增、遇到红红不平衡进行调整
    142.      *
    143.      * @param key   键
    144.      * @param value 值
    145.      */
    146.     public void put(int key, Object value) {
    147.         Node p = root;
    148.         Node parent = null;
    149.         //找到新增位置与父结点位置
    150.         while (p != null) {
    151.             parent = p;
    152.             if (key < p.key) {
    153.                 p = p.left;
    154.             } else if (p.key < key) {
    155.                 p = p.right;
    156.             } else {
    157.                 p.value = value; // 更新
    158.                 return;
    159.             }
    160.         }
    161.         Node inserted = new Node(key, value);
    162.         if (parent == null) {
    163.             //说明向根节点更新数据
    164.             root = inserted;
    165.         } else if (key < parent.key) {
    166.             parent.left = inserted;
    167.             inserted.parent = parent;
    168.         } else {
    169.             parent.right = inserted;
    170.             inserted.parent = parent;
    171.         }
    172.         //新增完成后，进行修正红黑树
    173.         fixRedRed(inserted);
    174.     }
    175.  
    176.     private void fixRedRed(Node x) {
    177.         // case 1 插入节点是根节点，变黑即可
    178.         if (x == root) {
    179.             x.color = BLACK;
    180.             return;
    181.         }
    182.         // case 2 插入节点父亲是黑色，无需调整
    183.         if (isBlack(x.parent)) {
    184.             return;
    185.         }
    186.         // case 3 当红红相邻，叔叔为红时
    187.         // 需要将父亲、叔叔变黑、祖父变红，然后对祖父做递归处理
    188.         Node parent = x.parent;
    189.         Node uncle = x.uncle();
    190.         Node grandparent = parent.parent;
    191.         if (isRed(uncle)) {
    192.             parent.color = BLACK;
    193.             uncle.color = BLACK;
    194.             grandparent.color = RED;
    195.             //如果祖父与祖父的父亲也触发了红红相邻，那么递归修改祖父,直到不再触发红红相邻
    196.             fixRedRed(grandparent);
    197.             return;
    198.         }
    199.  
    200.         // case 4 当红红相邻，叔叔为黑时
    201.         if (parent.isLeftChild() && x.isLeftChild()) { // LL
    202.             parent.color = BLACK;
    203.             grandparent.color = RED;
    204.             rightRotate(grandparent);
    205.         } else if (parent.isLeftChild()) { // LR
    206.             leftRotate(parent);
    207.             x.color = BLACK;
    208.             grandparent.color = RED;
    209.             rightRotate(grandparent);
    210.         } else if (!x.isLeftChild()) { // RR
    211.             parent.color = BLACK;
    212.             grandparent.color = RED;
    213.             leftRotate(grandparent);
    214.         } else { // RL
    215.             rightRotate(parent);
    216.             x.color = BLACK;
    217.             grandparent.color = RED;
    218.             leftRotate(grandparent);
    219.         }
    220.     }
    221.  
    222.     public void remove(int key) {
    223.         //得到被删除节点
    224.         Node deleted = find(key);
    225.         if (deleted == null) {
    226.             return;
    227.         }
    228.         doRemove(deleted);
    229.     }
    230.  
    231.     private void doRemove(Node deleted) {
    232.         //替代被删除节点的节点
    233.         Node replaceNode = findReplaced(deleted);
    234.         Node parent = deleted.parent;
    235.         //首先进行判断，如果要删除的节点是叶子节点
    236.         if (replaceNode == null) {
    237.             //如果是根节点
    238.             if (deleted == root) {
    239.                 root = null;
    240.             } else {
    241.                 if (isBlack(deleted)) {
    242.                     //需要进行调整
    243.                     fixDoubleBlack(deleted);
    244.                 }
    245.                 //如果不是根节点，判断是父结点的左孩子还是右孩子
    246.                 if (deleted.isLeftChild()) {
    247.                     parent.left = null;
    248.                 } else {
    249.                     parent.right = null;
    250.                 }
    251.             }
    252.             return;
    253.         }
    254.         //如果被删除节点存在一个孩子
    255.         if (deleted.left == null || deleted.right == null) {
    256.             if (deleted == root) {
    257.                 //如果是根节点，那么让该子节点直接顶替root节点即可
    258.                 root.key = replaceNode.key;
    259.                 root.value = replaceNode.value;
    260.                 replaceNode.parent = root.left = root.right = null;
    261.             } else {
    262.                 if (deleted.isLeftChild()) {
    263.                     //如果被删除节点是父结点的左孩子
    264.                     parent.left = replaceNode;
    265.                 } else {
    266.                     parent.right = replaceNode;
    267.                 }
    268.                 replaceNode.parent = parent;
    269.                 deleted.left = deleted.parent = deleted.right = null;
    270.                 //将被删除节点删除后，判断是否需要进行调整
    271.                 if (isBlack(deleted) && isBlack(replaceNode)) {
    272.                     //如果删除节点与后驱节点都为黑色，那么删除一个黑色会导致黑色节点个数不同(这种情况不存在)
    273.                     fixDoubleBlack(replaceNode);
    274.                 } else {
    275.                     //如果被删除节点与后驱节点是一红一黑，那么都只需要将后驱节点颜色设置为黑色即可
    276.                     replaceNode.color = BLACK;
    277.                 }
    278.             }
    279.             return;
    280.         }
    281.         //说明有两个孩子,replaceNode是该节点的后驱节点,这里我们采用值交换的方法来实现删除节点
    282.         int t = deleted.key;
    283.         deleted.key = replaceNode.key;
    284.         replaceNode.key = t;
    285.  
    286.         Object value = deleted.value;
    287.         deleted.value = replaceNode.value;
    288.         replaceNode.value = value;
    289.         //经过交换后，此时被删除节点只有一个孩子或是没有孩子。再次执行删除操作
    290.         doRemove(replaceNode);
    291.     }
    292.  
    293.     /**
    294.      * 触发双黑的调整
    295.      * @param node 被调整的节点
    296.      */
    297.     private void fixDoubleBlack(Node node) {
    298.         if (node == root){
    299.             return;
    300.         }
    301.         //被调整节点的父亲节点
    302.         Node parent = node.parent;
    303.         //被调整节点的兄弟节点
    304.         Node sibling = node.sibling();
    305.         //case 3代码，目的是调整红黑树为case4或case5的情况
    306.         if (isRed(sibling)){
    307.             if (node.isLeftChild()){
    308.                 leftRotate(parent);
    309.             }else {
    310.                 rightRotate(parent);
    311.             }
    312.             parent.color = RED;
    313.             sibling.color =BLACK;
    314.             fixDoubleBlack(node);
    315.             return;
    316.         }
    317.         if (sibling!=null){
    318.             //case 4
    319.             if (isBlack(sibling.left) && isBlack(sibling.right)){
    320.                 sibling.color = RED;
    321.                 if (isRed(parent)){
    322.                     parent.color = BLACK;
    323.                 }else {
    324.                     fixDoubleBlack(parent);
    325.                 }
    326.             }else {
    327.                 //case 5
    328.                 // LL
    329.                 if (sibling.isLeftChild() && isRed(sibling.left)) {
    330.                     rightRotate(parent);
    331.                     sibling.left.color = BLACK;
    332.                     sibling.color = parent.color;
    333.                 }
    334.                 // LR
    335.                 else if (sibling.isLeftChild() && isRed(sibling.right)) {
    336.                     sibling.right.color = parent.color;
    337.                     leftRotate(sibling);
    338.                     rightRotate(parent);
    339.                 }
    340.                 // RL
    341.                 else if (!sibling.isLeftChild() && isRed(sibling.left)) {
    342.                     sibling.left.color = parent.color;
    343.                     rightRotate(sibling);
    344.                     leftRotate(parent);
    345.                 }
    346.                 // RR
    347.                 else {
    348.                     leftRotate(parent);
    349.                     sibling.right.color = BLACK;
    350.                     sibling.color = parent.color;
    351.                 }
    352.                 parent.color = BLACK;
    353.             }
    354.  
    355.         }
    356.     }
    357.  
    358.     private Node find(int key) {
    359.         Node p = root;
    360.         while (p != null) {
    361.             if (p.key > key) {
    362.                 p = p.left;
    363.             } else if (key > p.key) {
    364.                 p = p.right;
    365.             } else {
    366.                 return p;
    367.             }
    368.         }
    369.         return null;
    370.     }
    371.  
    372.     // 查找剩余节点或是后继节点
    373.     private Node findReplaced(Node deleted) {
    374.         if (deleted.left == null && deleted.right == null) {
    375.             return null;
    376.         }
    377.         if (deleted.left == null) {
    378.             return deleted.right;
    379.         }
    380.         if (deleted.right == null) {
    381.             return deleted.left;
    382.         }
    383.         Node s = deleted.right;
    384.         while (s.left != null) {
    385.             s = s.left;
    386.         }
    387.         return s;
    388.     }
    389. }
  • 相关阅读:
    第二章 进程与线程 十二、进程同步与进程互斥
    Java之spring新手教程(包教包会)
    AWK用法全解与sed去掉sql最后一个字段哪一行的逗号
    VsCode集成Python开发环境
    代码随想录训练营Day 32|Python|Leetcode|● 738.单调递增的数字
    Java8新特性必知必会
    基于Python的信用评分卡模型建立和分析，万字详述，关注收藏
    【爬虫】get 和 post 的区别
    【linux应用开发】
    大厂敲门砖！原阿里P8架构师整理12万字Java面试技巧心得
  • 原文地址：https://blog.csdn.net/zmbwcx/article/details/134555933