devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java数据结构——树——红黑树_java 中树相关的知识点结合源码分析

作者：不正经 | 2024-03-09 10:43:21

赞

踩

java 中树相关的知识点结合源码分析

目录

一、简介

二、实现思路

2.1 插入节点

插入总结：通过对以上源码的解读，我们可以得出：

2.2 删除节点

删除总结：通过对上面源码的解读，我们可以得出：

三、代码仿现

   注：在开始阅读此文章之前，是默认读者掌握了节点的旋转规则，如果对旋转规则不了解的同学，可以先看我的这篇博客

    我把删除和插入节点用xmind进行了总结，上传到了此博客

一、简介

      红黑树 (Red Black Tree) 是一种二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

      它是在1972年由 Rudolf Bayer 发明的，当时被称为平衡二叉B树 (symmetric binary B-trees)。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

       红黑树和其他二叉查找树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的性质，从而获得较高的查找性能。

       它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的：它可以在 O(log n) 时间内做查找，插入和删除，这里的 n 是树中元素的数目。

                                                                                                                                                                       ——百度百科

二、实现思路

 在Java中很多对象比如TreeMap,HashMap（1.8）以及Linux虚拟内存的管理，都使用了红黑树的数据结构

想要理解红黑树，需要先知道红黑树是什么？它有什么特点？

红黑树是一种含有红黑结点并能自平衡的二叉查找树。

它必须满足下面性质：

  • 性质1：每个节点要么是黑色，要么是红色。
  • 性质2：根节点是黑色。
  • 性质3：每个叶子节点（NIL）是黑色。
  • 性质4：每个红色结点的两个子结点一定都是黑色。
  • 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

这里我通过TreeMap的源码来和大家一起理解这个神秘的红黑树

