1 红黑树逻辑推导图

https://www.processon.com/view/link/5eddac9ce401fd5f2d94f24d

2 节点类-Node

  1. public class Node<E> {
  3.     public static final boolean BLACK = true;
  4.     public static final boolean RED = false;
  5.     // 每一个新增节点都默认为红色
  6.     private boolean color = RED;
  8.     private Node<E> parent;
  9.     private Node<E> leftChild;
  10.     private Node<E> rightChild;
  11.     private E element;
  13.     public Node(E element,Node<E> parent) {
  14.         super();
  15.         this.element = element;
  16.         this.parent = parent;
  17.     }
  19.     public boolean getColor() {
  20.         return color;
  21.     }
  23.     public void setColor(boolean color) {
  24.         this.color = color;
  25.     }
  27.     public Node<E> getParent() {
  28.         return parent;
  29.     }
  31.     public void setParent(Node<E> parent) {
  32.         this.parent = parent;
  33.     }
  35.     public Node<E> getLeftChild() {
  36.         return leftChild;
  37.     }
  39.     public void setLeftChild(Node<E> leftChild) {
  40.         this.leftChild = leftChild;
  41.     }
  43.     public Node<E> getRightChild() {
  44.         return rightChild;
  45.     }
  47.     public void setRightChild(Node<E> rightChild) {
  48.         this.rightChild = rightChild;
  49.     }
  51.     public E getElement() {
  52.         return element;
  53.     }
  55.     public void setElement(E element) {
  56.         this.element = element;
  57.     }
  59.     //是否是左孩子节点
  60.     public boolean isLeftChild(){
  61.         return parent != null && this == parent.leftChild;
  62.     }
  63.     //是否是右孩子节点
  64.     public boolean isRightChild(){
  65.         return parent != null && this == parent.rightChild;
  66.     }
  67.     //判断是否是叶子节点
  68.     public boolean isLeaf(){
  69.         return leftChild == null && rightChild == null;
  70.     }
  71.     //判断是否有两个子节点
  72.     public boolean hasTwoChild(){
  73.         return leftChild != null && rightChild != null;
  74.     }
  76.     /**
  77.      * 返回兄弟节点
  78.      * 如果要拿到叔父节点
  79.      *  则可以调用 parent.sibling()
  80.      */
  81.     public Node<E> sibling(){
  82.         if(isLeftChild()){
  83.             return parent.rightChild;
  84.         }
  85.         if(isRightChild()){
  86.             return parent.leftChild;
  87.         }
  88.         //即不是左节点，也不是右节点，则没有兄弟节点
  89.         //即为根节点
  90.         return null;
  91.     }
  93. }

