手寫紅黑樹，實(shí)現(xiàn)增趾撵、刪侄柔、查功能

紅黑樹

1、概念

紅黑樹（RBT）的定義：它或者是一顆空樹占调，或者是具有一下性質(zhì)的二叉查找樹暂题。

  1. 節(jié)點(diǎn)非紅即黑
  2. 根節(jié)點(diǎn)是黑色
  3. 所有NULL節(jié)點(diǎn)稱為葉子節(jié)點(diǎn)，且認(rèn)為顏色為黑色
  4. 所有紅節(jié)點(diǎn)的子節(jié)點(diǎn)都為黑色
  5. 從任一節(jié)點(diǎn)到其葉子節(jié)點(diǎn)的所有路徑上都包含相同數(shù)目的黑節(jié)點(diǎn)

對平衡樹的改進(jìn)：任意一個(gè)節(jié)點(diǎn)妈候，它的左右子樹的層次最多不超過一倍敢靡。

1.png

2挂滓、插入節(jié)點(diǎn)

1. 插入節(jié)點(diǎn)：先按照二叉排序樹的方式插入一個(gè)節(jié)點(diǎn)（紅色）
2. 插入節(jié)點(diǎn)是根節(jié)點(diǎn)： 解決：直接將節(jié)點(diǎn)涂黑
3. 插入節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色： 不違背任何性質(zhì)苦银，不用調(diào)整
4. 插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，那么分以下幾種情況：

第一種情況：父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左孩子

情況1：祖父節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn)（叔叔節(jié)點(diǎn)）是紅色
對策： 將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)涂黑赶站，祖父節(jié)點(diǎn)涂紅幔虏，把當(dāng)前節(jié)點(diǎn)指向祖父節(jié)點(diǎn)，從新的當(dāng)前節(jié)點(diǎn)開始算法
2.png
情況2：叔叔節(jié)點(diǎn)是黑色贝椿，右分兩種情況：
情況2.1：當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右孩子
對策：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)做為新的當(dāng)前節(jié)點(diǎn)想括，以新當(dāng)前節(jié)點(diǎn)為支點(diǎn)左旋。
3.png
情況2.2：當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子
對策：父節(jié)點(diǎn)變?yōu)楹谏硬娓腹?jié)點(diǎn)變紅色瑟蜈，再祖父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋
4.png

第二種情況：父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右孩子(和上面情況一樣，將左全部變成右即可)

3渣窜、刪除節(jié)點(diǎn)

刪除節(jié)點(diǎn)：先進(jìn)行二叉排序樹的刪除操作铺根，然后已替換節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)進(jìn)行后面的平衡操作

1. 當(dāng)前節(jié)點(diǎn)是紅色。對策：直接把當(dāng)前節(jié)點(diǎn)染成黑色乔宿，結(jié)束位迂。

2. 當(dāng)前節(jié)點(diǎn)x是黑色，分以下幾種情況：

第一種情況：被刪除節(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子

2.1 當(dāng)前節(jié)點(diǎn)是根節(jié)點(diǎn)
對策：什么都不做
2.2 當(dāng)前節(jié)點(diǎn)x的兄弟節(jié)點(diǎn)是紅色(此時(shí)父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)分為黑)
對策：把父節(jié)點(diǎn)染成紅色详瑞，兄弟節(jié)點(diǎn)染成黑色掂林，對父節(jié)點(diǎn)進(jìn)行左旋，重新設(shè)置x的兄弟節(jié)點(diǎn)
5.png
2.3 當(dāng)前節(jié)點(diǎn)x 的兄弟節(jié)點(diǎn)是黑色
2.3.1 兄弟節(jié)點(diǎn)的兩個(gè)孩子都是黑色
對策：將x的兄弟節(jié)點(diǎn)設(shè)為紅色坝橡，設(shè)置x的父節(jié)點(diǎn)為新的x節(jié)點(diǎn)
6.png
2.3.2 兄弟的右孩子是黑色泻帮，左孩子是紅色
對策：將x兄弟節(jié)點(diǎn)的左孩子設(shè)為黑色，將x兄弟節(jié)點(diǎn)設(shè)置紅色计寇，將x的兄弟節(jié)點(diǎn)右旋刑顺，右旋后氯窍，重新設(shè)置x的兄弟節(jié)點(diǎn)。
7.png
2.3.3 兄弟節(jié)點(diǎn)的右孩子是紅色
對策：把兄弟節(jié)點(diǎn)染成當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)顏色蹲堂，把當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)染成黑色狼讨，兄弟節(jié)點(diǎn)右孩子染成黑色，再以當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋柒竞，算法結(jié)算
8.png