2.1 插入节点

  1. /**
  2.      * Associates the specified value with the specified key in this map.
  3.      * If the map previously contained a mapping for the key, the old
  4.      * value is replaced.
  5.      *
  6.      * @param key key with which the specified value is to be associated
  7.      * @param value value to be associated with the specified key
  8.      *
  9.      * @return the previous value associated with {@code key}, or
  10.      *         {@code null} if there was no mapping for {@code key}.
  11.      *         (A {@code null} return can also indicate that the map
  12.      *         previously associated {@code null} with {@code key}.)
  13.      * @throws ClassCastException if the specified key cannot be compared
  14.      *         with the keys currently in the map
  15.      * @throws NullPointerException if the specified key is null
  16.      *         and this map uses natural ordering, or its comparator
  17.      *         does not permit null keys
  18.      */
  19.     public V put(K key, V value) {
  20.         Entry<K,V> t = root;
  21.         if (t == null) {
  22.             compare(key, key); // type (and possibly null) check
  23.  
  24.             root = new Entry<>(key, value, null);
  25.             size = 1;
  26.             modCount++;
  27.             return null;
  28.         }
  29.         int cmp;
  30.         Entry<K,V> parent;
  31.         // split comparator and comparable paths
  32.         Comparator<? super K> cpr = comparator;
  33.         // 找到待添加节点的父节点并修改value
  34.         if (cpr != null) {
  35.             do {
  36.                 parent = t;
  37.                 cmp = cpr.compare(key, t.key);
  38.                 if (cmp < 0)
  39.                     t = t.left;
  40.                 else if (cmp > 0)
  41.                     t = t.right;
  42.                 else
  43.                     return t.setValue(value);
  44.             } while (t != null);
  45.         }
  46.         else {
  47.             if (key == null)
  48.                 throw new NullPointerException();
  49.             @SuppressWarnings("unchecked")
  50.                 Comparable<? super K> k = (Comparable<? super K>) key;
  51.             do {
  52.                 parent = t;
  53.                 cmp = k.compareTo(t.key);
  54.                 if (cmp < 0)
  55.                     t = t.left;
  56.                 else if (cmp > 0)
  57.                     t = t.right;
  58.                 else
  59.                     return t.setValue(value);
  60.             } while (t != null);
  61.         }
  62.         // 创建待添加节点并给其赋予相关的父节点
  63.         Entry<K,V> e = new Entry<>(key, value, parent);
  64.         // 将创建出来的节点放入合适的位置
  65.         if (cmp < 0)
  66.             parent.left = e;
  67.         else
  68.             parent.right = e;
  69.         // 平衡红黑树的一系列操作（重点）
  70.         fixAfterInsertion(e);
  71.         // 树中的条目数
  72.         size++;
  73.         // 树的结构修改数
  74.         modCount++;
  75.         return null;
  76.     }
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86. /** From CLR */
  87.     private void fixAfterInsertion(Entry<K,V> x) {
  88.         // 新插入的节点颜色默认为红色
  89.         x.color = RED;
  90.  
  91.         // 如果新插入节点的父节点颜色为红色 违反了性质4
  92.         while (x != null && x != root && x.parent.color == RED) {
  93.             // 如果新插入节点的父节点为其父节点的左子节点时
  94.             if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
  95.                 // 获取当前插入节点的叔叔节点
  96.                 Entry<K,V> y = rightOf(parentOf(parentOf(x)));
  97.                 // 如果此叔叔节点的颜色为红色
  98.                 if (colorOf(y) == RED) {
  99.                     // 将插入节点的父节点和叔叔节点的颜色设置为黑色
  100.                     setColor(parentOf(x), BLACK);
  101.                     setColor(y, BLACK);
  102.                     // 将插入节点的祖父节点的颜色设置为红色
  103.                     setColor(parentOf(parentOf(x)), RED);
  104.                     // 将祖父节点设置为插入的节点
  105.                     x = parentOf(parentOf(x));
  106.                 // 如果叔叔节点的颜色为黑色
  107.                 } else {
  108.                     // 如果当前插入节点是其父节点的右子节点时
  109.                     if (x == rightOf(parentOf(x))) {
  110.                         // 将两节点进行左旋操作
  111.                         x = parentOf(x);
  112.                         rotateLeft(x);
  113.                     }
  114.                     // 将新插入节点的父节点的颜色设置为黑色
  115.                     setColor(parentOf(x), BLACK);
  116.                     // 并将其祖父节点的颜色设置为红色
  117.                     setColor(parentOf(parentOf(x)), RED);
  118.                     // 将其祖父节点与其左子节点进行右旋
  119.                     rotateRight(parentOf(parentOf(x)));
  120.                 }
  121.             // 如果新插入节点的父节点为其父节点的右子节点时
  122.             } else {
  123.                 // 找到其叔叔节点
  124.                 Entry<K,V> y = leftOf(parentOf(parentOf(x)));
  125.                 // 如果当前叔叔节点为红色
  126.                 if (colorOf(y) == RED) {
  127.                     // 将新插入节点的父节点和其叔叔节点设置为黑色
  128.                     setColor(parentOf(x), BLACK);
  129.                     setColor(y, BLACK);
  130.                     // 并将其祖父节点设置为红色 并将祖父节点设置为新插入的节点
  131.                     setColor(parentOf(parentOf(x)), RED);
  132.                     x = parentOf(parentOf(x));
  133.                 } else {
  134.                     // 如果当前叔叔节点为黑色 并且插入节点为其父节点的左子节点
  135.                     if (x == leftOf(parentOf(x))) {
  136.                         // 右旋其父节点和插入节点
  137.                         x = parentOf(x);
  138.                         rotateRight(x);
  139.                     }
  140.                     // 将其父节点的颜色设置为黑色 并将其祖父节点的颜色设置为红色再进行左旋
  141.                     setColor(parentOf(x), BLACK);
  142.                     setColor(parentOf(parentOf(x)), RED);
  143.                     rotateLeft(parentOf(parentOf(x)));
  144.                 }
  145.             }
  146.         }
  147.         // 设置根节点的颜色为黑色
  148.         root.color = BLACK;
  149.     }
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
  157.  
  158.  
  159. /** From CLR */
  160.     private void rotateLeft(Entry<K,V> p) {
  161.         if (p != null) {
  162.             // 选中新插入的节点
  163.             Entry<K,V> r = p.right;
  164.             // 将其父节点的右子节点赋值为新插入节点的左子节点
  165.             p.right = r.left;
  166.             if (r.left != null)
  167.                 // 将新插入节点的左子节点的父节点设置为新插入节点的父节点
  168.                 r.left.parent = p;
  169.             // 将新插入节点的父节点设置为祖父节点
  170.             r.parent = p.parent;
  171.             // 判断当前祖父节点是否为根节点
  172.             if (p.parent == null)
  173.                 // 将根节点设置为新插入的节点
  174.                 root = r;
  175.             // 如果当前祖父节点的左子节点是其新插入节点的父节点
  176.             else if (p.parent.left == p)
  177.                 // 将当前祖父节点的左子节点设置为新插入的节点
  178.                 p.parent.left = r;
  179.             else
  180.                 // 将当前祖父节点的右子节点设置为新插入的节点
  181.                 p.parent.right = r;
  182.             // 将当前新插入节点的左子节点设置为其父节点
  183.             r.left = p;
  184.             // 将旋转后父节点的父节点设置为当前新插入的节点
  185.             p.parent = r;
  186.         }
  187.     }
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  /** From CLR */
  197.     // 操作方式与左旋相同，方向不一样而已
  198.     private void rotateRight(Entry<K,V> p) {
  199.         if (p != null) {
  200.             Entry<K,V> l = p.left;
  201.             p.left = l.right;
  202.             if (l.right != null) l.right.parent = p;
  203.             l.parent = p.parent;
  204.             if (p.parent == null)
  205.                 root = l;
  206.             else if (p.parent.right == p)
  207.                 p.parent.right = l;
  208.             else p.parent.left = l;
  209.             l.right = p;
  210.             p.parent = l;
  211.         }
  212.     }

