• 你真的了解红黑树的怎么实现的吗？

    1.前言

    红黑树是一种自平衡的二叉查找树，是在普通的二叉查找树的基础上增加了一些限制和规则，使得它能够自我调整来保持平衡。它的作用主要有以下几个方面：

    1. 查找和插入元素的时间复杂度都是O(logN)，其中N为树中节点的个数，因此红黑树可以高效地进行查找和插入操作。

    2. 在很多需要动态维护有序序列数据结构的场景中，红黑树可以非常高效地实现这个目标。

    3. 红黑树还可以用于高效地实现区间查询等数据结构，比如线段树。在这种场景下，红黑树作为线段树的底层数据结构，能够提升线段树查询、更新的效率。

    总之，红黑树是一种非常有用的数据结构，其自平衡特性使得它具有高效的查找和插入等操作，因此被广泛应用于数据处理和算法实现的领域。 

     2.原理分析

    2.1.左旋操作

    左旋是将当前节点往左旋转的操作。具体步骤如下：

    1. 将当前节点的右子节点（称为y）设为当前节点（称为x）的父节点。
    2. 将y的左子节点设为x的右子节点。
    3. 如果y的左子节点非空，将x设为y的左子节点的父节点。
    4. 将y的左子节点设为x。
    5. 将y的父节点设为原本x的父节点。
    6. 如果原本x的父节点为空，则将y设为红黑树的根节点；否则，如果x是其父节点的左子节点，则将y设为其父节点的左子节点；否则，将y设为其父节点的右子节点。

    2.2右旋操作

    左旋是将当前节点往左旋转的操作。具体步骤如下：

    1. 将当前节点的右子节点（称为y）设为当前节点（称为x）的父节点。
    2. 将y的左子节点设为x的右子节点。
    3. 如果y的左子节点非空，将x设为y的左子节点的父节点。
    4. 将y的左子节点设为x。
    5. 将y的父节点设为原本x的父节点。
    6. 如果原本x的父节点为空，则将y设为红黑树的根节点；否则，如果x是其父节点的左子节点，则将y设为其父节点的左子节点；否则，将y设为其父节点的右子节点。

    左右旋的作用:

    通过左旋和右旋操作可以改变节点之间的位置关系，从而保持红黑树的平衡性。这两个操作在插入或删除节点时经常被用到，以确保红黑树的性质得到维护和恢复。

    2.3 插入节点

    1. 插入操作：

      • 首先根据传入的键值创建一个新节点，并将其颜色设置为红色。
      • 通过比较键值大小，将新节点插入到正确的位置上，确保满足二叉查找树的性质。
      • 调用修复插入操作来保证红黑树的性质：
        • 如果插入节点的父节点是黑色节点，那么不需要进行调整，红黑树的性质没有被破坏。
        • 如果插入节点的父节点是红色节点，那么可能会破坏红黑树的性质，需要进行相应的调整。

    2.4插入后维持红黑树的平衡性

    1. 修复插入操作： 在红黑树中，有三种情况需要进行调整，分别是：插入节点的父节点是红色的情况下，叔节点是红色的情况下，和插入节点的父节点是红色且叔节点是黑色的情况下。调整的目标是使得插入节点的父节点是黑色，叔节点和祖父节点是红色，保持红黑树的性质。

      • 左旋转和右旋转：通过旋转操作来调整节点的位置，使得红黑树保持平衡。
      • 颜色翻转：通过改变节点的颜色来维护红黑树的性质。

    2.5删除节点 

    1. 插入操作：

      • 首先根据传入的键值创建一个新节点，并将其颜色设置为红色。
      • 通过比较键值大小，将新节点插入到正确的位置上，确保满足二叉查找树的性质。
      • 调用修复插入操作来保证红黑树的性质：
        • 如果插入节点的父节点是黑色节点，那么不需要进行调整，红黑树的性质没有被破坏。
        • 如果插入节点的父节点是红色节点，那么可能会破坏红黑树的性质，需要进行相应的调整。

    2.6删除后维持红黑树的平衡性

    1. 修复删除操作： 删除节点可能会破坏红黑树的性质，需要进行相应的调整。

      • 如果删除的节点是红色的，不会影响红黑树的性质，直接删除即可。
      • 如果删除的节点是黑色的，可能会导致红黑树的性质被破坏，需要进行相应的修复。修复的目标是保持每个节点到其后代叶节点的黑色节点数量相同。

    3.代码实现

    3.1准备工作

    1. // 红黑树节点类
    2. class RBNode {
    3.     int data;
    4.     RBNode parent;
    5.     RBNode left;
    6.     RBNode right;
    7.     int color;
    8.  
    9.     public RBNode(int data) {
    10.         this.data = data;
    11.         this.parent = null;
    12.         this.left = null;
    13.         this.right = null;
    14.         this.color = 1; // 默认节点为红色
    15.     }
    16. }
    17. // 红黑树类
    18. class RedBlackTree {
    19.     private RBNode root;
    20.  
    21.     public RedBlackTree() {
    22.         root = null;
    23.     }
    24. }

    3.2.左旋操作

    1.  // 左旋操作
    2.     private void leftRotate(RBNode x) {
    3.         RBNode y = x.right;
    4.         x.right = y.left;
    5.         if (y.left != null) {
    6.             y.left.parent = x;
    7.         }
    8.         y.parent = x.parent;
    9.         if (x.parent == null) {
    10.             root = y;
    11.         } else if (x == x.parent.left) {
    12.             x.parent.left = y;
    13.         } else {
    14.             x.parent.right = y;
    15.         }
    16.         y.left = x;
    17.         x.parent = y;
    18.     }

    3.3右旋操作

    1. // 右旋操作
    2.     private void rightRotate(RBNode y) {
    3.         RBNode x = y.left;
    4.         y.left = x.right;
    5.         if (x.right != null) {
    6.             x.right.parent = y;
    7.         }
    8.         x.parent = y.parent;
    9.         if (y.parent == null) {
    10.             root = x;
    11.         } else if (y == y.parent.left) {
    12.             y.parent.left = x;
    13.         } else {
    14.             y.parent.right = x;
    15.         }
    16.         x.right = y;
    17.         y.parent = x;
    18.     }

    3.4插入节点

    1. // 插入节点
    2.     public void insert(int key) {
    3.         RBNode newNode = new RBNode(key);
    4.         RBNode current = root;
    5.         RBNode parent = null;
    6.  
    7.         while (current != null) {
    8.             parent = current;
    9.             if (key < current.data) {
    10.                 current = current.left;
    11.             } else {
    12.                 current = current.right;
    13.             }
    14.         }
    15.  
    16.         newNode.parent = parent;
    17.         if (parent == null) {
    18.             root = newNode;
    19.         } else if (key < parent.data) {
    20.             parent.left = newNode;
    21.         } else {
    22.             parent.right = newNode;
    23.         }
    24.  
    25.         // 调整红黑树
    26.         fixInsert(newNode);
    27.     }

    3.5插入后维持红黑树的平衡性

    1. // 插入后修正红黑树平衡性
    2.     private void fixInsert(RBNode node) {
    3.         while (node.parent != null && node.parent.color == 1) {
    4.             // 当前节点的父节点是祖父节点的左子节点
    5.             if (node.parent == node.parent.parent.left) {
    6.                 RBNode uncle = node.parent.parent.right;
    7.                 // Case 1: 叔叔节点是红色
    8.                 if (uncle != null && uncle.color == 1) {
    9.                     node.parent.color = 0;
    10.                     uncle.color = 0;
    11.                     node.parent.parent.color = 1;
    12.                     node = node.parent.parent;
    13.                 } else {
    14.                     // Case 2: 叔叔节点是黑色，且当前节点是右子节点
    15.                     if (node == node.parent.right) {
    16.                         node = node.parent;
    17.                         leftRotate(node);
    18.                     }
    19.                     // Case 3: 叔叔节点是黑色，且当前节点是左子节点
    20.                     node.parent.color = 0;
    21.                     node.parent.parent.color = 1;
    22.                     rightRotate(node.parent.parent);
    23.                 }
    24.             } else {
    25.                 // 当前节点的父节点是祖父节点的右子节点
    26.                 RBNode uncle = node.parent.parent.left;
    27.                 // Case 1: 叔叔节点是红色
    28.                 if (uncle != null && uncle.color == 1) {
    29.                     node.parent.color = 0;
    30.                     uncle.color = 0;
    31.                     node.parent.parent.color = 1;
    32.                     node = node.parent.parent;
    33.                 } else {
    34.                     // Case 2: 叔叔节点是黑色，且当前节点是左子节点
    35.                     if (node == node.parent.left) {
    36.                         node = node.parent;
    37.                         rightRotate(node);
    38.                     }
    39.                     // Case 3: 叔叔节点是黑色，且当前节点是右子节点
    40.                     node.parent.color = 0;
    41.                     node.parent.parent.color = 1;
    42.                     leftRotate(node.parent.parent);
    43.                 }
    44.             }
    45.         }
    46.         root.color = 0;
    47.     }

    3.6删除节点

    1.  // 删除节点
    2.     public void delete(int key) {
    3.         RBNode z = search(key);
    4.         if (z == null) {
    5.             return;
    6.         }
    7.  
    8.         RBNode x, y;
    9.         if (z.left == null || z.right == null) {
    10.             y = z;
    11.         } else {
    12.             y = successor(z);
    13.         }
    14.  
    15.         if (y.left != null) {
    16.             x = y.left;
    17.         } else {
    18.             x = y.right;
    19.         }
    20.  
    21.         if (x != null) {
    22.             x.parent = y.parent;
    23.         }
    24.  
    25.         if (y.parent == null) {
    26.             root = x;
    27.         } else if (y == y.parent.left) {
    28.             y.parent.left = x;
    29.         } else {
    30.             y.parent.right = x;
    31.         }
    32.  
    33.         if (y != z) {
    34.             z.data = y.data;
    35.         }
    36.  
    37.         if (y.color == 0) {
    38.             fixDelete(x);
    39.         }
    40.     }
    41.  
    42.  
    43.  
    44.     // 查找节点
    45.     public RBNode search(int key) {
    46.         RBNode current = root;
    47.         while (current != null && current.data != key) {
    48.             if (key < current.data) {
    49.                 current = current.left;
    50.             } else {
    51.                 current = current.right;
    52.             }
    53.         }
    54.         return current;
    55.     }
    56.  
    57.     // 查找后继节点
    58.     private RBNode successor(RBNode x) {
    59.         if (x.right != null) {
    60.             RBNode current = x.right;
    61.             while (current.left != null) {
    62.                 current = current.left;
    63.             }
    64.             return current;
    65.         } else {
    66.             RBNode y = x.parent;
    67.             while (y != null && x == y.right) {
    68.                 x = y;
    69.                 y = y.parent;
    70.             }
    71.             return y;
    72.         }
    73.     }

    3.7删除后维持红黑树的平衡性

    1.   // 删除节点后修正红黑树平衡性
    2.     private void fixDelete(RBNode node) {
    3.         while (node != root && node.color == 0) {
    4.             if (node == node.parent.left) {
    5.                 RBNode brother = node.parent.right;
    6.                 if (brother.color == 1) {
    7.                     brother.color = 0;
    8.                     node.parent.color = 1;
    9.                     leftRotate(node.parent);
    10.                     brother = node.parent.right;
    11.                 }
    12.                 if (brother.left.color == 0 && brother.right.color == 0) {
    13.                     brother.color = 1;
    14.                     node = node.parent;
    15.                 } else {
    16.                     if (brother.right.color == 0) {
    17.                         brother.left.color = 0;
    18.                         brother.color = 1;
    19.                         rightRotate(brother);
    20.                         brother = node.parent.right;
    21.                     }
    22.                     brother.color = node.parent.color;
    23.                     node.parent.color = 0;
    24.                     brother.right.color = 0;
    25.                     leftRotate(node.parent);
    26.                     node = root;
    27.                 }
    28.             } else {
    29.                 RBNode brother = node.parent.left;
    30.                 if (brother.color == 1) {
    31.                     brother.color = 0;
    32.                     node.parent.color = 1;
    33.                     rightRotate(node.parent);
    34.                     brother = node.parent.left;
    35.                 }
    36.                 if (brother.right.color == 0 && brother.left.color == 0) {
    37.                     brother.color = 1;
    38.                     node = node.parent;
    39.                 } else {
    40.                     if (brother.left.color == 0) {
    41.                         brother.right.color = 0;
    42.                         brother.color = 1;
    43.                         leftRotate(brother);
    44.                         brother = node.parent.left;
    45.                     }
    46.                     brother.color = node.parent.color;
    47.                     node.parent.color = 0;
    48.                     brother.left.color = 0;
    49.                     rightRotate(node.parent);
    50.                     node = root;
    51.                 }
    52.             }
    53.         }
    54.         node.color = 0;
    55.     }

    4.完整代码

    1. // 红黑树节点类
    2. class RBNode {
    3.     int data;
    4.     RBNode parent;
    5.     RBNode left;
    6.     RBNode right;
    7.     int color;
    8.  
    9.     public RBNode(int data) {
    10.         this.data = data;
    11.         this.parent = null;
    12.         this.left = null;
    13.         this.right = null;
    14.         this.color = 1; // 默认节点为红色
    15.     }
    16. }
    17.  
    18. // 红黑树类
    19. class RedBlackTree {
    20.     private RBNode root;
    21.  
    22.     public RedBlackTree() {
    23.         root = null;
    24.     }
    25.  
    26.     // 左旋操作
    27.     private void leftRotate(RBNode x) {
    28.         RBNode y = x.right;
    29.         x.right = y.left;
    30.         if (y.left != null) {
    31.             y.left.parent = x;
    32.         }
    33.         y.parent = x.parent;
    34.         if (x.parent == null) {
    35.             root = y;
    36.         } else if (x == x.parent.left) {
    37.             x.parent.left = y;
    38.         } else {
    39.             x.parent.right = y;
    40.         }
    41.         y.left = x;
    42.         x.parent = y;
    43.     }
    44.  
    45.     // 右旋操作
    46.     private void rightRotate(RBNode y) {
    47.         RBNode x = y.left;
    48.         y.left = x.right;
    49.         if (x.right != null) {
    50.             x.right.parent = y;
    51.         }
    52.         x.parent = y.parent;
    53.         if (y.parent == null) {
    54.             root = x;
    55.         } else if (y == y.parent.left) {
    56.             y.parent.left = x;
    57.         } else {
    58.             y.parent.right = x;
    59.         }
    60.         x.right = y;
    61.         y.parent = x;
    62.     }
    63.  
    64.     // 插入节点
    65.     public void insert(int key) {
    66.         RBNode newNode = new RBNode(key);
    67.         RBNode current = root;
    68.         RBNode parent = null;
    69.  
    70.         while (current != null) {
    71.             parent = current;
    72.             if (key < current.data) {
    73.                 current = current.left;
    74.             } else {
    75.                 current = current.right;
    76.             }
    77.         }
    78.  
    79.         newNode.parent = parent;
    80.         if (parent == null) {
    81.             root = newNode;
    82.         } else if (key < parent.data) {
    83.             parent.left = newNode;
    84.         } else {
    85.             parent.right = newNode;
    86.         }
    87.  
    88.         // 调整红黑树
    89.         fixInsert(newNode);
    90.     }
    91.  
    92.     // 插入后修正红黑树平衡性
    93.     private void fixInsert(RBNode node) {
    94.         while (node.parent != null && node.parent.color == 1) {
    95.             // 当前节点的父节点是祖父节点的左子节点
    96.             if (node.parent == node.parent.parent.left) {
    97.                 RBNode uncle = node.parent.parent.right;
    98.                 // Case 1: 叔叔节点是红色
    99.                 if (uncle != null && uncle.color == 1) {
    100.                     node.parent.color = 0;
    101.                     uncle.color = 0;
    102.                     node.parent.parent.color = 1;
    103.                     node = node.parent.parent;
    104.                 } else {
    105.                     // Case 2: 叔叔节点是黑色，且当前节点是右子节点
    106.                     if (node == node.parent.right) {
    107.                         node = node.parent;
    108.                         leftRotate(node);
    109.                     }
    110.                     // Case 3: 叔叔节点是黑色，且当前节点是左子节点
    111.                     node.parent.color = 0;
    112.                     node.parent.parent.color = 1;
    113.                     rightRotate(node.parent.parent);
    114.                 }
    115.             } else {
    116.                 // 当前节点的父节点是祖父节点的右子节点
    117.                 RBNode uncle = node.parent.parent.left;
    118.                 // Case 1: 叔叔节点是红色
    119.                 if (uncle != null && uncle.color == 1) {
    120.                     node.parent.color = 0;
    121.                     uncle.color = 0;
    122.                     node.parent.parent.color = 1;
    123.                     node = node.parent.parent;
    124.                 } else {
    125.                     // Case 2: 叔叔节点是黑色，且当前节点是左子节点
    126.                     if (node == node.parent.left) {
    127.                         node = node.parent;
    128.                         rightRotate(node);
    129.                     }
    130.                     // Case 3: 叔叔节点是黑色，且当前节点是右子节点
    131.                     node.parent.color = 0;
    132.                     node.parent.parent.color = 1;
    133.                     leftRotate(node.parent.parent);
    134.                 }
    135.             }
    136.         }
    137.         root.color = 0;
    138.     }
    139.  
    140.     // 删除节点
    141.     public void delete(int key) {
    142.         RBNode z = search(key);
    143.         if (z == null) {
    144.             return;
    145.         }
    146.  
    147.         RBNode x, y;
    148.         if (z.left == null || z.right == null) {
    149.             y = z;
    150.         } else {
    151.             y = successor(z);
    152.         }
    153.  
    154.         if (y.left != null) {
    155.             x = y.left;
    156.         } else {
    157.             x = y.right;
    158.         }
    159.  
    160.         if (x != null) {
    161.             x.parent = y.parent;
    162.         }
    163.  
    164.         if (y.parent == null) {
    165.             root = x;
    166.         } else if (y == y.parent.left) {
    167.             y.parent.left = x;
    168.         } else {
    169.             y.parent.right = x;
    170.         }
    171.  
    172.         if (y != z) {
    173.             z.data = y.data;
    174.         }
    175.  
    176.         if (y.color == 0) {
    177.             fixDelete(x);
    178.         }
    179.     }
    180.  
    181.     // 删除节点后修正红黑树平衡性
    182.     private void fixDelete(RBNode node) {
    183.         while (node != root && node.color == 0) {
    184.             if (node == node.parent.left) {
    185.                 RBNode brother = node.parent.right;
    186.                 if (brother.color == 1) {
    187.                     brother.color = 0;
    188.                     node.parent.color = 1;
    189.                     leftRotate(node.parent);
    190.                     brother = node.parent.right;
    191.                 }
    192.                 if (brother.left.color == 0 && brother.right.color == 0) {
    193.                     brother.color = 1;
    194.                     node = node.parent;
    195.                 } else {
    196.                     if (brother.right.color == 0) {
    197.                         brother.left.color = 0;
    198.                         brother.color = 1;
    199.                         rightRotate(brother);
    200.                         brother = node.parent.right;
    201.                     }
    202.                     brother.color = node.parent.color;
    203.                     node.parent.color = 0;
    204.                     brother.right.color = 0;
    205.                     leftRotate(node.parent);
    206.                     node = root;
    207.                 }
    208.             } else {
    209.                 RBNode brother = node.parent.left;
    210.                 if (brother.color == 1) {
    211.                     brother.color = 0;
    212.                     node.parent.color = 1;
    213.                     rightRotate(node.parent);
    214.                     brother = node.parent.left;
    215.                 }
    216.                 if (brother.right.color == 0 && brother.left.color == 0) {
    217.                     brother.color = 1;
    218.                     node = node.parent;
    219.                 } else {
    220.                     if (brother.left.color == 0) {
    221.                         brother.right.color = 0;
    222.                         brother.color = 1;
    223.                         leftRotate(brother);
    224.                         brother = node.parent.left;
    225.                     }
    226.                     brother.color = node.parent.color;
    227.                     node.parent.color = 0;
    228.                     brother.left.color = 0;
    229.                     rightRotate(node.parent);
    230.                     node = root;
    231.                 }
    232.             }
    233.         }
    234.         node.color = 0;
    235.     }
    236.  
    237.     // 查找节点
    238.     public RBNode search(int key) {
    239.         RBNode current = root;
    240.         while (current != null && current.data != key) {
    241.             if (key < current.data) {
    242.                 current = current.left;
    243.             } else {
    244.                 current = current.right;
    245.             }
    246.         }
    247.         return current;
    248.     }
    249.  
    250.     // 查找后继节点
    251.     private RBNode successor(RBNode x) {
    252.         if (x.right != null) {
    253.             RBNode current = x.right;
    254.             while (current.left != null) {
    255.                 current = current.left;
    256.             }
    257.             return current;
    258.         } else {
    259.             RBNode y = x.parent;
    260.             while (y != null && x == y.right) {
    261.                 x = y;
    262.                 y = y.parent;
    263.             }
    264.             return y;
    265.         }
    266.     }
    267.  
    268.     // 修改节点
    269.     public void modify(int oldKey, int newKey) {
    270.         RBNode node = search(oldKey);
    271.         if (node != null) {
    272.             delete(oldKey);
    273.             insert(newKey);
    274.         }
    275.     }
    276.  
    277.  
    278.     // 中序遍历红黑树
    279.     private void inorderTraversal(RBNode node) {
    280.         if (node != null) {
    281.             inorderTraversal(node.left);
    282.             System.out.print(node.data + " ");
    283.             inorderTraversal(node.right);
    284.         }
    285.     }
    286.  
    287.     public void printTree() {
    288.         inorderTraversal(root);
    289.     }
    290. }
    291.  
    292.  
    293. public class Main {
    294.     public static void main(String[] args) {
    295.         RedBlackTree tree = new RedBlackTree();
    296.         tree.insert(10);
    297.         tree.insert(15);
    298.         tree.insert(13);
    299.         tree.insert(16);
    300.         tree.insert(5);
    301.         tree.insert(7);
    302.  
    303.         System.out.println("红黑树中序遍历结果：");
    304.         tree.printTree();
    305.     }
    306. }

  • 相关阅读:
    aspnetcore中aop的实现
    22年牛客网最全面的Java面试手册，助你金九银十轻松过关
    sql注入手法详解
    EffectiveC++-条款41：了解隐式接口和编译器多态
    点击化学修饰多肽：DBCO-PEG-YIGSR/RVG29/R8/CCK8肽
    入侵野草(IWO)优化算法（Matlab完整代码实现）
    精读大型网站架构：前端架构模块化的方法及困境，自研框架Trick
    双-(二苯胺基-苯基)-苯并[c]硫代咪唑聚集诱导发光微球/四苯基乙烯聚集诱导发光AIE微球
    Java每日笔试题错题分析（7）
    原型和原型链
  • 原文地址：https://blog.csdn.net/m0_74749208/article/details/133914499