红黑树 - litter-fish/ReadSource GitHub Wiki

二叉查找树

介绍

特点

  1. 若存在左子树则左子树的所有值都小于根节点值
  2. 若存在右子树则右子树的所有值都大于根节点的值
  3. 任意节点的左、右孩子也分别是二叉查找树
  4. 没有键值相等的节点

插入操作

  1. 如果节点小于新加入的值则在左孩子中加入
  2. 如果节点大于新加入的则在右节点中加入

删除操作

  1. 如果左孩子和右孩子都不存在，直接删除节点即可
  2. 如果存在右孩子且不存在左孩子，则将右孩子赋值给节点即可
  3. 如果存在左孩子且右孩子不存在，则将左孩子赋值该节点
  4. 如果左右孩子都不为空，则找到右孩子最小的节点，和最小孩子进行交换操作，删除最小孩子

源码实现

public class BiTree {

    private volatile static BiTNode<Integer> root;

    public BiTree() {
        root = new BiTNode<>();
    }

    public static boolean insert(Integer data) {

        BiTNode<Integer> newNode = new BiTNode<>(data);

        if (root == null) {
            root = new BiTNode<>(data);
        } else {
            return doInsert(root, newNode);
        }

        return true;
    }

    private static boolean doInsert(BiTNode<Integer> root, BiTNode<Integer> newNode) {
        // 如果节点小于新加入的值则在左孩子中加入
        if (root.data > newNode.data) {
            if (root.left == null) {
                root.left = newNode;
            } else {
                return doInsert(root.left, newNode);
            }
        // 如果节点大于新加入的则在右节点中加入
        } else if (root.data < newNode.data) {
            if (root.right == null) {
                root.right = newNode;
            } else {
                return doInsert(root.right, newNode);
            }
        } else {
            return false;
        }

        return true;
    }


    public static BiTNode delete(Integer data) {

        if (root == null) {
            return null;
        } else {
            return doDelete(root, data);
        }
    }

    private static BiTNode doDelete(BiTNode<Integer> node, Integer data) {

        if (node == null) {
            return null;
        }

        if (node.data > data) {
            doDelete(node.left, data);
        } else if (node.data < data) {
            doDelete(node.right, data);
        } else {
            // 如果左孩子和右孩子都不存在，直接删除节点即可
            if (node.right == null && node.left == null) {
                node = null;
                return node;
            }
            // 如果存在右孩子且不存在左孩子，则将右孩子赋值给节点即可
            if (node.right != null && node.left == null) {
                node = node.right;
                return node;
            }
            // 如果存在左孩子且右孩子不存在，则将左孩子赋值该节点
            if (node.left != null && node.right == null) {
                node = node.left;
                return node;
            }

            // 如果左右孩子都不为空，则找到右孩子最小的节点，和最小孩子进行交换操作，删除最小孩子
            BiTNode<Integer> minNode = findMinNode(node.right);
            node.data = minNode.data;

            doDelete(minNode, data);

        }

        return null;
    }

    public static BiTNode<Integer> findMinNode(BiTNode<Integer> minNode) {
        while (minNode != null && minNode.left != null) {
            minNode = minNode.left;
        }

        return minNode;
    }

    public static BiTNode<Integer> search(Integer data) {
        if (data == null) {
            return null;
        } else {
            return doSearch(root, data);
        }
    }

    private static BiTNode<Integer> doSearch(BiTNode<Integer> node, Integer data) {
        if(node == null) {
            return null;
        }
        if (node.data > data) {
            return doSearch(node.left, data);
        } else if (node.data < data) {
            return doSearch(node.right, data);
        } else {
            return node;
        }
    }


    public static void main(String[] args) {
        insert(12);
        insert( 10);
        insert(100);
        insert(40);
        insert(20);
        insert(6);
        insert(11);
        insert(120);
        insert(105);
        insert(101);
        insert(106);
        insert(130);
        System.out.println(root);
        delete(100);
        System.out.println(search(40));
    }

}

class BiTNode<T> {
    T data;
    BiTNode left;
    BiTNode right;

    public BiTNode() {

    }