通过对以上源码的解读，我们可以得出：

新插入的节点颜色默认为红色

如果新插入节点的父节点颜色为红色 违反了性质4

       1.新插入节点的父节点为其父节点的左子节点时，找到其叔叔节点

              1.1  如果叔叔节点的颜色为红色时

                      1.1.1 将插入节点的父节点和叔叔节点的颜色设置为黑色，并且将插入节点的祖父节点的颜色设置为红色，再将祖父节点设置为插入的节点

             1.2  如果叔叔节点的颜色为黑色时

                        1.2.1 如果当前插入节点是其父节点的右子节点时，先将新插入节点和其父节点进行左旋操作，再进行1.2.2操作

                        1.2.2 将新插入节点的父节点的颜色设置为黑色，并将其祖父节点的颜色设置为红色，最后将其祖父节点与其左子节点进行右旋

     2.新插入节点的父节点为其父节点的右子节点时，找到其叔叔节点

             2.1 如果当前叔叔节点为红色

                      2.1.1 将新插入节点的父节点和其叔叔节点设置为黑色，并将其祖父节点设置为红色，最后将祖父节点设置为新插入的节点

             2.2 如果叔叔节点的颜色为黑色时

                       2.2.1 如果当前插入节点为其父节点的左子节点 ，先将新插入节点和其父节点进行右旋操作。再进行2.2.2操作

                       2.2.2 将新插入节点的父节点的颜色设置为黑色，并将其祖父节点的颜色设置为红色，最后将其祖父节点与其左子节点进行左旋

     3. 最后设置根节点的颜色为黑色

