Java-红黑树

转x33g5p2x  于2022-02-07 转载在 Java  
字(12.5k)|赞(0)|评价(0)|浏览(471)

学习注意事项

  1. 必须会二叉搜索树
  2. 必须会AVL树
  3. 必须知道什么是L , R ,RL , LR 这些旋转概念

以上概念,我博客里都有自行寻找…下面就开始红黑树的讲解了

介绍

红黑树必须满足的5个条件

和AVL树的比较
AVL树是一棵严格的平衡树，它所有的子树都满足二叉平衡树的定义。因此AVL树高被严格控制在(-1 ,1,+1)，因此AVL树的查找比较高效。但AVL树插入、删除结点后旋转的次数比红黑树多。红黑树用非严格的平衡来降低插入删除时旋转的次数。因此，如果你的业务中查找远远多于插入、删除，那选AVL树； 如果查找、插入、删除频率差不多，那么选择红黑树。

插入过程

默认插入的结点为红色。为何？
因为红黑树中黑节点至少是红节点的两倍，因此插入节点的父节点为黑色的概率较大，而此时并不需要作任何调整，因此效率较高。

1. 父为黑

插入后无需任何操作。由于黑节点个数至少为红节点的两倍，因此父为黑的情况较多，而这种情况在插入后无需任何调整，这就是红黑树比AVL树插入效率高的原因！

2. 父为红

父为红的情况破坏了红黑树的性质，此时需要根据叔叔的颜色来做不同的处理。

2.1叔叔为红

此时很简单，只需交换爸爸、叔叔和爷爷的颜色即可。
此时若爷爷节点和太爷爷节点颜色相同，再以爷爷节点为起始节点，进行刚才相同的操作，即：根据爷爷的兄弟颜色做相应的操作。

2.2叔叔为黑

此时较为复杂，分如下四种情况：

2.2.1爸爸在左、叔叔在右、我在左

以爸爸为根节点，进行一次R旋转。

2.2.2爸爸在左、叔叔在右、我在右

先以新为根节点，进行一次L旋转
再以新为根节点，进行一次R旋转

2.2.3叔叔在左、爸爸在右、我在左

先以新为根节点，进行一次R旋转；
再以新为根节点，进行一次L旋转。

2.2.4叔叔在左、爸爸在右、我在右

以爸爸为根节点，进行一次L旋转。

删除过程

  1. 实际删除节点要么是叶子节点，要么有且仅有一个左孩子；
  2. 若为叶子节点，必为红色；
  3. 若实际删除节点还有孩子，则该必为左孩子；
    a）若左孩子为红色，则实际删除节点必为黑色；
    b）若左孩子为黑色，则实际删除节点红黑均可以。

约定

  1. 蓝色箭头：表示判定点
  2. 在删除操作开始前，蓝色箭头首先指向实际删除节点。
  3. 『实际删除节点』在图中以『父』表示。

1. 父为红色(待删节点为红)

直接删除父节点即可：

2. 父为黑子为红(待删节点为黑)

待删节点子节点为红+左孩子,用子节点覆盖父节点，并保持父节点的颜色：

3. 父为黑子为黑(待删节点和子节点均为黑)

那么就需要根据叔叔的颜色进行不同逻辑的删除

3.1. 叔叔为红

注意: 叔叔为红，则爷爷必为黑！

3.1.1 父在左 叔在右
  1. 子节点覆盖父节点
  2. 进行一次左旋

3.1.2 父在右 叔在左
  1. 子节点覆盖父节点
  2. 进行一次右旋

3.2. 叔叔为黑

注意; 叔叔、爸爸都为黑，那爷爷颜色就不确定了！

3.2.1 祖父红两个侄子黑

以下两种情况操作一致：
5. 子覆盖父（删除）
6. 交换祖父和叔叔的颜色。

3.2.1.1父在左叔在右

3.2.1.2父在右叔在左

3.2.2祖父黑两个侄子黑