3 红黑树实现类-RBTree

  1. import java.util.Comparator;
  2. import java.util.LinkedList;
  3. import java.util.Queue;
  5. public class RBTree<E> {
  6.     // 比较器，用于比较两个存储对象的大小
  7.     private Comparator<E> comparator;
  8.     // 树根
  9.     private Node<E> root;
  10.     // 树中元素的多少
  11.     private int size;
  13.     public RBTree() {
  14.         this(null);
  15.     }
  17.     public RBTree(Comparator<E> comparator) {
  18.         this.comparator = comparator;
  19.     }
  21.     public void add(E element) {
  22.         // 校验传入的参数是否为null
  23.         // 如果为null，则抛出异常
  24.         elementNotNullCheck(element);
  25.         // 校验是否创建了树根
  26.         if (root == null) {
  27.             root = createNode(element, null);
  28.             size++;
  29.             // 新添加节点之后的处理
  30.             afterAdd(root);
  31.             return;
  32.         }
  33.         // 添加的不是第一个节点
  34.         Node<E> parent = root;
  35.         Node<E> node = root;
  36.         // 用于保存比较的结果
  37.         // 大于0，则向右子树
  38.         // 等于0，则有相等的元素
  39.         // 小于0，则向左子树
  40.         int cmp = 0;
  41.         // 遍历找到插入位置的父节点
  42.         while (node != null) {
  43.             cmp = compare(element, node.getElement());
  44.             parent = node;
  45.             if (cmp > 0) {
  46.                 node = node.getRightChild();
  47.             } else if (cmp < 0) {
  48.                 node = node.getLeftChild();
  49.             } else { // 相等
  50.                 node.setElement(element);
  51.                 return;
  52.             }
  53.         }
  54.         // 已经找到了插入位置的父节点 parent
  55.         // 新建节点
  56.         Node<E> newNode = createNode(element, parent);
  57.         if (cmp > 0) {
  58.             parent.setRightChild(newNode);
  59.         } else {
  60.             parent.setLeftChild(newNode);
  61.         }
  62.         size++;
  63.         // 新添加节点之后的处理
  64.         afterAdd(newNode);
  65.     }
  67. //    public E get
  69.     //删除节点
  70.     public void remove(E element) {
  71.         remove(findNode(element));
  72.     }
  74.     private void remove(Node<E> node) {
  75.         if (node == null)
  76.             return;
  78.         size--;
  80.         if (node.hasTwoChild()) { // 度为2的节点
  81.             // 找到后继节点
  82.             Node<E> s = successor(node);
  83.             // 用后继节点的值覆盖度为2的节点的值
  84.             node.setElement(s.getElement());
  85.             // 删除后继节点
  86.             node = s;
  87.         }
  89.         // 删除node节点（node的度必然是1或者0）
  90.         Node<E> replacement = node.getLeftChild() != null ? node.getLeftChild() : node.getRightChild();
  92.         if (replacement != null) { // node是度为1的节点
  93.             // 更改parent
  94.             replacement.setParent(node.getParent());
  95.             // 更改parent的left、right的指向
  96.             if (node.getParent() == null) { // node是度为1的节点并且是根节点
  97.                 root = replacement;
  98.             } else if (node == node.getParent().getLeftChild()) {
  99.                 node.getParent().setLeftChild(replacement);
  100.             } else { // node == node.parent.right
  101.                 node.getParent().setRightChild(replacement);
  102.             }
  104.             // 删除节点之后的处理
  105.             afterRemove(replacement);
  106.         } else if (node.getParent() == null) { // node是叶子节点并且是根节点
  107.             root = null;
  108.             // 删除节点之后的处理
  109.             afterRemove(node);
  110.         } else { // node是叶子节点，但不是根节点
  111.             if (node == node.getParent().getLeftChild()) {
  112.                 node.getParent().setLeftChild(null);
  113.             } else { // node == node.parent.right
  114.                 node.getParent().setRightChild(null);
  115.             }
  117.             // 删除节点之后的处理
  118.             afterRemove(node);
  119.         }
  120.     }
  122.     // 找到前驱节点
  123.     protected Node<E> successor(Node<E> node) {
  124.         if (node == null)
  125.             return null;
  127.         // 前驱节点在左子树当中（right.left.left.left....）
  128.         Node<E> p = node.getRightChild();
  129.         if (p != null) {
  130.             while (p.getLeftChild() != null) {
  131.                 p = p.getLeftChild();
  132.             }
  133.             return p;
  134.         }
  136.         // 从父节点、祖父节点中寻找前驱节点
  137.         while (node.getParent() != null && node == node.getParent().getRightChild()) {
  138.             node = node.getParent();
  139.         }
  140.         return node.getParent();
  141.     }
  143.     // 查找元素对应的Node节点
  144.     private Node<E> findNode(E element) {
  145.         Node<E> node = root;
  146.         while (node != null) {
  147.             int cmp = compare(element, node.getElement());
  148.             if (cmp == 0)
  149.                 return node;
  150.             if (cmp > 0) {
  151.                 node = node.getRightChild();
  152.             } else { // cmp < 0
  153.                 node = node.getLeftChild();
  154.             }
  155.         }
  156.         return null;
  157.     }
  159.     private void afterAdd(Node<E> node) {
  160.         Node<E> parent = node.getParent();
  162.         // 一： 如果父节点为null，则表示变动的节点为根节点
  163.         if (null == parent) {
  164.             black(node);// 将其置为黑色
  165.             return;
  166.         }
  167.         // 二：如果变动的节点的父节点为黑色，则什么都不用处理
  168.         if (isBlack(parent)) {
  169.             return;
  170.         }
  171.         // 三：到此处，说明插入节点的父节点为红色
  172.         Node<E> uncle = parent.sibling();
  173.         // 祖父节点在这种大的情况下都会要变为红色（仅在最后一步做树根保持黑色的操作）
  174.         Node<E> grandParent = red(parent.getParent());
  175.         // 1.叔叔节点为红色，即此时父亲节点和叔叔节点都为红色
  176.         if (isRed(uncle)) {
  177.             // 将叔叔节点与父节点染成黑色，将祖父节点染成红色
  178.             black(parent);
  179.             black(uncle);
  180.             // 将祖父节点染成红色，
  181.             red(grandParent);
  182.             // 并将其当做新添加节点,向上传递
  183.             afterAdd(grandParent);
  184.             return;
  185.         }
  186.         // 2.叔叔节点不为红色，那么只能为空（Nil），不能为黑色节点
  187.         // 父节点是左节点
  188.         if (parent.isLeftChild()) {
  189.             // 插入的节点如果是右孩子，则需要进行左旋操作
  190.             if (node.isRightChild()) {
  191.                 black(node);
  192.                 rotateLeft(parent);
  193.             }
  194.             // 插入的节点如果是左孩子，则仅需直接变色
  195.             else {
  196.                 black(parent);
  197.             }
  198.             // 然后以祖父节点为轴，向右旋转
  199.             rotateRight(grandParent);
  200.         }
  201.         // 父节点是右节点
  202.         else {
  203.             // 插入的节点如果是左孩子，则先需要右旋操作
  204.             if (node.isLeftChild()) {
  205.                 black(node);
  206.                 rotateRight(parent);
  207.             }
  208.             // 插入的节点如果是右孩子，则将父节点变黑
  209.             else {
  210.                 black(parent);
  211.             }
  212.             // 然后以祖父节点为轴，向左旋转
  213.             rotateLeft(grandParent);
  214.         }
  215.     }
  217.     private void afterRemove(Node<E> node) {
  218.         // 如果删除的节点是红色的，那么就不用做任何处理
  219.         // 用于取代被删除的节点的节点是红色的
  220.         if (isRed(node)) {
  221.             black(node);
  222.             return;
  223.         }
  225.         // 删除的是黑色的节点
  226.         Node<E> parent = node.getParent();
  227.         // 1.删除的是黑色的根节点
  228.         if (null == parent)
  229.             return;
  231.         // 2.删除的是黑色的叶子节点
  232.         // 判断是否为左孩子节点
  233.         boolean left = (parent.getLeftChild() == null) | node.isLeftChild();
  234.         // 拿到兄弟节点
  235.         Node<E> sibling = left ? parent.getRightChild() : parent.getLeftChild();
  236.         if (left) {
  237.             // 被删除的黑色节点是左孩子，其兄弟节点在右边
  238.             if (isRed(sibling)) {
  239.                 // 兄弟节点是红色
  240.                 black(sibling);
  241.                 red(parent);
  242.                 rotateLeft(parent);
  243.                 // 经过旋转之后，兄弟节点发生改变
  244.                 sibling = parent.getRightChild();
  245.                 // 后面即可按照兄弟节点为黑色的来处理
  246.             }
  247.             // 兄弟节点为黑色
  248.             if (isBlack(sibling.getLeftChild()) && isBlack(sibling.getRightChild())) {
  249.                 // 兄弟节点的子节点没有红色节点,即：为黑色节点或者为null
  250.                 boolean parentIsBlack = isBlack(parent);
  251.                 black(parent);
  252.                 red(sibling);
  253.                 if (parentIsBlack) {
  254.                     afterRemove(parent);
  255.                 }
  256.             } else {
  257.                 // 兄弟节点的子节点中至少有一个为红色节点
  258.                 if (isBlack(sibling.getRightChild())) {
  259.                     // 兄弟节点的右孩子是null，即为黑色的，不为红色
  260.                     // 说明红色节点在左边
  261.                     // 则进行右旋转
  262.                     rotateRight(sibling);
  263.                     // 此时兄弟节点发生了改变
  264.                     sibling = parent.getRightChild();
  265.                     // 此时即可用兄弟节点的红色孩子节点当做在右边处理
  266.                 }
  267.                 // 变色处理（包含了两种情况，将两种情况的颜色统一处理）
  268.                 color(sibling, colorOf(parent));
  269.                 black(sibling.getRightChild());
  270.                 black(parent);
  271.                 rotateLeft(parent);
  272.             }
  273.         } else {
  274.             // 被删除的黑色节点是右孩子，其兄弟节点在左边
  276.             if (isRed(sibling)) {
  277.                 // 兄弟节点是红色
  278.                 black(sibling);
  279.                 red(parent);
  280.                 rotateRight(parent);
  281.                 // 经过旋转之后，兄弟节点发生改变
  282.                 sibling = parent.getLeftChild();
  283.                 // 后面即可按照兄弟节点为黑色的来处理
  284.             }
  285.             // 兄弟节点为黑色
  286.             if (isBlack(sibling.getLeftChild()) && isBlack(sibling.getRightChild())) {
  287.                 // 兄弟节点的子节点没有红色节点,即：为黑色节点或者为null
  288.                 boolean parentIsBlack = isBlack(parent);
  289.                 black(parent);
  290.                 red(sibling);
  291.                 if (parentIsBlack) {
  292.                     afterRemove(parent);
  293.                 }
  294.             } else {
  295.                 // 兄弟节点的子节点中至少有一个为红色节点
  296.                 if (isBlack(sibling.getLeftChild())) {
  297.                     // 兄弟节点的左孩子是null，即为黑色的，不为红色
  298.                     // 则进行左旋转
  299.                     rotateLeft(sibling);
  300.                     // 此时兄弟节点发生了改变
  301.                     sibling = parent.getLeftChild();
  302.                     // 此时即可用兄弟节点的红色孩子节点当做在左边处理
  303.                 }
  304.                 // 变色处理（包含了两种情况，将两种情况的颜色统一处理）
  305.                 color(sibling, colorOf(parent));
  306.                 black(sibling.getLeftChild());
  307.                 black(parent);
  308.                 rotateRight(parent);
  309.             }
  311.         }
  313.     }
  315.     protected Node<E> createNode(E element, Node<E> parent) {
  316.         return new Node<>(element, parent);
  317.     }
  319.     // 元素不能为null，否则就抛出异常，中断程序
  320.     private void elementNotNullCheck(E element) {
  321.         if (element == null) {
  322.             throw new IllegalArgumentException("element must not be null");
  323.         }
  324.     }
  326.     // 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2
  327.     @SuppressWarnings("unchecked")
  328.     private int compare(E e1, E e2) {
  329.         if (comparator != null) {
  330.             return comparator.compare(e1, e2);
  331.         }
  332.         return ((Comparable<E>) e1).compareTo(e2);
  333.     }
  335.     /**
  336.      * ========辅助方法============
  337.      */
  338.     // ==== 旋转
  339.     // 左旋转
  340.     private void rotateLeft(Node<E> grand) {
  341.         Node<E> parent = grand.getRightChild();
  342.         Node<E> child = parent.getLeftChild();
  343.         grand.setRightChild(child);
  344.         parent.setLeftChild(grand);
  345.         afterRotate(grand, parent, child);
  346.     }
  348.     // 右旋转
  349.     private void rotateRight(Node<E> grand) {
  350.         Node<E> parent = grand.getLeftChild();
  351.         Node<E> child = parent.getRightChild();
  352.         grand.setLeftChild(child);
  353.         parent.setRightChild(grand);
  354.         afterRotate(grand, parent, child);
  355.     }
  357.     private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
  358.         // 让parent称为子树的根节点
  359.         parent.setParent(grand.getParent());
  360.         if (grand.isLeftChild()) {
  361.             grand.getParent().setLeftChild(parent);
  362.         } else if (grand.isRightChild()) {
  363.             grand.getParent().setRightChild(parent);
  364.         } else { // grand是root节点
  365.             root = parent;
  366.         }
  367.         // 更新child的parent
  368.         if (child != null) {
  369.             child.setParent(grand);
  370.         }
  371.         // 更新grand的parent
  372.         grand.setParent(parent);
  373.     }
  375.     // ==== 染色
  376.     //将节点设置为黑色
  377.     public Node<E> black(Node<E> node) {
  378.         return color(node, Node.BLACK);
  379.     }
  380.     //将节点设置为红色
  381.     public Node<E> red(Node<E> node) {
  382.         return color(node, Node.RED);
  383.     }
  384.     //设置节点颜色
  385.     private Node<E> color(Node<E> node, boolean color) {
  386.         if (null != node) {
  387.             node.setColor(color);
  388.         }
  389.         return node;
  390.     }
  391.     // ========== 判断颜色 =============
  392.     //判断是否为黑色
  393.     public boolean isBlack(Node<E> node) {
  394.         return colorOf(node) == Node.BLACK;
  395.     }
  396.     //判断是否为红色
  397.     public boolean isRed(Node<E> node) {
  398.         return colorOf(node) == Node.RED;
  399.     }
  400.     //获取颜色，如果节点为null，返回黑色
  401.     private boolean colorOf(Node<E> node) {
  402.         return node == null ? Node.BLACK : node.getColor();
  403.     }
  405.     /**
  406.      * 遍历
  407.      */
  408.     // 遍历===前序遍历
  409.     public void preOrder() {
  410.         System.out.println("前序遍历");
  411.         preOrder(root);
  412.     }
  413.     // 遍历===前序遍历
  414.     private void preOrder(Node<E> node) {
  415.         if (null == node)
  416.             return;
  417.         System.out.println((node.getColor() ? "BLACK" : "RED") + node.getElement().toString());
  418.         preOrder(node.getLeftChild());
  419.         preOrder(node.getRightChild());
  420.     }
  422.     // 遍历===中序遍历
  423.     public void inOrder() {
  424.         System.out.println("中序遍历");
  425.         inOrder(root);
  426.     }
  427.     // 遍历===中序遍历
  428.     private void inOrder(Node<E> node) {
  429.         if (null == node)
  430.             return;
  431.         inOrder(node.getLeftChild());
  432.         System.out.println((node.getColor() ? "BLACK" : "RED") + node.getElement().toString());
  433.         inOrder(node.getRightChild());
  434.     }
  436.     // 遍历===后序遍历
  437.     public void afterOrder() {
  438.         System.out.println("后序遍历");
  439.         afterOrder(root);
  440.     }
  441.     // 遍历===后序遍历
  442.     private void afterOrder(Node<E> node) {
  443.         if (null == node)
  444.             return;
  445.         afterOrder(node.getLeftChild());
  446.         afterOrder(node.getRightChild());
  447.         System.out.println((node.getColor() ? "BLACK" : "RED") + node.getElement().toString());
  448.     }
  450.     // 遍历===层序遍历
  451.     public void levelOrder() {
  452.         System.out.println("层序遍历");
  453.         levelOrder(root);
  454.     }
  455.     // 遍历===层序遍历
  456.     private void levelOrder(Node<E> node) {
  457.         if(root == null){
  458.             System.out.println("树为空");
  459.             return;
  460.         }
  461.         Queue<Node<E>> queue = new LinkedList<>();
  462.         queue.offer(root);
  464.         while (!queue.isEmpty()) {
  465.             Node<E> head = queue.poll();
  466.             if (head.getLeftChild() != null) {
  467.                 queue.offer(head.getLeftChild());
  468.             }
  470.             if (head.getRightChild() != null) {
  471.                 queue.offer(head.getRightChild());
  472.             }
  473.             System.out.println((head.getColor() ? "BLACK" : "RED") + head.getElement().toString());
  474.         }
  475.     }
  476. }