2.2 删除节点

  1. /**
  2.      * Delete node p, and then rebalance the tree.
  3.      */
  4.     private void deleteEntry(Entry<K,V> p) {
  5.         modCount++;
  6.         size--;
  7.  
  8.         // If strictly internal, copy successor's element to p and then make p
  9.         // point to successor.
  10.         // 当前待删除的节点有两个子节点
  11.         if (p.left != null && p.right != null) {
  12.             // 找到当前节点的前驱或者后继子节点，当前方法采用后继
  13.             Entry<K,V> s = successor(p);
  14.             // 使用后继子节点替换掉当前待删除的节点
  15.             p.key = s.key;
  16.             p.value = s.value;
  17.             p = s;
  18.         } // p has 2 children
  19.  
  20.         // Start fixup at replacement node, if it exists.
  21.         // 找到待删除节点的子节点，可能为null
  22.         Entry<K,V> replacement = (p.left != null ? p.left : p.right);
  23.  
  24.         // 如果找到子节点
  25.         if (replacement != null) {
  26.             // Link replacement to parent
  27.             // 将当前子节点的父节点指向待删除结点的父节点
  28.             replacement.parent = p.parent;
  29.             // 如果待删除结点的父节点为空，说明待删除结点为根节点
  30.             if (p.parent == null)
  31.                 // 将根节点替换为当前子节点
  32.                 root = replacement;
  33.             // 如果当前待删除的节点是其父节点的左子节点
  34.             else if (p == p.parent.left)
  35.                 // 将父节点的左子节点替换为待删除节点的子节点 换句话说就是孩子抢了父亲的位置
  36.                 p.parent.left  = replacement;
  37.             else
  38.                 // 如果待删除的节点是其父节点的右子节点，则将父节点的右子节点替换为待删除节点的子节点
  39.                 p.parent.right = replacement;
  40.  
  41.             // Null out links so they are OK to use by fixAfterDeletion.
  42.             // 空出待删除节点的所有链接，以便后续操作
  43.             p.left = p.right = p.parent = null;
  44.  
  45.             // Fix replacement
  46.             // 如果待删除的节点的颜色为黑色，违反了性质5
  47.             if (p.color == BLACK)
  48.                 // 传入其子节点
  49.                 fixAfterDeletion(replacement);
  50.         // 如果待删除节点的父节点为null，说明为根节点，并且没有子节点，则删除当前树
  51.         } else if (p.parent == null) { // return if we are the only node.
  52.             root = null;
  53.         // 如果待删除节点的父节点不为null，且没有子节点
  54.         } else { //  No children. Use self as phantom replacement and unlink.
  55.             // 如果当前待删除结点的颜色为黑色，违反性质5，则需要做平衡操作
  56.             if (p.color == BLACK)
  57.                 fixAfterDeletion(p);
  58.  
  59.             // 从待删除结点的父节点上删除该节点 （从父亲的角度上清除父子关系）
  60.             if (p.parent != null) {
  61.                 if (p == p.parent.left)
  62.                     p.parent.left = null;
  63.                 else if (p == p.parent.right)
  64.                     p.parent.right = null;
  65.                 // 将待删除结点的父节点连接删除 （从孩子的角度上清除父子关系）
  66.                 p.parent = null;
  67.             }
  68.         }
  69.     }
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83. /**
  84.      * Returns the successor of the specified Entry, or null if no such.
  85.      */
  86.     static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
  87.         if (t == null)
  88.             return null;
  89.         // 返回当前节点的后继节点
  90.         else if (t.right != null) {
  91.             Entry<K,V> p = t.right;
  92.             while (p.left != null)
  93.                 p = p.left;
  94.             return p;
  95.         // 当前节点没有右子节点，返回null
  96.         } else {
  97.             Entry<K,V> p = t.parent;
  98.             Entry<K,V> ch = t;
  99.             // 当前节点不为根节点且为其父节点的右子节点，则返回当前节点的父节点
  100.             while (p != null && ch == p.right) {
  101.                 ch = p;
  102.                 p = p.parent;
  103.             }
  104.             return p;
  105.         }
  106.     }
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  /** From CLR */
  116.     private void fixAfterDeletion(Entry<K,V> x) {
  117.         // 当前节点不是根节点，且颜色为黑色
  118.         while (x != root && colorOf(x) == BLACK) {
  119.             // 如果当前节点是其父节点的左子节点
  120.             if (x == leftOf(parentOf(x))) {
  121.                 // 找到其兄弟节点
  122.                 Entry<K,V> sib = rightOf(parentOf(x));
  123.  
  124.                 // 如果当前兄弟节点的颜色为红色
  125.                 if (colorOf(sib) == RED) {
  126.                     // 将当前兄弟节点的颜色设置为黑色
  127.                     setColor(sib, BLACK);
  128.                     // 其父节点设置为红色
  129.                     setColor(parentOf(x), RED);
  130.                     // 左旋两节点
  131.                     rotateLeft(parentOf(x));
  132.                     // 将兄弟节点重新赋值为旋转后的父节点的右子节点
  133.                     sib = rightOf(parentOf(x));
  134.                 }
  135.  
  136.                 // 如果当前兄弟节点的左右节点的子节点均为黑色
  137.                 if (colorOf(leftOf(sib))  == BLACK &&
  138.                     colorOf(rightOf(sib)) == BLACK) {
  139.                     // 将当前兄弟节点的颜色设置为红色 并且将当前节点指向父节点（左右树同时减少一个黑节点，对于整棵树来说，可能会破坏其平衡性，所以需要将当前父节点作为整颗树平衡条件）
  140.                     setColor(sib, RED);
  141.                     x = parentOf(x);
  142.                 } else {
  143.                     // 如果当前兄弟节点只有其右子节点为黑色
  144.                     if (colorOf(rightOf(sib)) == BLACK) {
  145.                         // 将当前兄弟节点的左子节点赋值为黑色
  146.                         setColor(leftOf(sib), BLACK);
  147.                         // 将当前兄弟节点颜色设置为红色
  148.                         setColor(sib, RED);
  149.                         // 右旋当前兄弟节点
  150.                         rotateRight(sib);
  151.                         // 将兄弟节点重新赋值为旋转后节点
  152.                         sib = rightOf(parentOf(x));
  153.                     }
  154.                     // 将当前兄弟节点的颜色设置为x的父节点的颜色
  155.                     setColor(sib, colorOf(parentOf(x)));
  156.                     // 将其父节点的颜色设置为黑色
  157.                     setColor(parentOf(x), BLACK);
  158.                     // 将当前兄弟节点的右子节点的颜色设置为黑色
  159.                     setColor(rightOf(sib), BLACK);
  160.                     // 左旋父节点
  161.                     rotateLeft(parentOf(x));
  162.                     // 将当前节点设置为根节点 跳出循环
  163.                     x = root;
  164.                 }
  165.              // 如果当前节点是其父节点的右子节点
  166.             } else { // symmetric
  167.                 // 找到当前节点的兄弟节点
  168.                 Entry<K,V> sib = leftOf(parentOf(x));
  169.  
  170.                 // 如果当前兄弟节点是红色
  171.                 if (colorOf(sib) == RED) {
  172.                     // 将当前兄弟节点设置为黑色
  173.                     setColor(sib, BLACK);
  174.                     // 将父节点设置为红色
  175.                     setColor(parentOf(x), RED);
  176.                     // 右旋父节点
  177.                     rotateRight(parentOf(x));
  178.                     // 将兄弟节点重新赋值为旋转后的节点
  179.                     sib = leftOf(parentOf(x));
  180.                 }
  181.  
  182.                 // 如果当前兄弟节点的左右子节点均为黑色
  183.                 if (colorOf(rightOf(sib)) == BLACK &&
  184.                     colorOf(leftOf(sib)) == BLACK) {
  185.                     // 将当前兄弟节点的颜色设置为红色
  186.                     setColor(sib, RED);
  187.                     // 将当前节点指向其父节点
  188.                     x = parentOf(x);
  189.                 } else {
  190.                     // 如果当前兄弟节点的左子节点为黑色
  191.                     if (colorOf(leftOf(sib)) == BLACK) {
  192.                         // 将当前兄弟节点的右子节点设置为黑色 并将当前兄弟节点的颜色设为红色
  193.                         setColor(rightOf(sib), BLACK);
  194.                         setColor(sib, RED);
  195.                         // 左旋当前兄弟节点
  196.                         rotateLeft(sib);
  197.                         // 将当前兄弟节点重新赋值为旋转后的节点（更新兄弟节点）
  198.                         sib = leftOf(parentOf(x));
  199.                     }
  200.                     // 将当前兄弟节点的颜色设置为其父节点的颜色
  201.                     setColor(sib, colorOf(parentOf(x)));
  202.                     // 将其父节点与当前兄弟节点的左子节点颜色设置为黑色 
  203.                     setColor(parentOf(x), BLACK);
  204.                     setColor(leftOf(sib), BLACK);
  205.                     // 右旋其父节点
  206.                     rotateRight(parentOf(x));
  207.                     // 将当前节点设置为根节点
  208.                     x = root;
  209.                 }
  210.             }
  211.         }
  212.  
  213.         // 将当前节点的颜色设置为黑色
  214.         setColor(x, BLACK);
  215.     }