    public BiTNode(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public BiTNode getLeft() {
        return left;
    }

    public void setLeft(BiTNode left) {
        this.left = left;
    }

    public BiTNode getRight() {
        return right;
    }

    public void setRight(BiTNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "BiTNode{" +
                "data=" + data +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}

AVL树

介绍

带有平衡条件的二叉查询树

每个节点的左右子树的高度差不超过1的二叉查询树

旋转

按照插入位置分类 右旋 如图所示，插入节点12 后，节点20 平衡被破坏，需要将节点 20 进行右旋。 操作步骤：

  1. 节点20的左节点指向17的右节点即18
  2. 节点20的左节点17，指向节点20

2372733a18f10b1c0f8b8b2b8fdbf1c8.png

源码

/**
 * 右旋操作
 * @param root 需要做右旋的节点
 * @return
 */
private static AVLBiTNode<Integer> rotateRight(AVLBiTNode<Integer> root) {
    // 暂存左节点
    AVLBiTNode<Integer> left = root.left;
    // 节点左孩子指向节点左孩子的右节点
    root.left = left.right;
    // 左节点的右子树指向原节点，左子树“上升”，父节点“下沉”
    left.right = root;

    left.height = Math.max(getHeight(left.left), getHeight(left.right)) + 1;
    if (left.right != null) {
        left.right.height = Math.max(getHeight(left.right.left), getHeight(left.right.right)) + 1;
    }

    return left;
}

左旋 如图所示，插入节点 6 后，节点 2 平衡被破坏，需要将节点 2 进行左旋。 操作步骤：

  1. 节点 2 的右节点指向节点4的左节点
  2. 节点4的左节点指向节点2

6c189b021437e66bcb08a560cec07d9e.png

源码

/**
 * 左旋操作
 * @param root 需要做左旋的节点。
 * @return
 */
private static AVLBiTNode<Integer> rotateLeft(AVLBiTNode<Integer> root) {
    // 暂存右节点
    AVLBiTNode<Integer> right = root.right;
    // 右节点指向右节点的左子树
    root.right = right.left;
    // 将右节点的左子树指向当前需要旋转的节点，即完成旋转
    right.left = root;
    // 重新计算旋转后的节点高度，旋转后节点位置提升了将节点高度+1，这边直接取了原来父节点的高度值
    right.height = Math.max(getHeight(right.left), getHeight(right.right)) + 1;
    // 旋转后原来的节点，“下沉了”，所有高度相应的减去1
    if (right.left != null) {
        right.left.height = Math.max(getHeight(right.left.left), getHeight(right.left.right)) + 1;
    }
    return right;
}

先左旋再右旋，节点的左节点的右子树上插入节点 如图所示，插入节点 19 后，节点 20 的平衡被破坏，先将节点 17 左旋，在将 20 右旋 操作步骤：

  1. 节点17的右节点指向节点18 的左节点
  2. 节点18的左节点指向节点17
  3. 在将节点20 右旋
  4. 将节点20的左节点指向18的右节点
  5. 节点18的右节点指向20

83ee34b9d42bd81e909f0ea62b0a9da6.png

源码

/**
 * 先将右节点进行右旋，然后进行左旋操作
 * @param root 破坏平衡的子树
 * @return 已经平衡的子树
 */
private static AVLBiTNode<Integer> rotateBeforeRightAfterLeft(AVLBiTNode<Integer> root) {
    //先右旋
    root.right = rotateRight(root.right);
    // 父节点“下沉”，高度减去1
    root.right.height = getHeight(root) - 1;
    //再左旋
    root = rotateLeft(root);

    return root;
}

先右旋再左旋，节点的右节点的左子树上插入节点 f5e6108a9b461f2855b0cc4cb3029014.png

源码

/**
 * 先将左节点进行右旋，然后进行左旋操作
 * @param root 破坏平衡的子树
 * @return 已经平衡的子树
 */
private static AVLBiTNode<Integer> rotateBeforeLeftAfterRight(AVLBiTNode<Integer> root) {
    //先左旋
    root.left = rotateLeft(root.left);
    // 父节点“下沉”，高度减去1
    root.left.height = getHeight(root) - 1;
    //再右旋
    root = rotateRight(root);

    return root;
}

插入操作

数据结构

class AVLBiTNode<T> {
    T data;
    AVLBiTNode left;
    AVLBiTNode right;
    int height;
}

插入操作

public class AVLBiTree {

    private volatile static AVLBiTNode<Integer> rootNode;

    //允许的高度差，超过该值即视为不平衡，此处定义为1
    private static final int ALLOWED_HEIGHT_DIFF = 1;

    public AVLBiTree() {
        rootNode = new AVLBiTNode<>();
    }

   public static boolean insert(Integer data) {

    AVLBiTNode<Integer> newNode = new AVLBiTNode<>(data);

    if (rootNode == null) {
        rootNode = new AVLBiTNode<>(data);
    } else {
        rootNode = doInsert(rootNode, newNode);
        rootNode.height = Math.max(getHeight(rootNode.left), getHeight(rootNode.right)) + 1;
    }
    return true;
}

private static AVLBiTNode<Integer> doInsert(AVLBiTNode<Integer> parent, AVLBiTNode<Integer> newNode) {
    AVLBiTNode<Integer> tempNode = parent;
    // 如果节点小于新加入的值则在左孩子中加入
    if (parent.data > newNode.data) {
        if (parent.left == null) {
            parent.left = newNode;
            parent.height = Math.max(getHeight(parent.left), getHeight(parent.right)) + 1;
        } else {
            tempNode = doInsert(parent.left, newNode);
            parent.left = tempNode;
            parent.height = Math.max(getHeight(parent.left), getHeight(parent.right)) + 1;
            tempNode = rotate(parent);
        }
    // 如果节点大于新加入的则在右节点中加入
    } else if (parent.data < newNode.data) {
        // 如果不存在右节点则将新加入的节点设置为其右节点，否则继续递归
        if (parent.right == null) {
            parent.right = newNode;
            parent.height = Math.max(getHeight(parent.left), getHeight(parent.right)) + 1;
        } else {
            tempNode = doInsert(parent.right, newNode);
            parent.right = tempNode;
            parent.height = Math.max(getHeight(parent.left), getHeight(parent.right)) + 1;
            tempNode = rotate(parent);
        }
    } else {
        return parent;
    }
    tempNode.height = Math.max(getHeight(tempNode.left), getHeight(tempNode.right)) + 1;
    return tempNode;
}

    public static int getHeight(AVLBiTNode<Integer> root){

        return root == null ? -1 : root.height;
    }

}

树的旋转

/**
 * 旋转子树
 * @param parent 待旋转的子树
 * @return
 */
private static AVLBiTNode<Integer> rotate(AVLBiTNode<Integer> parent) {
    if (parent == null) {
        return null;
    }
    AVLBiTNode<Integer> root = parent;
    //newNode.height = getHeight(root) + 1;
    parent.height = Math.max(getHeight(parent.left), getHeight(parent.right)) + 1;
    if (getHeight(parent.left) - getHeight(parent.right) > ALLOWED_HEIGHT_DIFF) {
        if (getHeight(parent.left.left) > getHeight(parent.left.right)) {
            // 右旋
            root = rotateRight(root);
        } else {
            // 先将左节点进行右旋，然后进行左旋操作
            root = rotateBeforeLeftAfterRight(root);
        }
    } else if (getHeight(parent.right) - getHeight(parent.left) > ALLOWED_HEIGHT_DIFF) {
        if (getHeight(parent.right.right) > getHeight(parent.right.left)) {
            root = rotateLeft(root);
        } else {
            // 先将右节点进行右旋，然后进行左旋操作
            root = rotateBeforeRightAfterLeft(root);
        }
    }
    return root;
}

获取树的高度

/**
 * 获取树的高度
 * @param root 树的根
 * @return 返回树的高度，空树高度为-1
 */
public static int getHeight(AVLBiTNode<Integer> root){

    return root == null ? -1 : root.height;
}

删除操作

删除情况

  1. 如果左右节点都为空，则直接删除节点即可
  2. 如果删除的节点左子树或右子树存在一个非空的，则将其非空节点赋值给它即可
  3. 如果左右子树都不为空，根据左右子树的高度获取最大或最小的值，与之交换，后删除其即可 如果左子树的高度更大则找到左子树中最大值，与之交换，然后删除这个左子树的最大值 否则找到右子树中值最小的值，与之交换，然后删除这个最大值 完成删除节点后可能会破坏树的平衡，需要进行旋转

源码

public static AVLBiTNode delete(Integer data) {

    if (rootNode == null) {
        return null;
    } else {
        return doDelete(rootNode, data);
    }
}

private static AVLBiTNode doDelete(AVLBiTNode<Integer> node, Integer data) {

    if (node == null) {
        return null;
    }

    if (node.data > data) {
        node.left = doDelete(node.left, data);
        if (getHeight(node.right) - getHeight(node.left) > ALLOWED_HEIGHT_DIFF) {
            if (getHeight(node.right.right) > getHeight(node.right.left)) {
                node = rotateLeft(node);
            } else {
                // 先右旋，再左旋
                node = rotateBeforeRightAfterLeft(node);
            }
        }
    } else if (node.data < data) {
        node.right = doDelete(node.right, data);
        if (getHeight(node.left) - getHeight(node.right) > ALLOWED_HEIGHT_DIFF) {
            if (getHeight(node.left.left) > getHeight(node.left.right)) {
                // 右旋
                node = rotateRight(node);
            } else {
                // 先左旋，再右旋
                node = rotateBeforeLeftAfterRight(node);
            }
        }
    } else {
        // 如果左孩子和右孩子都不存在，直接删除节点即可
        // 如果左右孩子都不为空，则找到右孩子最小的节点，和最小孩子进行交换操作，删除最小孩子
        if (node.right != null && node.left != null ) {
            if (getHeight(node.left) > getHeight(node.right)) {
                AVLBiTNode<Integer> minNode = findMaxNode(node.left);
                Integer temp = node.data;
                node.data = minNode.data;
                minNode.data = temp;

                node.left = doDelete(node.left, data);
            } else {
                AVLBiTNode<Integer> minNode = findMinNode(node.right);
                Integer temp = node.data;
                node.data = minNode.data;
                minNode.data = temp;

                node.right = doDelete(node.right, data);
            }
        } else {
            node = (node.left != null) ? node.left : node.right;
        }
    }
    if (node != null)
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    return node;
}

查找最小值的节点

/**
 * 查找子树中最小值得节点，直接找到最左边的值
 * @param minNode 需要查找的子树
 * @return
 */
public static AVLBiTNode<Integer> findMinNode(AVLBiTNode<Integer> minNode) {
    while (minNode != null && minNode.left != null) {
        minNode = minNode.left;
    }

    return minNode;
}

查找最大值的节点

/**
 * 查找子树中最大值得节点，直接找到最右边的值
 * @param maxNode 需要查找的子树
 * @return
 */
public static AVLBiTNode<Integer> findMaxNode(AVLBiTNode<Integer> maxNode) {
    while (maxNode != null && maxNode.right != null) {
        maxNode = maxNode.right;
    }

    return maxNode;
}

遍历

层序遍历

public static void levelOrderFor(AVLBiTNode<Integer> root) {
    LinkedList<AVLBiTNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        AVLBiTNode<Integer> node = queue.poll();
        System.out.println(node);
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

查找操作

public static AVLBiTNode<Integer> search(Integer data) {
    if (data == null) {
        return null;
    } else {
        return doSearch(rootNode, data);
    }
}

private static AVLBiTNode<Integer> doSearch(AVLBiTNode<Integer> node, Integer data) {
    if(node == null) {
        return null;
    }
    if (node.data > data) {
        return doSearch(node.left, data);
    } else if (node.data < data) {
        return doSearch(node.right, data);
    } else {
        return node;
    }
}

红黑树

介绍

红黑树是一种自平衡的二叉查找树，可在O(logN)时间内完成查找，删除，插入等操作。

ce48ba4d39a9a64a9bb291dfeb6356e7.png

处理红黑树的核心思想：将红色的节点移到根节点；然后，将根节点设为黑色。 既然是“将红色的节点移到根节点”，那就是说要不断的将破坏红黑树特性的红色节点上移(即向根方向移动)

特点

  1. 节点要么是红要么是黑
  2. 根节点是黑色
  3. 所有叶子节点也是黑色（NIL节点）
  4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

旋转操作

左旋：将某个节点旋转为其右孩子的左孩子

deb911c6d4232b65cbbac93d4c900edb.jpeg 对x进行左旋，意味着"将x变成一个Y的左节点，B变成X的右孩子"。 给个例子

9a2260b4b1c53a568af942e12a3b879b.jpeg

右旋：将某个节点旋转为其左孩子的右孩子

144c5dd5dc6680b1f1cf4245ab283fc0.jpeg 对Y进行右旋，意味着"将Y变成一个X的右节点，B变为Y的左孩子" 给个例子

ff029b438f2828f7cb667dd72e5a136c.jpeg

右旋M步骤说明

  1. 将节点M的左孩子引用指向节点E的右孩子
  2. 将节点E的右孩子引用指向M，即完成右旋

dac0088d974a8e6f85f765d83bbd56db.jpeg

左旋E步骤说明

  1. 将节点E的右孩子引用指向节点M的左孩子
  2. 将节点M的左孩子引用指向E，即完成右旋转

插入操作

将要插入的节点标为N，N的父节点标为P，N的祖父节点标为G，N的叔父节点标为U

public static boolean insert(Integer data) {

    RedBlackTreeNode<Integer> newNode = new RedBlackTreeNode<>(data);

    if (rootNode == null) {
        rootNode = newNode;
    }
    rootNode = doInsert(rootNode, newNode);
    return true;
}

private static RedBlackTreeNode<Integer> doInsert(RedBlackTreeNode<Integer> node, RedBlackTreeNode<Integer> newNode) {
    if (node.data > newNode.data) {
        if (node.left == null) {
            newNode.parent = node;
            node.left = newNode;
            RedBlackTreeNode<Integer> tempNode = balance(newNode);
            do {
                node = tempNode;
            } while((tempNode = tempNode.parent) != null);
        } else {
            return doInsert(node.left, newNode);
        }
    // 如果节点大于新加入的则在右节点中加入
    } else if (node.data < newNode.data) {
        if (node.right == null) {
            newNode.parent = node;
            node.right = newNode;
            RedBlackTreeNode<Integer> tempNode = balance(newNode);
            do {
                node = tempNode;
            } while((tempNode = tempNode.parent) != null);

        } else {
            return doInsert(node.right, newNode);
        }
    } else {
        node = balance(node);
    }

    return node;
}

情形1: 新节点N位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑节点数目增加一，性质5符合。

private static RedBlackTreeNode<Integer> balance(RedBlackTreeNode<Integer> node) {
    // 情景1：新节点N位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑节点数目增加一，性质5符合
    if (node.parent == null) {
        node.color = 1;
        return node;
    }
   ......

    return node;
}

情形2：N节点的父节点是黑色

 private static RedBlackTreeNode<Integer> balance(RedBlackTreeNode<Integer> node) {
    // 情景1：新节点N位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑节点数目增加一，性质5符合
    ....
    // 情景2：N节点的父节点是黑色
    if (node.parent.color == 1) {
        return node;
    }
   ....

    return node;
}

情形3：父节点P和叔父节点U都为红色，需要重新绘制P、U为黑色，祖父G为红色，但是G节点可能是根节点也可能其父节点也是红色，因此需要按照情形1递归处理

720cd6adba9f6f32c0e028603b78032a.png

private static RedBlackTreeNode<Integer> balance(RedBlackTreeNode<Integer> node) {
    // 情景1：新节点N位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑节点数目增加一，性质5符合
    ....
    // 情景2：N节点的父节点是黑色
    ....
    // 情景3：父节点P和叔父节点U都为红色，需要重新绘制P、U为黑色，祖父G为红色，但是G节点可能是根节点也可能其父节点也是红色，因此需要按照情形1递归处理
    if (uncle(node) != null && uncle(node).color == 0) {
        node.parent.color = 1;
        uncle(node).color = 1;
        grandparent(node).color = 0;
        return balance(grandparent(node));
    }
    ....

    return node;
}

情形4：如果父节点P是红色，而叔父节点U是黑色，且新增节点N是P的右孩子，P是G的左孩子，此种情况，需要将节点P进行一次左旋操作，然后按照情形5进行操作

a74323bcf776f3c39024c1dd7085e625.png

 private static RedBlackTreeNode<Integer> balance(RedBlackTreeNode<Integer> node) {
    // 情景1：新节点N位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑节点数目增加一，性质5符合
    .......
    // 情景2：N节点的父节点是黑色
    ......
    // 情景3：父节点P和叔父节点U都为红色，需要重新绘制P、U为黑色，祖父G为红色，但是G节点可能是根节点也可能其父节点也是红色，因此需要按照情形1递归处理
    .....
    // 情形4.1：如果父节点P是红色，而叔父节点U是黑色，且新增节点N是P的右孩子，P是G的左孩子，此种情况，需要将节点P进行一次左旋操作，然后按照情形5.1进行操作
    if (node == node.parent.right && node.parent == grandparent(node).left) {
        node = rotateLeft(node.parent);
        return balance(node);
    // 情形4.2：如果父节点P是红色，而叔父节点U是黑色，且新增节点N是P的左孩子，P是G的右孩子，此种情况，需要将节点P进行一次右旋操作，然后按照情形5.2进行操作
    } 
    .....
    return node;
}

情形5：如果父节点P是红色，且其叔父节点U是黑色或缺失，同时新增节点N是P的左孩子且P也是G的左孩子，此时将节点祖父节点G进行一次右旋，并替换G和P节点的颜色 处理策略： (01) 将“父节点”设为“黑色”。 (02) 将“祖父节点”设为“红色”。 (03) 以“祖父节点”为支点进行右旋。

41f38672ba6104d08be22798c7a4e961.png

 private static RedBlackTreeNode<Integer> balance(RedBlackTreeNode<Integer> node) {
    // 情景1：新节点N位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑节点数目增加一，性质5符合
    .....
    // 情景2：N节点的父节点是黑色
    ......
    // 情景3：父节点P和叔父节点U都为红色，需要重新绘制P、U为黑色，祖父G为红色，但是G节点可能是根节点也可能其父节点也是红色，因此需要按照情形1递归处理
    ......
    // 情形4.1：如果父节点P是红色，而叔父节点U是黑色，且新增节点N是P的右孩子，P是G的左孩子，此种情况，需要将节点P进行一次左旋操作，然后按照情形5.1进行操作
    ......
    // 情形4.2：如果父节点P是红色，而叔父节点U是黑色，且新增节点N是P的左孩子，P是G的右孩子，此种情况，需要将节点P进行一次右旋操作，然后按照情形5.2进行操作
    ......
    // 情形5.1：如果父节点P是红色，且其叔父节点U是黑色或缺失，同时新增节点N是P的左孩子且P也是G的左孩子，此时将节点祖父节点G进行一次右旋，并替换G和P节点的颜色
    } else if (node == node.parent.left && node.parent == grandparent(node).left) {
        node.parent.color = 1;
        grandparent(node).color = 0;
        node = rotateRight(grandparent(node));
    // 情形5.2：如果父节点P是红色，且其叔父节点U是黑色或缺失，同时新增节点N是P的右孩子且P也是G的右孩子，此时将节点祖父节点G进行一次左旋，并替换G和P节点的颜色
    } else if (node == node.parent.right && node.parent == grandparent(node).right) {
        node.parent.color = 1;
        grandparent(node).color = 0;
        node = rotateLeft(grandparent(node));
    }

    return node;
}

平衡的处理

private static RedBlackTreeNode<Integer> balance(RedBlackTreeNode<Integer> node) {
    // 情景1：新节点N位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑节点数目增加一，性质5符合
    if (node.parent == null) {
        node.color = 1;
        return node;
    }
    // 情景2：N节点的父节点是黑色
    if (node.parent.color == 1) {
        return node;
    }
    // 情景3：父节点P和叔父节点U都为红色，需要重新绘制P、U为黑色，祖父G为红色，但是G节点可能是根节点也可能其父节点也是红色，因此需要按照情形1递归处理
    if (uncle(node) != null && uncle(node).color == 0) {
        node.parent.color = 1;
        uncle(node).color = 1;
        grandparent(node).color = 0;
        return balance(grandparent(node));
    }
    // 情形4.1：如果父节点P是红色，而叔父节点U是黑色，且新增节点N是P的右孩子，P是G的左孩子，此种情况，需要将节点P进行一次左旋操作，然后按照情形5.1进行操作
    if (node == node.parent.right && node.parent == grandparent(node).left) {
        node = rotateLeft(node.parent);
        return balance(node);
    // 情形4.2：如果父节点P是红色，而叔父节点U是黑色，且新增节点N是P的左孩子，P是G的右孩子，此种情况，需要将节点P进行一次右旋操作，然后按照情形5.2进行操作
    } else if (node == node.parent.left && node.parent == grandparent(node).right) {
        node = rotateRight(node.parent);
        return balance(node);
    // 情形5.1：如果父节点P是红色，且其叔父节点U是黑色或缺失，同时新增节点N是P的左孩子且P也是G的左孩子，此时将节点祖父节点G进行一次右旋，并替换G和P节点的颜色
    } else if (node == node.parent.left && node.parent == grandparent(node).left) {
        node.parent.color = 1;
        grandparent(node).color = 0;
        node = rotateRight(grandparent(node));
    // 情形5.2：如果父节点P是红色，且其叔父节点U是黑色或缺失，同时新增节点N是P的右孩子且P也是G的右孩子，此时将节点祖父节点G进行一次左旋，并替换G和P节点的颜色
    } else if (node == node.parent.right && node.parent == grandparent(node).right) {
        node.parent.color = 1;
        grandparent(node).color = 0;
        node = rotateLeft(grandparent(node));
    }

    return node;
}

左旋

/**
 * 左旋操作
 * @param root 需要做左旋的节点。
 * @return
 */
private static RedBlackTreeNode<Integer> rotateLeft(RedBlackTreeNode<Integer> root) {
    RedBlackTreeNode<Integer> parent = root.parent;
    // 暂存右节点
    RedBlackTreeNode<Integer> right = root.right;
    // 右节点指向右节点的左子树
    root.right = right.left;
    // 将右节点的左子树指向当前需要旋转的节点，即完成旋转
    right.left = root;
    right.left.parent = right;

    right.parent = parent;
    if (parent != null)
        parent.left = right;

    return root;
}

右旋

/**
 * 右旋操作
 * @param root 需要做右旋的节点
 * @return
 */
private static RedBlackTreeNode<Integer> rotateRight(RedBlackTreeNode<Integer> root) {
    RedBlackTreeNode<Integer> parent = root.parent;
    // 暂存左节点
    RedBlackTreeNode<Integer> left = root.left;
    // 节点左孩子指向节点左孩子的右节点
    root.left = left.right;
    // 左节点的右子树指向原节点，左子树“上升”，父节点“下沉”
    left.right = root;
    left.right.parent = left;

    left.parent = parent;
    if (parent != null)
        parent.right = left;

    return root;
}

其他一些方法

/**
 * 获取叔父节点
 * @param node
 * @return
 */
private static RedBlackTreeNode<Integer> uncle(RedBlackTreeNode<Integer> node) {
    if (node == null) {
        return null;
    }
    if (node.parent == grandparent(node).left) {
        return grandparent(node).right;
    } else {
        return grandparent(node).left;
    }
}

/**
 * 获取祖父节点
 * @param node
 * @return
 */
private static RedBlackTreeNode<Integer> grandparent(RedBlackTreeNode<Integer> node) {
    if (node == null) {
        return null;
    }
    if (node.parent == null) {
        return null;
    }
    return node.parent.parent;
}

删除操作

假设存在如下一颗树，约定N为待删除的节点，兄弟节点为S。P为N的父亲，SL为S的左儿子，SR为S的右儿子。

8f29707c323d7944c6b8a4551c323f71.jpeg

删除情况说明

  1. 假如删除的节点N是一个红色的节点，直接删除即可并不会违反定义
  2. 假如待删除的节点N是一个黑色的节点，且其子节点是一个红色节点，直接用孩子节点替换删除节点，并修改节点的颜色即可
  3. 如果删除节点N是一个黑色的节点，且子节点也是黑色的，需要按照如下场景进行删除操作 情景1：N是新的根
if(p->parent == NULL){
        p->color = BLACK;
        return;
  }

情景2：删除节点的兄弟节点是一个红色节点

78dcec42a25e5593f5c298c8055bb197.png

if(p->sibling()->color == RED) {
    // 交换兄弟节点和父节点的颜色
    p->parent->color = RED;
    p->sibling()->color = BLACK;
    // 如果是父节点的左子树，则将父节点左旋，否则右旋父节点
    if(p == p->parent->leftTree)
        rotate_left(p->parent);
    else
        rotate_right(p->parent);
}

情景3：N的父节点、兄弟节点S和S的孩子都是黑色的。替换S颜色为红色，这边如果父亲节点P是一个根节点，即完成操作，如果上面还存在其他节点，则需要递归处理

03128e7b46b46b4fcae85576f92fb86c.png

if(p->parent->color == BLACK
        && p->sibling()->color == BLACK
        && p->sibling()->leftTree->color == BLACK 
        && p->sibling()->rightTree->color == BLACK) {
    p->sibling()->color = RED;
    delete_case(p->parent);
}

情形4：兄弟节点S即其孩子节点都是黑色，但父节点P是红色。交换兄弟节点S和父节点P的颜色

e4fd3b3b20cc556b8915d58864b80b51.png

if(p->parent->color == RED
            && p->sibling()->color == BLACK
            && p->sibling()->leftTree->color == BLACK
            && p->sibling()->rightTree->color == BLACK) {
        p->sibling()->color = RED;
        p->parent->color = BLACK;
 }

情形5：兄弟节点S是黑色的

ef9ef281ad1a7630bc09e04f616093ee.png

if (sibling(parent).color == 1) {
    // 情景5.1： N节点是父节点的左子树，且其左孩子SL是红色、右孩子SR是黑色的。将兄弟节点S的左孩子进行右旋操作，并交换S和SL的颜色
    if (parent == parent.parent.left
            && sibling(parent).left.color == 0
            && sibling(parent).right.color == 1) {
        sibling(parent).color = 0;
        sibling(parent).left.color = 1;
        rotateRight(sibling(parent).left);
    // 情景5.2： N节点是父节点的右子树，且其左孩子SL是黑色、右孩子SR是红色的。将兄弟节点S的右孩子进行左旋操作，并交换S和SR的颜色
    } else if (parent == parent.parent.right
            && sibling(parent).left.color == 1
            && sibling(parent).right.color == 0) {
        sibling(parent).color = 0;
        sibling(parent).right.color = 1;
        rotateLeft(sibling(parent).right);
    }
}

情景6：兄弟节点S是黑色，交换兄弟节点S和父节点P的颜色

34367fc71a7ba6853583b0b6bc3508aa.png

sibling(parent).color = parent.parent.color;
parent.parent.color = 1;
// 情景6.1：N是其父节点的左子树，将兄弟节点S做左旋操作
if (parent == parent.parent.left) {
    sibling(parent).right.color = 1;
    rotateLeft(sibling(parent));
// 情景6.2：N是其父节点的右子树，将兄弟节点S做右旋操作
} else {
    sibling(parent).left.color = 1;
    rotateRight(sibling(parent));
}

源码

public static RedBlackTreeNode<Integer> delete(Integer data) {

    if (rootNode == null) {
        return null;
    } else {
        return doDelete(rootNode, data);
    }
}

private static RedBlackTreeNode<Integer> doDelete(RedBlackTreeNode<Integer> node, Integer data) {
    if (node == null) {
        return null;
    }

    if (node.data > data) {
        if (node.left == null) {
            return null;
        }
       return doDelete(node.left, data);
    } else if (node.data < data) {
        if (node.right == null) {
            return null;
        }
        return doDelete(node.right, data);
    } else if (node.data == data) {
        if (node.right == null) {
            deleteOneChild(node);
            return null;
        }

        // 找到右子树中最小的值。
        RedBlackTreeNode<Integer> smallest = getSmallestChild(node.right);
        Integer dataValue = smallest.data;
        smallest.data = node.data;
        node.data = dataValue;
        deleteOneChild(smallest);
    }
    return null;
}

private static void deleteOneChild(RedBlackTreeNode<Integer> node) {
    RedBlackTreeNode<Integer> child = node.left == null ? node.right : node.left;

    // 如果删除的是根节点
    if (node.parent == null) {
        child.parent = null;
        rootNode = child;
        rootNode.color = 1;
        return;
    }

    if (node.parent.left == node) {
        node.parent.left = child;
    } else if (node.parent.right == node) {
        node.parent.right = child;
    }
    if (child == null)
        return;

    child.parent = node.parent;
    if (node.color == 1) {
        if (child.color == 0) {
            child.color = 1;
        } else {
            deleteCase(node);
        }
    }
    return;
}

private static void deleteCase(RedBlackTreeNode<Integer> parent) {

    // 情景1：N是新的根
    if (parent.parent == null) {
        parent.color = 1;
        return;
    }
    // 情景2：删除节点的兄弟节点是一个红色节点
    if (sibling(parent).color == 0) {
        parent.parent.color = 0;
        sibling(parent).color = 1;
        // 如果是父节点的左子树，则将父节点左旋，否则右旋父节点
        if (parent == parent.parent.left) {
            rotateLeft(parent.parent);
        } else {
            rotateRight(parent.parent);
        }
    }
    // 情景3：N的父节点、兄弟节点S和S的孩子都是黑色的。替换S颜色为红色，这边如果父亲节点P是一个根节点，即完成操作，如果上面还存在其他节点，则需要递归处理
    if (parent.parent.color == 1
            && sibling(parent).color == 1
            && sibling(parent).left.color == 1
            && sibling(parent).right.color == 1) {
        sibling(parent).color = 0;
        deleteCase(parent.parent);
    // 情形4：兄弟节点S即其孩子节点都是黑色，但父节点P是红色。交换兄弟节点S和父节点P的颜色
    } else if (parent.parent.color == 0
            && sibling(parent).color == 1
            && sibling(parent).left.color == 1
            && sibling(parent).right.color == 1) {
        sibling(parent).color = 0;
        parent.parent.color = 1;
    } else {
        // 情形5：兄弟节点S是黑色的
        if (sibling(parent).color == 1) {
            // 情景5.1： N节点是父节点的左子树，且其左孩子SL是红色、右孩子SR是黑色的。将兄弟节点S的左孩子进行右旋操作，并交换S和SL的颜色
            if (parent == parent.parent.left
                    && sibling(parent).left.color == 0
                    && sibling(parent).right.color == 1) {
                sibling(parent).color = 0;
                sibling(parent).left.color = 1;
                rotateRight(sibling(parent).left);
            // 情景5.2： N节点是父节点的右子树，且其左孩子SL是黑色、右孩子SR是红色的。将兄弟节点S的右孩子进行左旋操作，并交换S和SR的颜色
            } else if (parent == parent.parent.right
                    && sibling(parent).left.color == 1
                    && sibling(parent).right.color == 0) {
                sibling(parent).color = 0;
                sibling(parent).right.color = 1;
                rotateLeft(sibling(parent).right);
            }
        }

        // 情景6：兄弟节点S是黑色，交换兄弟节点S和父节点P的颜色
        sibling(parent).color = parent.parent.color;
        parent.parent.color = 1;
        // 情景6.1：N是其父节点的左子树，将兄弟节点S做左旋操作
        if (parent == parent.parent.left) {
            sibling(parent).right.color = 1;
            rotateLeft(sibling(parent));
        // 情景6.2：N是其父节点的右子树，将兄弟节点S做右旋操作
        } else {
            sibling(parent).left.color = 1;
            rotateRight(sibling(parent));
        }

    }
}

/**
 * 获取最小节点
 * @param node
 * @return
 */
private static RedBlackTreeNode<Integer>  getSmallestChild(RedBlackTreeNode<Integer> node) {
    if (node.left == null) {
        return node;
    }
    return getSmallestChild(node.left);
}
⚠️ **GitHub.com Fallback** ⚠️