以下两种情况操作一致：

  1. 祖父染成子节点的颜色；
  2. 子节点染成黑色；
  3. 叔叔染成红色
3.2.2.1 父在左叔在右

3.2.2.2父在右叔在左

3.2.3祖父颜色随意至少有一个红侄
3.2.3.1红侄为左左（叔左、红侄左）
  1. 红侄进行一次右旋
  2. 红侄染成黑色
  3. 交换叔叔和祖父的颜色

3.2.3.2红侄为左右（叔左、红侄右）
  1. 红侄进行一次右旋+左旋
  2. 红侄染成父节点颜色；
  3. 父节点染成黑色

3.2.3.3 红侄为右左（叔右、红侄左）
  1. 红侄进行一次右旋+左旋
  2. 红侄染成父节点颜色；
  3. 父节点染成黑色；

3.2.3.4 红侄为右右（叔右、红侄右）
  1. 红侄进行一次左旋
  2. 叔叔染成父节点颜色；
  3. 红侄染成黑色；

红黑树动态可视化网站

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

红黑树参考代码

  1. package com.tree.rbtree;
  3. /**
  4.  * Java 语言: 红黑树
  5.  *
  6.  * @author skywang
  7.  * @date 2013/11/07
  8.  */
  10. public class RBTree<T extends Comparable<T>> {
  12.     private RBTNode<T> mRoot;    // 根结点
  14.     private static final boolean RED   = false;
  15.     private static final boolean BLACK = true;
  17.     public class RBTNode<T extends Comparable<T>> {
  18.         boolean color;        // 颜色
  19.         T key;                // 关键字(键值)
  20.         RBTNode<T> left;    // 左孩子
  21.         RBTNode<T> right;    // 右孩子
  22.         RBTNode<T> parent;    // 父结点
  24.         public RBTNode(T key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right) {
  25.             this.key = key;
  26.             this.color = color;
  27.             this.parent = parent;
  28.             this.left = left;
  29.             this.right = right;
  30.         }
  32.         public T getKey() {
  33.             return key;
  34.         }
  36.         @Override
  37.         public String toString() {
  38.             return ""+key+(this.color==RED?"(R)":"B");
  39.         }
  40.     }
  42.     public RBTree() {
  43.         mRoot=null;
  44.     }
  46.     private RBTNode<T> parentOf(RBTNode<T> node) {
  47.         return node!=null ? node.parent : null;
  48.     }
  49.     private boolean colorOf(RBTNode<T> node) {
  50.         return node!=null ? node.color : BLACK;
  51.     }
  52.     private boolean isRed(RBTNode<T> node) {
  53.         return ((node!=null)&&(node.color==RED)) ? true : false;
  54.     }
  55.     private boolean isBlack(RBTNode<T> node) {
  56.         return !isRed(node);
  57.     }
  58.     private void setBlack(RBTNode<T> node) {
  59.         if (node!=null) {
  60.             node.color = BLACK;
  61.         }
  62.     }
  63.     private void setRed(RBTNode<T> node) {
  64.         if (node!=null) {
  65.             node.color = RED;
  66.         }
  67.     }
  68.     private void setParent(RBTNode<T> node, RBTNode<T> parent) {
  69.         if (node!=null) {
  70.             node.parent = parent;
  71.         }
  72.     }
  73.     private void setColor(RBTNode<T> node, boolean color) {
  74.         if (node!=null) {
  75.             node.color = color;
  76.         }
  77.     }
  79.     /*
  80.      * 前序遍历"红黑树"
  81.      */
  82.     private void preOrder(RBTNode<T> tree) {
  83.         if(tree != null) {
  84.             System.out.print(tree.key+" ");
  85.             preOrder(tree.left);
  86.             preOrder(tree.right);
  87.         }
  88.     }
  90.     public void preOrder() {
  91.         preOrder(mRoot);
  92.     }
  94.     /*
  95.      * 中序遍历"红黑树"
  96.      */
  97.     private void inOrder(RBTNode<T> tree) {
  98.         if(tree != null) {
  99.             inOrder(tree.left);
  100.             System.out.print(tree.key+" ");
  101.             inOrder(tree.right);
  102.         }
  103.     }
  105.     public void inOrder() {
  106.         inOrder(mRoot);
  107.     }
  109.     /*
  110.      * 后序遍历"红黑树"
  111.      */
  112.     private void postOrder(RBTNode<T> tree) {
  113.         if(tree != null)
  114.         {
  115.             postOrder(tree.left);
  116.             postOrder(tree.right);
  117.             System.out.print(tree.key+" ");
  118.         }
  119.     }
  121.     public void postOrder() {
  122.         postOrder(mRoot);
  123.     }
  125.     /*
  126.      * (递归实现)查找"红黑树x"中键值为key的节点
  127.      */
  128.     private RBTNode<T> search(RBTNode<T> x, T key) {
  129.         if (x==null) {
  130.             return x;
  131.         }
  133.         int cmp = key.compareTo(x.key);
  134.         if (cmp < 0) {
  135.             return search(x.left, key);
  136.         } else if (cmp > 0) {
  137.             return search(x.right, key);
  138.         } else {
  139.             return x;
  140.         }
  141.     }
  143.     public RBTNode<T> search(T key) {
  144.         return search(mRoot, key);
  145.     }
  147.     /*
  148.      * (非递归实现)查找"红黑树x"中键值为key的节点
  149.      */
  150.     private RBTNode<T> iterativeSearch(RBTNode<T> x, T key) {
  151.         while (x!=null) {
  152.             int cmp = key.compareTo(x.key);
  154.             if (cmp < 0) {
  155.                 x = x.left;
  156.             } else if (cmp > 0) {
  157.                 x = x.right;
  158.             } else {
  159.                 return x;
  160.             }
  161.         }
  163.         return x;
  164.     }
  166.     public RBTNode<T> iterativeSearch(T key) {
  167.         return iterativeSearch(mRoot, key);
  168.     }
  170.     /*
  171.      * 查找最小结点：返回tree为根结点的红黑树的最小结点。
  172.      */
  173.     private RBTNode<T> minimum(RBTNode<T> tree) {
  174.         if (tree == null) {
  175.             return null;
  176.         }
  178.         while(tree.left != null) {
  179.             tree = tree.left;
  180.         }
  181.         return tree;
  182.     }
  184.     public T minimum() {
  185.         RBTNode<T> p = minimum(mRoot);
  186.         if (p != null) {
  187.             return p.key;
  188.         }
  190.         return null;
  191.     }
  193.     /*
  194.      * 查找最大结点：返回tree为根结点的红黑树的最大结点。
  195.      */
  196.     private RBTNode<T> maximum(RBTNode<T> tree) {
  197.         if (tree == null) {
  198.             return null;
  199.         }
  201.         while(tree.right != null) {
  202.             tree = tree.right;
  203.         }
  204.         return tree;
  205.     }
  207.     public T maximum() {
  208.         RBTNode<T> p = maximum(mRoot);
  209.         if (p != null) {
  210.             return p.key;
  211.         }
  213.         return null;
  214.     }
  216.     /*
  217.      * 找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。
  218.      */
  219.     public RBTNode<T> successor(RBTNode<T> x) {
  220.         // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
  221.         if (x.right != null) {
  222.             return minimum(x.right);
  223.         }
  225.         // 如果x没有右孩子。则x有以下两种可能：
  226.         // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
  227.         // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
  228.         RBTNode<T> y = x.parent;
  229.         while ((y!=null) && (x==y.right)) {
  230.             x = y;
  231.             y = y.parent;
  232.         }
  234.         return y;
  235.     }
  237.     /*
  238.      * 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。
  239.      */
  240.     public RBTNode<T> predecessor(RBTNode<T> x) {
  241.         // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
  242.         if (x.left != null) {
  243.             return maximum(x.left);
  244.         }
  246.         // 如果x没有左孩子。则x有以下两种可能：
  247.         // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
  248.         // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
  249.         RBTNode<T> y = x.parent;
  250.         while ((y!=null) && (x==y.left)) {
  251.             x = y;
  252.             y = y.parent;
  253.         }
  255.         return y;
  256.     }
  258.     /*
  259.      * 对红黑树的节点(x)进行左旋转
  260.      *
  261.      * 左旋示意图(对节点x进行左旋)：
  262.      *      px                              px
  263.      *     /                               /
  264.      *    x                               y
  265.      *   /  \      --(左旋)-.           / \                #
  266.      *  lx   y                          x  ry
  267.      *     /   \                       /  \
  268.      *    ly   ry                     lx  ly
  269.      *
  270.      *
  271.      */
  272.     private void leftRotate(RBTNode<T> x) {
  273.         // 设置x的右孩子为y
  274.         RBTNode<T> y = x.right;
  276.         // 将 “y的左孩子” 设为 “x的右孩子”；
  277.         // 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”
  278.         x.right = y.left;
  279.         if (y.left != null) {
  280.             y.left.parent = x;
  281.         }
  283.         // 将 “x的父亲” 设为 “y的父亲”
  284.         y.parent = x.parent;
  286.         if (x.parent == null) {
  287.             this.mRoot = y;            // 如果 “x的父亲” 是空节点，则将y设为根节点
  288.         } else {
  289.             if (x.parent.left == x) {
  290.                 x.parent.left = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
  291.             } else {
  292.                 x.parent.right = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
  293.             }
  294.         }
  296.         // 将 “x” 设为 “y的左孩子”
  297.         y.left = x;
  298.         // 将 “x的父节点” 设为 “y”
  299.         x.parent = y;
  300.     }
  302.     /*
  303.      * 对红黑树的节点(y)进行右旋转
  304.      *
  305.      * 右旋示意图(对节点y进行左旋)：
  306.      *            py                               py
  307.      *           /                                /
  308.      *          y                                x
  309.      *         /  \      --(右旋)-.            /  \                     #
  310.      *        x   ry                           lx   y
  311.      *       / \                                   / \                   #
  312.      *      lx  rx                                rx  ry
  313.      *
  314.      */
  315.     private void rightRotate(RBTNode<T> y) {
  316.         // 设置x是当前节点的左孩子。
  317.         RBTNode<T> x = y.left;
  319.         // 将 “x的右孩子” 设为 “y的左孩子”；
  320.         // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
  321.         y.left = x.right;
  322.         if (x.right != null) {
  323.             x.right.parent = y;
  324.         }
  326.         // 将 “y的父亲” 设为 “x的父亲”
  327.         x.parent = y.parent;
  329.         if (y.parent == null) {
  330.             this.mRoot = x;            // 如果 “y的父亲” 是空节点，则将x设为根节点
  331.         } else {
  332.             if (y == y.parent.right) {
  333.                 y.parent.right = x;    // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
  334.             } else {
  335.                 y.parent.left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
  336.             }
  337.         }
  339.         // 将 “y” 设为 “x的右孩子”
  340.         x.right = y;
  342.         // 将 “y的父节点” 设为 “x”
  343.         y.parent = x;
  344.     }
  346.     /*
  347.      * 红黑树插入修正函数
  348.      *
  349.      * 在向红黑树中插入节点之后(失去平衡)，再调用该函数；
  350.      * 目的是将它重新塑造成一颗红黑树。
  351.      *
  352.      * 参数说明：
  353.      *     node 插入的结点        // 对应《算法导论》中的z
  354.      */
  355.     private void insertFixUp(RBTNode<T> node) {
  356.         RBTNode<T> parent, gparent;
  358.         // 若“父节点存在，并且父节点的颜色是红色”
  359.         while (((parent = parentOf(node))!=null) && isRed(parent)) {
  360.             gparent = parentOf(parent);
  362.             //若“父节点”是“祖父节点的左孩子”
  363.             if (parent == gparent.left) {
  364.                 // Case 1条件：叔叔节点是红色
  365.                 RBTNode<T> uncle = gparent.right;
  366.                 if ((uncle!=null) && isRed(uncle)) {
  367.                     setBlack(uncle);
  368.                     setBlack(parent);
  369.                     setRed(gparent);
  370.                     node = gparent;
  371.                     continue;
  372.                 }
  374.                 // Case 2条件：叔叔是黑色，且当前节点是右孩子
  375.                 if (parent.right == node) {
  376.                     RBTNode<T> tmp;
  377.                     leftRotate(parent);
  378.                     tmp = parent;
  379.                     parent = node;
  380.                     node = tmp;
  381.                 }
  383.                 // Case 3条件：叔叔是黑色，且当前节点是左孩子。
  384.                 setBlack(parent);
  385.                 setRed(gparent);
  386.                 rightRotate(gparent);
  387.             } else {    //若“z的父节点”是“z的祖父节点的右孩子”
  388.                 // Case 1条件：叔叔节点是红色
  389.                 RBTNode<T> uncle = gparent.left;
  390.                 if ((uncle!=null) && isRed(uncle)) {
  391.                     setBlack(uncle);
  392.                     setBlack(parent);
  393.                     setRed(gparent);
  394.                     node = gparent;
  395.                     continue;
  396.                 }
  398.                 // Case 2条件：叔叔是黑色，且当前节点是左孩子
  399.                 if (parent.left == node) {
  400.                     RBTNode<T> tmp;
  401.                     rightRotate(parent);
  402.                     tmp = parent;
  403.                     parent = node;
  404.                     node = tmp;
  405.                 }
  407.                 // Case 3条件：叔叔是黑色，且当前节点是右孩子。
  408.                 setBlack(parent);
  409.                 setRed(gparent);
  410.                 leftRotate(gparent);
  411.             }
  412.         }
  414.         // 将根节点设为黑色
  415.         setBlack(this.mRoot);
  416.     }
  418.     /*
  419.      * 将结点插入到红黑树中
  420.      *
  421.      * 参数说明：
  422.      *     node 插入的结点        // 对应《算法导论》中的node
  423.      */
  424.     private void insert(RBTNode<T> node) {
  425.         int cmp;
  426.         RBTNode<T> y = null;
  427.         RBTNode<T> x = this.mRoot;
  429.         // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。
  430.         while (x != null) {
  431.             y = x;
  432.             cmp = node.key.compareTo(x.key);
  433.             if (cmp < 0) {
  434.                 x = x.left;
  435.             } else {
  436.                 x = x.right;
  437.             }
  438.         }
  440.         node.parent = y;
  441.         if (y!=null) {
  442.             cmp = node.key.compareTo(y.key);
  443.             if (cmp < 0) {
  444.                 y.left = node;
  445.             } else {
  446.                 y.right = node;
  447.             }
  448.         } else {
  449.             this.mRoot = node;
  450.         }
  452.         // 2. 设置节点的颜色为红色
  453.         node.color = RED;
  455.         // 3. 将它重新修正为一颗二叉查找树
  456.         insertFixUp(node);
  457.     }
  459.     /*
  460.      * 新建结点(key)，并将其插入到红黑树中
  461.      *
  462.      * 参数说明：
  463.      *     key 插入结点的键值
  464.      */
  465.     public void insert(T key) {
  466.         RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null);
  468.         // 如果新建结点失败，则返回。
  469.         if (node != null) {
  470.             insert(node);
  471.         }
  472.     }
  474.     /*
  475.      * 红黑树删除修正函数
  476.      *
  477.      * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；
  478.      * 目的是将它重新塑造成一颗红黑树。
  479.      *
  480.      * 参数说明：
  481.      *     node 待修正的节点
  482.      */
  483.     private void removeFixUp(RBTNode<T> node, RBTNode<T> parent) {
  484.         RBTNode<T> other;
  486.         while ((node==null || isBlack(node)) && (node != this.mRoot)) {
  487.             if (parent.left == node) {
  488.                 other = parent.right;
  489.                 if (isRed(other)) {
  490.                     // Case 1: x的兄弟w是红色的
  491.                     setBlack(other);
  492.                     setRed(parent);
  493.                     leftRotate(parent);
  494.                     other = parent.right;
  495.                 }
  497.                 if ((other.left==null || isBlack(other.left)) &&
  498.                         (other.right==null || isBlack(other.right))) {
  499.                     // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
  500.                     setRed(other);
  501.                     node = parent;
  502.                     parent = parentOf(node);
  503.                 } else {
  505.                     if (other.right==null || isBlack(other.right)) {
  506.                         // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
  507.                         setBlack(other.left);
  508.                         setRed(other);
  509.                         rightRotate(other);
  510.                         other = parent.right;
  511.                     }
  512.                     // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
  513.                     setColor(other, colorOf(parent));
  514.                     setBlack(parent);
  515.                     setBlack(other.right);
  516.                     leftRotate(parent);
  517.                     node = this.mRoot;
  518.                     break;
  519.                 }
  520.             } else {
  522.                 other = parent.left;
  523.                 if (isRed(other)) {
  524.                     // Case 1: x的兄弟w是红色的
  525.                     setBlack(other);
  526.                     setRed(parent);
  527.                     rightRotate(parent);
  528.                     other = parent.left;
  529.                 }
  531.                 if ((other.left==null || isBlack(other.left)) &&
  532.                         (other.right==null || isBlack(other.right))) {
  533.                     // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的
  534.                     setRed(other);
  535.                     node = parent;
  536.                     parent = parentOf(node);
  537.                 } else {
  539.                     if (other.left==null || isBlack(other.left)) {
  540.                         // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。
  541.                         setBlack(other.right);
  542.                         setRed(other);
  543.                         leftRotate(other);
  544.                         other = parent.left;
  545.                     }
  547.                     // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。
  548.                     setColor(other, colorOf(parent));
  549.                     setBlack(parent);
  550.                     setBlack(other.left);
  551.                     rightRotate(parent);
  552.                     node = this.mRoot;
  553.                     break;
  554.                 }
  555.             }
  556.         }
  558.         if (node!=null) {
  559.             setBlack(node);
  560.         }
  561.     }
  563.     /*
  564.      * 删除结点(node)，并返回被删除的结点
  565.      *
  566.      * 参数说明：
  567.      *     node 删除的结点
  568.      */
  569.     private void 
  570.     remove(RBTNode<T> node) {
  571.         RBTNode<T> child, parent;
  572.         boolean color;
  574.         // 被删除节点的"左右孩子都不为空"的情况。
  575.         if ( (node.left!=null) && (node.right!=null) ) {
  576.             // 被删节点的后继节点。(称为"取代节点")
  577.             // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。
  578.             RBTNode<T> replace = node;
  580.             // 获取后继节点
  581.             replace = replace.right;
  582.             while (replace.left != null) {
  583.                 replace = replace.left;
  584.             }
  586.             // "node节点"不是根节点(只有根节点不存在父节点)
  587.             if (parentOf(node)!=null) {
  588.                 if (parentOf(node).left == node) {
  589.                     parentOf(node).left = replace;
  590.                 } else {
  591.                     parentOf(node).right = replace;
  592.                 }
  593.             } else {
  594.                 // "node节点"是根节点，更新根节点。
  595.                 this.mRoot = replace;
  596.             }
  598.             // child是"取代节点"的右孩子，也是需要"调整的节点"。
  599.             // "取代节点"肯定不存在左孩子！因为它是一个后继节点。
  600.             child = replace.right;
  601.             parent = parentOf(replace);
  602.             // 保存"取代节点"的颜色
  603.             color = colorOf(replace);
  605.             // "被删除节点"是"它的后继节点的父节点"
  606.             if (parent == node) {
  607.                 parent = replace;
  608.             } else {
  609.                 // child不为空
  610.                 if (child!=null) {
  611.                     setParent(child, parent);
  612.                 }
  613.                 parent.left = child;
  615.                 replace.right = node.right;
  616.                 setParent(node.right, replace);
  617.             }
  619.             replace.parent = node.parent;
  620.             replace.color = node.color;
  621.             replace.left = node.left;
  622.             node.left.parent = replace;
  624.             if (color == BLACK) {
  625.                 removeFixUp(child, parent);
  626.             }
  628.             node = null;
  629.             return ;
  630.         }
  632.         if (node.left !=null) {
  633.             child = node.left;
  634.         } else {
  635.             child = node.right;
  636.         }
  638.         parent = node.parent;
  639.         // 保存"取代节点"的颜色
  640.         color = node.color;
  642.         if (child!=null) {
  643.             child.parent = parent;
  644.         }
  646.         // "node节点"不是根节点
  647.         if (parent!=null) {
  648.             if (parent.left == node) {
  649.                 parent.left = child;
  650.             } else {
  651.                 parent.right = child;
  652.             }
  653.         } else {
  654.             this.mRoot = child;
  655.         }
  657.         if (color == BLACK) {
  658.             removeFixUp(child, parent);
  659.         }
  660.         node = null;
  661.     }
  663.     /*
  664.      * 删除结点(z)，并返回被删除的结点
  665.      *
  666.      * 参数说明：
  667.      *     tree 红黑树的根结点
  668.      *     z 删除的结点
  669.      */
  670.     public void remove(T key) {
  671.         RBTNode<T> node;
  673.         if ((node = search(mRoot, key)) != null) {
  674.             remove(node);
  675.         }
  676.     }
  678.     /*
  679.      * 销毁红黑树
  680.      */
  681.     private void destroy(RBTNode<T> tree) {
  682.         if (tree==null) {
  683.             return ;
  684.         }
  686.         if (tree.left != null) {
  687.             destroy(tree.left);
  688.         }
  689.         if (tree.right != null) {
  690.             destroy(tree.right);
  691.         }
  693.         tree=null;
  694.     }
  696.     public void clear() {
  697.         destroy(mRoot);
  698.         mRoot = null;
  699.     }
  701.     /*
  702.      * 打印"红黑树"
  703.      *
  704.      * key        -- 节点的键值
  705.      * direction  --  0，表示该节点是根节点;
  706.      *               -1，表示该节点是它的父结点的左孩子;
  707.      *                1，表示该节点是它的父结点的右孩子。
  708.      */
  709.     private void print(RBTNode<T> tree, T key, int direction) {
  711.         if(tree != null) {
  713.             if(direction==0)    // tree是根节点
  714.             {
  715.                 System.out.printf("%2d(B) is root\n", tree.key);
  716.             } else                // tree是分支节点
  717.             {
  718.                 System.out.printf("%2d(%s) is %2d's %6s child\n", tree.key, isRed(tree)?"R":"B", key, direction==1?"right" : "left");
  719.             }
  721.             print(tree.left, tree.key, -1);
  722.             print(tree.right,tree.key,  1);
  723.         }
  724.     }
  726.     public void print() {
  727.         if (mRoot != null) {
  728.             print(mRoot, mRoot.key, 0);
  729.         }
  730.     }
  731. }

点赞 -收藏-关注-便于以后复习和收到最新内容有其他问题在评论区讨论-或者私信我-收到会在第一时间回复如有侵权，请私信联系我感谢,配合,希望我的努力对你有帮助^_^

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/weixin_45203607/article/details/122727513

内容来源于网络，如有侵权，请联系作者删除！

Java数据结构算法红黑树

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多

    目录

    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com