删除节点相对于插入节点来说比较复杂，不过没关系，掌握了插入的情况下学删除是比较容易的。换汤不换药

通过对上面源码的解读，我们可以得出：

1. 待删除的节点有两个子节点

    1.1 找到当前待删除节点的前驱或者后继子节点（当前方法采用后继），并且使用后继子节点替换掉当前待删除的节点，最后再删除后继子节点，转到2

2.待删除的节点有一个子节点

    2.1 如果待删除的节点的颜色为红色，用其子节点替换掉待删除的节点

    2.2 如果待删除的节点的颜色为黑色，并且其子节点为红色，用当前子节点替换掉待删除的节点然后将颜色改为黑色

    2.3 如果待删除的节点的颜色为黑色，并且其子节点为黑色，找到当前子节点的兄弟节点

          2.3.1 如果当前兄弟节点是其父节点的右子节点

                     2.3.1.1 如果当前兄弟节点的颜色为红色，则将当前兄弟节点的颜色设置为黑色，父节点设置为红色，以父节点为中心左旋两节点并且将兄弟节点重新赋值为旋转后的父节点的右子节点

                     2.3.1.2 如果当前兄弟节点的左右节点的子节点均为黑色，则将当前兄弟节点的颜色设置为红色，并且将当前子节点指向父节点

                     2.3.1.3 如果当前兄弟节点只有其右子节点为黑色，则将当前兄弟节点的左子节点赋值为黑色，并且将当前兄弟节点的颜色设置为红色，再右旋当前兄弟节点，最后将兄弟节点重新赋值为旋转后节点，再进行2.3.1.4 操作

                      2.3.1.4  将当前兄弟节点的颜色设置为其父节点的颜色，并将其父节点的颜色设置为黑色，然后将当前兄弟节点的右子节点的颜色设置为黑色，再以其父节点为中心左旋两节点，最后将当前节点设置为根节点，以便跳出循环

         2.3.2 如果当前兄弟节点是其父节点的左子节点

                     2.3.2.1 如果当前兄弟节点的颜色为红色，则将当前兄弟节点的颜色设置为黑色，父节点设置为红色，以父节点为中心右旋两节点并且将兄弟节点重新赋值为旋转后的父节点的左子节点

                     2.3.2.2 如果当前兄弟节点的左右节点的子节点均为黑色，则将当前兄弟节点的颜色设置为红色，并且将当前子节点指向父节点

                     2.3.2.3 如果当前兄弟节点只有其左子节点为黑色，将当前兄弟节点的右子节点赋值为黑色，并且将当前兄弟节点的颜色设置为红色，再左旋当前兄弟节点，最后将兄弟节点重新赋值为旋转后节点，再进行2.3.2.4操作

                     2.3.2.4  将当前兄弟节点的颜色设置为其父节点的颜色，并将其父节点的颜色设置为黑色，然后将当前兄弟节点的左子节点的颜色设置为黑色，再以其父节点为中心右旋两节点，最后将当前节点设置为根节点（跳出循环）