第二種情況：被刪除節(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子（對策： 把第一種情況的左設(shè)置為右）

4政供、完整代碼（代碼有詳細(xì)的注釋）

import java.util.LinkedList;

/**
 * 紅黑樹
 * <p>
 * author: bobo
 * create time: 2018/12/18 3:39 PM
 * email: jqbo84@163.com
 */
public class RBTree<E extends Comparable<E>> {

    private static final boolean BLACK = true;
    private static final boolean RED = false;

    private Node<E> root;

    private int size;

    public Node<E> getRoot() {
        return root;
    }

    public int getSize() {
        return size;
    }

    /**
     * 獲取顏色值
     *
     * @param p
     */
    private boolean colorOf(Node<E> p) {
        return (p == null ? BLACK : p.color);
    }

    /**
     * 獲取父節(jié)點(diǎn)
     *
     * @param p
     * @return
     */
    private Node<E> parentOf(Node<E> p) {
        return (p == null ? null : p.parent);
    }

    /**
     * 設(shè)置節(jié)點(diǎn)的顏色
     *
     * @param p
     * @param color
     */
    private void setColor(Node<E> p, boolean color) {
        if (p != null) {
            p.color = color;
        }
    }

    /**
     * 獲取當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)
     *
     * @param p
     * @return
     */
    private Node<E> leftOf(Node<E> p) {
        return (p == null ? null : p.leftChild);
    }

    /**
     * 獲取當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)
     *
     * @param p
     * @return
     */
    private Node<E> rightOf(Node<E> p) {
        return (p == null ? null : p.rightChild);
    }

    /**
     * 左旋轉(zhuǎn)
     *
     * @param x
     */
    public void leftRotate(Node<E> x) {
        if (x == null) {
            return;
        }
        //1.先取到x的右結(jié)點(diǎn)
        Node<E> y = x.rightChild;
        //2.把??接上x的右結(jié)點(diǎn)上
        x.rightChild = y.leftChild;
        if (y.leftChild != null) {
            y.leftChild.parent = x;
        }
        //3.把y移到x的父結(jié)點(diǎn)上
        y.parent = x.parent;
        if (x.parent == null) {
            root = y;
        } else {
            if (x.parent.leftChild == x) {
                x.parent.leftChild = y;
            } else {
                x.parent.rightChild = y;
            }
        }
        y.leftChild = x;
        x.parent = y;
    }

    /**
     * 右旋轉(zhuǎn)
     *
     * @param x
     */
    public void rightRotate(Node<E> x) {
        if (x == null) {
            return;
        }
        //1.先取到x的左結(jié)點(diǎn)
        Node<E> y = x.leftChild;
        //2.把??接上x的左結(jié)點(diǎn)上
        x.leftChild = y.rightChild;
        if (y.rightChild != null) {
            y.rightChild.parent = x;
        }
        //3.把y移到x的父結(jié)點(diǎn)上
        y.parent = x.parent;
        if (x.parent == null) {
            root = y;
        } else {
            if (x.parent.leftChild == x) {
                x.parent.leftChild = y;
            } else {
                x.parent.rightChild = y;
            }
        }
        y.rightChild = x;
        x.parent = y;
    }

    /**
     * 插入節(jié)點(diǎn)：先按照二叉排序樹的方式插入一個(gè)節(jié)點(diǎn)，再查找最小不平衡子樹朽基，以最小不平衡子樹進(jìn)行下面的操作
     *
     * @param element
     * @return
     */
    public boolean insertElement(E element) {
        if (element == null) {
            return false;
        }
        Node<E> t = root;
        if (t == null) {
            root = new Node<>(element, null);
            size = 1;
            return true;
        }
        int cmp = 0;
        Node<E> parent = null;
        Comparable<E> e = element;
        //1.查找可以插入的位置
        do {
            parent = t;
            cmp = e.compareTo(t.element);
            if (cmp < 0) {//比父結(jié)點(diǎn)小布隔，那么查左結(jié)點(diǎn)
                t = t.leftChild;
            } else if (cmp > 0) {//比父結(jié)點(diǎn)大，那么查右結(jié)點(diǎn)
                t = t.rightChild;
            } else {//相等稼虎，說明是同一個(gè)數(shù)據(jù)衅檀，不需要插入
                return false;
            }
        } while (t != null);
        //2.找到可以插入的位置，進(jìn)行插入
        Node<E> child = new Node<>(element, parent);
        if (cmp < 0) {
            parent.leftChild = child;
        } else {
            parent.rightChild = child;
        }
        //平衡樹出現(xiàn)問題霎俩，需要修正
        fixAfterInsertion(child);
        size++;

        return true;
    }

    /**
     * 修正插入之后的平衡樹
     *
     * @param node
     */
    public void fixAfterInsertion(Node<E> node) {
        if (node == null) return;

        node.color = RED;

        while (node != null && node != root && node.parent.color == RED) {
            //1.父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左孩子哀军，有3種情況
            if (parentOf(node) == leftOf(parentOf(parentOf(node)))) {
                //取叔叔節(jié)點(diǎn)
                Node<E> uncleNode = rightOf(parentOf(parentOf(node)));
                if (colorOf(uncleNode) == RED) {//情況1：祖父節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn)（叔叔節(jié)點(diǎn)）是紅色
                    //對策： 將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)涂黑，祖父節(jié)點(diǎn)涂紅打却，把當(dāng)前節(jié)點(diǎn)指向祖父節(jié)點(diǎn)杉适，從新的當(dāng)前節(jié)點(diǎn)開始算法
                    setColor(parentOf(node), BLACK);
                    setColor(uncleNode, BLACK);
                    setColor(parentOf(parentOf(node)), RED);
                    node = parentOf(parentOf(node));
                } else {//情況2：叔叔節(jié)點(diǎn)是黑色
                    if (node == rightOf(parentOf(node))) {//情況2.1：當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右孩子
                        //對策：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)做為新的當(dāng)前節(jié)點(diǎn)，以新當(dāng)前節(jié)點(diǎn)為支點(diǎn)左旋柳击。
                        node = parentOf(node);
                        leftRotate(node);
                    }
                    //情況2.2：當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子
                    //對策：父節(jié)點(diǎn)變?yōu)楹谏惩疲娓腹?jié)點(diǎn)變紅色，再祖父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋
                    setColor(parentOf(node), BLACK);
                    setColor(parentOf(parentOf(node)), RED);
                    rightRotate(parentOf(parentOf(node)));
                }
            }
            //2.父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右孩子
            else {
                //取叔叔節(jié)點(diǎn)
                Node<E> uncleNode = leftOf(parentOf(parentOf(node)));
                if (colorOf(uncleNode) == RED) {//情況1：祖父節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn)（叔叔節(jié)點(diǎn)）是紅色
                    //對策： 將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)涂黑捌肴，祖父節(jié)點(diǎn)涂紅蹬叭，把當(dāng)前節(jié)點(diǎn)指向祖父節(jié)點(diǎn)，從新的當(dāng)前節(jié)點(diǎn)開始算法
                    setColor(parentOf(node), BLACK);
                    setColor(uncleNode, BLACK);
                    setColor(parentOf(parentOf(node)), RED);
                    node = parentOf(parentOf(node));
                } else {//情況2：叔叔節(jié)點(diǎn)是黑色
                    if (node == leftOf(parentOf(node))) {//情況2.1：當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子
                        //對策：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)做為新的當(dāng)前節(jié)點(diǎn)状知，以新當(dāng)前節(jié)點(diǎn)為支點(diǎn)右旋秽五。
                        node = parentOf(node);
                        rightRotate(node);
                    }
                    //情況2.2：當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右孩子
                    //對策：父節(jié)點(diǎn)變?yōu)楹谏娓腹?jié)點(diǎn)變紅色试幽，再祖父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋
                    setColor(parentOf(node), BLACK);
                    setColor(parentOf(parentOf(node)), RED);
                    leftRotate(parentOf(parentOf(node)));
                }
            }
        }
        root.color = BLACK;
    }

    /**
     * 根據(jù)當(dāng)前的值筝蚕，獲取當(dāng)前節(jié)點(diǎn)
     *
     * @param element
     * @return
     */
    public Node<E> getNode(E element) {
        if (element == null) {
            return null;
        }
        Node<E> t = root;
        Comparable<E> e = element;
        while (t != null) {
            int cmp = e.compareTo(t.element);
            if (cmp < 0) {
                t = t.leftChild;
            } else if (cmp > 0) {
                t = t.rightChild;
            } else {
                return t;
            }
        }
        return null;
    }

    /**
     * 獲取傳入P節(jié)點(diǎn)下面最小的節(jié)點(diǎn)
     *
     * @param p
     * @return
     */
    public Node<E> getMinLeftNode(Node<E> p) {
        if (p == null) {
            return null;
        }
        Node<E> t = p;
        while (t.leftChild != null) {
            t = t.leftChild;
        }
        return t;
    }

    /**
     * 刪除元素
     *
     * @param element
     */
    public void remove(E element) {
        //查找當(dāng)前的節(jié)點(diǎn)
        Node<E> node = getNode(element);
        if (node == null) {
            return;
        }
        deleteElement(node);
    }

    /**
     * 刪除當(dāng)前的節(jié)點(diǎn)
     *
     * @param node
     */
    public void deleteElement(Node<E> node) {

        if (node.leftChild != null && node.rightChild != null) {
            Node<E> s = getMinLeftNode(node.rightChild);
            node.element = s.element;
            node = s;
        }

        Node<E> t = (node.leftChild != null ? node.leftChild : node.rightChild);

        if (t == null) {
            Node<E> parent = node.parent;
            if (parent == null) {
                root = null;
            } else {
                // 注重：如果刪除節(jié)點(diǎn)是黑色，那么一定要先修正紅黑二叉樹铺坞，在做下面的刪除動作
                if (node.color == BLACK) {
                    fixAfterDeletion(node);
                }

                if (parent.leftChild == node) {
                    parent.leftChild = null;
                } else {
                    parent.rightChild = null;
                }
                node.parent = null;
            }
        } else {
            t.parent = node.parent;
            if (node.parent == null) {
                root = t;
            } else {
                if (node.parent.leftChild == node) {
                    node.parent.leftChild = t;
                } else {
                    node.parent.rightChild = t;
                }
            }
            node.leftChild = node.rightChild = node.parent = null;
            if (node.color == BLACK) {
                fixAfterDeletion(t);
            }
        }

        size--;
    }

    /**
     * 刪除節(jié)點(diǎn)后起宽，修正紅黑樹
     * @param node
     */
    public void fixAfterDeletion(Node<E> node) {
        while (node != root && colorOf(node) == BLACK) {
            if (leftOf(parentOf(node)) == node) { //被刪除節(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子
                //拿到node的兄弟節(jié)點(diǎn)
                Node<E> sib = rightOf(parentOf(node));
                if (colorOf(sib) == RED) { //2.2 當(dāng)前節(jié)點(diǎn)x的兄弟節(jié)點(diǎn)是紅色(此時(shí)父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)分為黑)
                    //對策：把父節(jié)點(diǎn)染成紅色，兄弟節(jié)點(diǎn)染成黑色济榨，對父節(jié)點(diǎn)進(jìn)行左旋坯沪，重新設(shè)置x的兄弟節(jié)點(diǎn)
                    setColor(parentOf(node), RED);
                    setColor(sib, BLACK);
                    leftRotate(parentOf(node));
                    sib = rightOf(parentOf(node));
                }
                if (colorOf(sib) == BLACK) {//2.3 當(dāng)前節(jié)點(diǎn)x 的兄弟節(jié)點(diǎn)是黑色
                    if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {//2.3.1 兄弟節(jié)點(diǎn)的兩個(gè)孩子都是黑色
                        //對策：將x的兄弟節(jié)點(diǎn)設(shè)為紅色，設(shè)置x的父節(jié)點(diǎn)為新的x節(jié)點(diǎn)
                        setColor(sib, RED);
                        node = parentOf(node);
                    } else {
                        if (colorOf(rightOf(sib)) == BLACK) {//2.3.2 兄弟的右孩子是黑色擒滑，左孩子是紅色
                            //對策：將x兄弟節(jié)點(diǎn)的左孩子設(shè)為黑色腐晾，將x兄弟節(jié)點(diǎn)設(shè)置紅色叉弦，將x的兄弟節(jié)點(diǎn)右旋，右旋后藻糖，重新設(shè)置x的兄弟節(jié)點(diǎn)淹冰。
                            setColor(leftOf(sib), BLACK);
                            setColor(sib, RED);
                            rightRotate(sib);
                            sib = rightOf(parentOf(node));
                        }
                        //2.3.3 兄弟節(jié)點(diǎn)的右孩子是紅色
                        //對策：把兄弟節(jié)點(diǎn)染成當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)顏色，把當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)染成黑色巨柒，兄弟節(jié)點(diǎn)右孩子染成黑色樱拴，再以當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋，算法結(jié)算
                        setColor(sib, colorOf(parentOf(node)));
                        setColor(parentOf(node), BLACK);
                        setColor(rightOf(sib), BLACK);
                        leftRotate(parentOf(node));
                        node = root;
                    }
                }
            } else { //被刪除節(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子, 對策： 把上面的左設(shè)置為右
                //拿到node的兄弟節(jié)點(diǎn)
                Node<E> sib = leftOf(parentOf(node));
                if (colorOf(sib) == RED) { //2.2 當(dāng)前節(jié)點(diǎn)x的兄弟節(jié)點(diǎn)是紅色(此時(shí)父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)分為黑)
                    //對策：把父節(jié)點(diǎn)染成紅色洋满，兄弟節(jié)點(diǎn)染成黑色晶乔，對父節(jié)點(diǎn)進(jìn)行右旋，重新設(shè)置x的兄弟節(jié)點(diǎn)
                    setColor(parentOf(node), RED);
                    setColor(sib, BLACK);
                    rightRotate(parentOf(node));
                    sib = leftOf(parentOf(node));
                }
                if (colorOf(sib) == BLACK) {//2.3 當(dāng)前節(jié)點(diǎn)x 的兄弟節(jié)點(diǎn)是黑色
                    if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {//2.3.1 兄弟節(jié)點(diǎn)的兩個(gè)孩子都是黑色
                        //對策：將x的兄弟節(jié)點(diǎn)設(shè)為紅色牺勾，設(shè)置x的父節(jié)點(diǎn)為新的x節(jié)點(diǎn)
                        setColor(sib, RED);
                        node = parentOf(node);
                    } else {
                        if (colorOf(leftOf(sib)) == BLACK) {//2.3.2 兄弟的左孩子是黑色正罢，右孩子是紅色
                            //對策：將x兄弟節(jié)點(diǎn)的右孩子設(shè)為黑色，將x兄弟節(jié)點(diǎn)設(shè)置紅色驻民，將x的兄弟節(jié)點(diǎn)左旋翻具，左旋后，重新設(shè)置x的兄弟節(jié)點(diǎn)川无。
                            setColor(rightOf(sib), BLACK);
                            setColor(sib, RED);
                            leftRotate(sib);
                            sib = leftOf(parentOf(node));
                        }
                        //2.3.3 兄弟節(jié)點(diǎn)的左孩子是紅色
                        //對策：把兄弟節(jié)點(diǎn)染成當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)顏色呛占，把當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)染成黑色虑乖，兄弟節(jié)點(diǎn)左孩子染成黑色懦趋，再以當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋，算法結(jié)算
                        setColor(sib, colorOf(parentOf(node)));
                        setColor(parentOf(node), BLACK);
                        setColor(leftOf(sib), BLACK);
                        rightRotate(parentOf(node));
                        node = root;
                    }
                }
            }
        }
    }

    /**
     * 一層一層打印出數(shù)據(jù)
     *
     * @param root)
     */
    public void showRBTree(Node<E> root) {
        if (root == null) {
            return;
        }
        LinkedList<Node<E>> list = new LinkedList<>();
        list.offer(root);
        while (!list.isEmpty()) {
            Node<E> node = list.pop();
            System.out.println("node.element = " + node.element + ", color = " + node.color);
            if (node.leftChild != null) {
                list.offer(node.leftChild);
            }
            if (node.rightChild != null) {
                list.offer(node.rightChild);
            }
        }
    }

    /**
     * 紅黑樹結(jié)點(diǎn)
     *
     * @param <E>
     */
    public class Node<E extends Comparable>{
        E element;
        Node<E> leftChild;
        Node<E> rightChild;
        Node<E> parent;

        //0：黑色  1：紅色
        boolean color = BLACK;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }
}

5疹味、測試

@Test
public void testRBTree(){
    Integer[] nums = {13,8,5,11,6,22,27,25,14,17};
    RBTree<Integer> tree = new RBTree<>();
    for (int i = 0; i < nums.length; i++) {
        Integer num = nums[i];
        tree.insertElement(num);
    }
    tree.showRBTree(tree.getRoot());

    tree.remove(25);
    System.out.println("---------------------------------------- ");
    tree.showRBTree(tree.getRoot());

    System.out.println("---------------------------------------- ");
    for (Integer num : nums) {
        tree.remove(num);
        tree.showRBTree(tree.getRoot());
        System.out.println("------------------------------------ : " + num);
    }

}

測試結(jié)果： true：是黑色仅叫，false：是紅色
---------------打印插入數(shù)據(jù)--------------- 
node.element = 13, color = true
node.element = 8, color = false
node.element = 25, color = false
node.element = 5, color = true
node.element = 11, color = true
node.element = 17, color = true
node.element = 27, color = true
node.element = 6, color = false
node.element = 14, color = false
node.element = 22, color = false
---------------------------------------- 刪除: 25
node.element = 13, color = true
node.element = 8, color = false
node.element = 17, color = false
node.element = 5, color = true
node.element = 11, color = true
node.element = 14, color = true
node.element = 27, color = true
node.element = 6, color = false
node.element = 22, color = false
----------------循環(huán)刪除----------------- 
------------------------------------ 刪除: 13
node.element = 14, color = true
node.element = 8, color = false
node.element = 22, color = false
node.element = 5, color = true
node.element = 11, color = true
node.element = 17, color = true
node.element = 27, color = true
node.element = 6, color = false
------------------------------------ 刪除: 8
node.element = 14, color = true
node.element = 6, color = false
node.element = 22, color = false
node.element = 5, color = true
node.element = 11, color = true
node.element = 17, color = true
node.element = 27, color = true
------------------------------------ 刪除: 5
node.element = 14, color = true
node.element = 6, color = false
node.element = 22, color = false
node.element = 11, color = false
node.element = 17, color = true
node.element = 27, color = true
------------------------------------ 刪除: 11
node.element = 14, color = true
node.element = 6, color = false
node.element = 22, color = false
node.element = 17, color = true
node.element = 27, color = true
------------------------------------ 刪除: 6
node.element = 14, color = true
node.element = 22, color = false
node.element = 17, color = true
node.element = 27, color = true
------------------------------------ 刪除: 22
node.element = 14, color = true
node.element = 27, color = false
node.element = 17, color = false
------------------------------------ 刪除: 27
node.element = 14, color = true
node.element = 17, color = false
------------------------------------ 刪除: 25
node.element = 14, color = true
node.element = 17, color = false
------------------------------------ 刪除: 14
node.element = 17, color = false
------------------------------------ 刪除: 17

附上插入數(shù)據(jù)的紅黑樹 筆記 如圖：

9.jpg
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市糙捺，隨后出現(xiàn)的幾起案子诫咱，更是在濱河造成了極大的恐慌，老刑警劉巖洪灯，帶你破解...
    沈念sama閱讀 221,430評論 6贊 515
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件坎缭，死亡現(xiàn)場離奇詭異，居然都是意外死亡签钩，警方通過查閱死者的電腦和手機(jī)掏呼，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,406評論 3贊 398
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來铅檩，“玉大人憎夷，你說我怎么就攤上這事∶林迹” “怎么了拾给？”我有些...
    開封第一講書人閱讀 167,834評論 0贊 360
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵祥得，是天一觀的道長。 經(jīng)常有香客問我蒋得，道長级及，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 59,543評論 1贊 296
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任额衙，我火速辦了婚禮创千，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘入偷。我一直安慰自己追驴，他們只是感情好，可當(dāng)我...
    茶點(diǎn)故事閱讀 68,547評論 6贊 397
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布疏之。 她就那樣靜靜地躺著殿雪，像睡著了一般。 火紅的嫁衣襯著肌膚如雪锋爪。 梳的紋絲不亂的頭發(fā)上丙曙，一...
    開封第一講書人閱讀 52,196評論 1贊 308
  • 城市分裂傳說
    那天，我揣著相機(jī)與錄音其骄，去河邊找鬼亏镰。 笑死，一個(gè)胖子當(dāng)著我的面吹牛拯爽，可吹牛的內(nèi)容都是我干的索抓。 我是一名探鬼主播，決...
    沈念sama閱讀 40,776評論 3贊 421
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼毯炮，長吁一口氣：“原來是場噩夢啊……” “哼逼肯！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起桃煎，我...
    開封第一講書人閱讀 39,671評論 0贊 276
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對情侶失蹤篮幢，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后为迈，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體三椿，經(jīng)...
    沈念sama閱讀 46,221評論 1贊 320
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,303評論 3贊 340
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年葫辐，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了搜锰。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,444評論 1贊 352
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡另患，死狀恐怖纽乱，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情昆箕，我是刑警寧澤鸦列，帶...
    沈念sama閱讀 36,134評論 5贊 350
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布租冠，位于F島的核電站，受9級特大地震影響薯嗤，放射性物質(zhì)發(fā)生泄漏顽爹。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,810評論 3贊 333
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一骆姐、第九天 我趴在偏房一處隱蔽的房頂上張望镜粤。 院中可真熱鬧，春花似錦玻褪、人聲如沸肉渴。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,285評論 0贊 24
  • 一樁弒父案带射，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽同规。三九已至，卻和暖如春窟社，著一層夾襖步出監(jiān)牢的瞬間券勺，已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,399評論 1贊 272
  • 情欲美人皮
    我被黑心中介騙來泰國打工灿里， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留关炼，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,837評論 3贊 376
  • 代替公主和親
    正文 我出身青樓匣吊，卻偏偏與公主長得像儒拂，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子缀去，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,455評論 2贊 359

推薦閱讀更多精彩內(nèi)容

  • 上一篇：Java集合-ConcurrentHashMap工作原理和實(shí)現(xiàn)JDK8 本文學(xué)習(xí)知識點(diǎn) 1侣灶、二叉查找樹甸祭，以...
    Misout閱讀 13,873評論 9贊 67
  • 樹的概述 樹是一種非常常用的數(shù)據(jù)結(jié)構(gòu)缕碎，樹與前面介紹的線性表，棧池户，隊(duì)列等線性結(jié)構(gòu)不同咏雌，樹是一種非線性結(jié)構(gòu) 1.樹的定...
    Jack921閱讀 4,462評論 1贊 31
  • 1、紅黑樹介紹 紅黑樹又稱R-B Tree校焦，全稱是Red-Black Tree赊抖，它是一種特殊的二叉查找樹，紅黑樹的...
    文哥的學(xué)習(xí)日記閱讀 9,879評論 1贊 35
  • 0.目錄 1.算法導(dǎo)論的紅黑樹本質(zhì)上是2-3-4樹 2.紅黑樹的結(jié)構(gòu)和性質(zhì) 3.紅黑樹的插入 4.紅黑樹的刪除 5...
    王偵閱讀 2,485評論 1贊 2
  • 1. 網(wǎng)頁設(shè)計(jì) （來源網(wǎng)站：nipponcolors.com） 日本の伝統(tǒng)色寨典，日本的一個(gè)關(guān)于顏色的網(wǎng)站氛雪，功能明確，...
    護(hù)林員閱讀 381評論 0贊 1