3.待删除的节点没有子节点

    3.1 待删除的节点为红色，直接删除

    3.2 待删除的节点为黑色，将当前待删除的节点作为平衡条件进行以上操作，再删除该节点 
4.将当前节点的颜色设置为黑色

图片我就不画了，如果大家觉得没图片不太好理解的话，我推荐这篇博客                                                

三、代码仿现

我是通过模仿TreeMap来实现红黑树，里边没有任何注释 

大家可以自行解读来检验自己有没有掌握

  1. @AllArgsConstructor
  2. @NoArgsConstructor
  3. @Data
  4. @ToString
  5. public class RedBlackNode {
  6.  
  7.     public Integer key;
  8.     public Integer value;
  9.     public RedBlackNode leftNode;
  10.     public RedBlackNode rightNode;
  11.     public RedBlackNode parentNode;
  12.     public String color;
  13.  
  14.     @Override
  15.     public String toString() {
  16.         JSONObject jsonObject = new JSONObject();
  17.         jsonObject.put("key",this.key);
  18.         jsonObject.put("value",this.value);
  19.         jsonObject.put("leftNode",this.leftNode);
  20.         jsonObject.put("rightNode",this.rightNode);
  21.         jsonObject.put("parentNode",this.parentNode);
  22.         jsonObject.put("color",this.color);
  23.         return jsonObject.toJSONString();
  24.     }
  25. }
  1. /**
  2.  * @Author: Eating melons the masses
  3.  * @Date: 2020/3/15 15:42
  4.  */
  5. public class RedBlackTree {
  6.  
  7.     public static final String BLACK = "black";
  8.     public static final String RED = "red";
  9.  
  10.     public RedBlackNode root;
  11.  
  12.     public RedBlackNode insert(Integer key,Integer value){
  13.         RedBlackNode thisNode = root;
  14.         if (root == null){
  15.             root = new RedBlackNode(key,value,null,null,null,BLACK);
  16.             return root;
  17.         }
  18.         int cmp;
  19.         RedBlackNode parent = thisNode;
  20.         RedBlackNode current = thisNode;
  21.  
  22.         while (current != null){
  23.             parent = current;
  24.             int cos = compass(parent.key,key);
  25.             if (cos > 0){
  26.                 current = current.leftNode;
  27.             }else if (cos < 0){
  28.                 current = current.rightNode;
  29.             }else {
  30.                 current.setValue(value);
  31.                return  current;
  32.             }
  33.         }
  34.  
  35.         RedBlackNode redBlackNode = new RedBlackNode(key, value, null, null, parent, RED);
  36.         cmp = compass(parent.key,key);
  37.         if (cmp > 0){
  38.             parent.leftNode = redBlackNode;
  39.         }else {
  40.             parent.rightNode = redBlackNode;
  41.         }
  42.         addNodeToTree(redBlackNode);
  43.  
  44.  
  45.         return root;
  46.     }
  47.  
  48.     public RedBlackNode delete(int key){
  49.         RedBlackNode redBlackNode = findNodeByKey(key);
  50.  
  51.         if (redBlackNode.leftNode != null && redBlackNode.rightNode != null){
  52.             RedBlackNode minNode = minNode(redBlackNode.rightNode);
  53.             redBlackNode.key = minNode.key;
  54.             redBlackNode.value = minNode.value;
  55.             redBlackNode = minNode;
  56.         }
  57.  
  58.         RedBlackNode onlyChild = redBlackNode.leftNode == null ? redBlackNode.rightNode : redBlackNode.leftNode;
  59.         if (onlyChild != null){
  60.             onlyChild.parentNode = redBlackNode.parentNode;
  61.             if (redBlackNode.parentNode == null){
  62.                 root = onlyChild;
  63.             }else if (redBlackNode == redBlackNode.parentNode.leftNode){
  64.                 redBlackNode.parentNode.leftNode = onlyChild;
  65.             }else {
  66.                 redBlackNode.parentNode.rightNode = onlyChild;
  67.             }
  68.             redBlackNode.leftNode = redBlackNode.parentNode = redBlackNode.rightNode = null;
  69.             if (redBlackNode.color == BLACK){
  70.                 deleteNodeByTree(onlyChild);
  71.             }
  72.         }else if (redBlackNode.parentNode == null){
  73.             root = null;
  74.         }else {
  75.             if (redBlackNode.color == BLACK){
  76.                 deleteNodeByTree(redBlackNode);
  77.             }
  78.             if (redBlackNode.parentNode != null){
  79.                 if (redBlackNode == redBlackNode.parentNode.leftNode){
  80.                     redBlackNode.parentNode.leftNode = null;
  81.                 }else {
  82.                     redBlackNode.parentNode.rightNode = null;
  83.                 }
  84.                 redBlackNode.parentNode = null;
  85.             }
  86.         }
  87.     return root;
  88.     }
  89.  
  90.     private void deleteNodeByTree(RedBlackNode child) {
  91.         while (child != root && child.color == BLACK){
  92.             if (child == child.parentNode.leftNode){
  93.                 RedBlackNode broNode = child.parentNode.rightNode;
  94.                 if (broNode.color == RED){
  95.                     broNode.setColor(BLACK);
  96.                     child.parentNode.setColor(RED);
  97.                     ll_rotate(child.parentNode);
  98.                     broNode = child.parentNode.rightNode;
  99.                 }else if (broNode.leftNode.color == BLACK &&
  100.                         broNode.rightNode.color == BLACK){
  101.                     broNode.setColor(RED);
  102.                     child = child.parentNode;
  103.                 }else {
  104.                     if (broNode.rightNode.color == BLACK){
  105.                         broNode.leftNode.setColor(BLACK);
  106.                         rr_rotate(broNode);
  107.                         broNode = child.parentNode.rightNode;
  108.                     }
  109.                     broNode.setColor(child.parentNode.color);
  110.                     child.parentNode.setColor(BLACK);
  111.                     broNode.rightNode.setColor(BLACK);
  112.                     ll_rotate(child.parentNode);
  113.                     child = root;
  114.                 }
  115.             }else {
  116.                 RedBlackNode broNode = child.parentNode.leftNode;
  117.                 if (broNode.color == RED){
  118.                     broNode.setColor(BLACK);
  119.                     child.parentNode.setColor(RED);
  120.                     rr_rotate(child.parentNode);
  121.                     broNode = child.parentNode.leftNode;
  122.                 }else if (broNode.leftNode.color == BLACK &&
  123.                         broNode.rightNode.color == BLACK){
  124.                     broNode.setColor(RED);
  125.                     child = child.parentNode;
  126.                 }else {
  127.                     if (broNode.leftNode.color == BLACK){
  128.                         broNode.rightNode.setColor(BLACK);
  129.                         ll_rotate(broNode);
  130.                         broNode = child.parentNode.leftNode;
  131.                     }
  132.                     broNode.setColor(child.parentNode.color);
  133.                     child.parentNode.setColor(BLACK);
  134.                     broNode.leftNode.setColor(BLACK);
  135.                     rr_rotate(child.parentNode);
  136.                     child = root;
  137.                 }
  138.             }
  139.         }
  140.         child.setColor(BLACK);
  141.     }
  142.  
  143.     private RedBlackNode minNode(RedBlackNode node) {
  144.         if (node != null){
  145.             RedBlackNode current = node;
  146.             while (current != null){
  147.                 if (current.leftNode != null){
  148.                     current = current.leftNode;
  149.                 }else {
  150.                     return current;
  151.                 }
  152.             }
  153.         }
  154.         return null;
  155.     }
  156.  
  157.     private RedBlackNode findNodeByKey(int key) {
  158.         if (root != null){
  159.             RedBlackNode current = root;
  160.             while (current != null){
  161.                 if (current.key > key){
  162.                     current = current.leftNode;
  163.                 }else if (current.key < key){
  164.                     current = current.rightNode;
  165.                 }else {
  166.                     return current;
  167.                 }
  168.             }
  169.         }
  170.         return null;
  171.     }
  172.  
  173.     private void addNodeToTree(RedBlackNode redBlackNode) {
  174.         if (redBlackNode != null && redBlackNode.parentNode.color == RED){
  175.             RedBlackNode uncle = null;
  176.             RedBlackNode grandparent = redBlackNode.parentNode.parentNode;
  177.             if (grandparent != null){
  178.                 if (redBlackNode.parentNode == grandparent.leftNode){
  179.                     uncle = redBlackNode.parentNode.parentNode.rightNode;
  180.                     String color = uncle == null?BLACK:uncle.color;
  181.                     if (color == RED){
  182.                         redBlackNode.parentNode.setColor(BLACK);
  183.                         uncle.setColor(BLACK);
  184.                         grandparent.setColor(RED);
  185.                         redBlackNode = grandparent;
  186.                     }else {
  187.                         if (redBlackNode == redBlackNode.parentNode.rightNode){
  188.                             ll_rotate(redBlackNode.parentNode);
  189.                         }
  190.                         redBlackNode.parentNode.setColor(BLACK);
  191.                         grandparent.setColor(RED);
  192.                         rr_rotate(grandparent);
  193.                     }
  194.                 }else {
  195.                     uncle = redBlackNode.parentNode.parentNode.leftNode;
  196.                     String color = uncle == null?BLACK:uncle.color;
  197.                     if (color == RED){
  198.                         redBlackNode.parentNode.setColor(BLACK);
  199.                         uncle.setColor(BLACK);
  200.                         grandparent.setColor(RED);
  201.                         redBlackNode = grandparent;
  202.                     }else {
  203.                         if (redBlackNode == redBlackNode.parentNode.leftNode){
  204.                             rr_rotate(redBlackNode.parentNode);
  205.                         }
  206.                         redBlackNode.parentNode.setColor(BLACK);
  207.                         grandparent.setColor(RED);
  208.                         ll_rotate(grandparent);
  209.                     }
  210.                 }
  211.             }
  212.         }
  213.         root.setColor(BLACK);
  214.     }
  215.  
  216.     private void rr_rotate(RedBlackNode node) {
  217.         if (node != null){
  218.             RedBlackNode leftNode = node.leftNode;
  219.             node.leftNode = leftNode.rightNode;
  220.             if (leftNode.rightNode != null){
  221.                 leftNode.rightNode.parentNode = node;
  222.             }
  223.             leftNode.parentNode = node.parentNode;
  224.             if (node.parentNode == null){
  225.                 root = leftNode;
  226.             }else if (node.parentNode.leftNode == node){
  227.                 node.parentNode.leftNode = leftNode;
  228.             }else {
  229.                 node.parentNode.rightNode = leftNode;
  230.             }
  231.             leftNode.rightNode = node;
  232.             node.parentNode = leftNode;
  233.         }
  234.     }
  235.  
  236.     private int compass(Integer le, Integer ri) {
  237.         return le - ri;
  238.     }
  239.  
  240.     private void ll_rotate(RedBlackNode node) {
  241.         if (node != null){
  242.             RedBlackNode rightNode = node.rightNode;
  243.             node.rightNode = rightNode.leftNode;
  244.             if (rightNode.leftNode != null){
  245.                 rightNode.leftNode.parentNode = node;
  246.             }
  247.             rightNode.parentNode = node.parentNode;
  248.             if (node.parentNode == null){
  249.                 root = rightNode;
  250.             }else if (node.parentNode.leftNode == node){
  251.                 node.parentNode.leftNode = rightNode;
  252.             }else {
  253.                 node.parentNode.rightNode = rightNode;
  254.             }
  255.             rightNode.leftNode = node;
  256.             node.parentNode = rightNode;
  257.         }
  258.  
  259.     }
  260.  
  261.  
  262.     public static void main(String[] args) {
  263.         RedBlackTree redBlackTree = new RedBlackTree();
  264.         redBlackTree.insert(18,12);
  265.         redBlackTree.insert(8,134);
  266.         redBlackTree.insert(3,325);
  267.         redBlackTree.insert(9,5464);
  268.         redBlackTree.insert(10,1);
  269.         redBlackTree.insert(5,32);
  270.         redBlackTree.insert(4,122);
  271.         redBlackTree.insert(1,25);
  272.         redBlackTree.insert(7,65);
  273.         redBlackTree.insert(13,123);
  274.         redBlackTree.insert(12, 1455);
  275.         redBlackTree.insert(21, 342);
  276.         redBlackTree.insert(22, 534);
  277.  
  278.         redBlackTree.delete(5);
  279.         redBlackTree.delete(7);
  280.         System.out.println(redBlackTree.root);
  281.  
  282.     }
  283.  
  284.  
  285. }
  1.                 {\__/}                                          {\__/}
  2.                 ( ·-·)                                          (·-· )
  3.                 / >------------------------------------------------< \
  4.                          |      ☆                            |
  5.                          |         ☆                         |
  6.                          |  ★                                |
  7.                          |         ☆                         |
  8.                          |      ☆                            |
  9.                          |                                   |
  10.                          -------------------------------------

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/214767
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号