聊聊红黑树

前言

大家都知道，如果二叉查找树不平衡的话，查找的时间复杂度就会降为O(n)，也就是说二叉查找树退化成链表了。因此，需要让二叉查找树维持平衡，这样就算在最坏的情况下，基本的操作的时间复杂度也会降低到O(logn)。

红黑树的几个性质

红黑树，结点上有一个存储位用来表示结点是红色的还是黑色的，因此叫红黑树。红黑树可以确保从根节点到叶结点的任意两条路径的长度不会相差两倍，因此红黑树是相对平衡的。

一颗二叉查找树需要满足一下的性质，才能称为红黑树：

• 每个结点要么红色，要么是黑色；
• 根节点为黑色的；
• 每个叶结点（NIL）是黑色的；
• 红结点的子节点只能是黑色，也就是说不能够出现两个红结点相邻的情况；
• 对于每个结点，从它出发到任意子结点的路径，黑结点的数量是相同的（称为黑高度相等）。

采取《算法导论》一书中对于红黑树的编写方法，设置一个哨兵对象NIL结点来作为所有结点的空结点，即对于没有子结点的结点，将它们的子结点指向NIL结点：

    A                       A
|       |       ->      |       |
NULL    NULL            NIL     NIL

旋转

二叉树的旋转是一种比较常见的操作，包括了左旋、右旋与双旋。

左旋是对结点进行逆时针旋转，让原本结点的右结点成为新的父结点，而原来的父结点成为新的父结点的左结点。右旋与左旋的情况相反，右旋为顺时针旋转，原来的左结点成为新的父结点，而原来的父结点成为新的父结点的右结点。

双旋包括了左旋后右旋与右旋后左旋。

左旋的为代码如下：

public void leftRotate(TreeNode node) {
    // 右结点成为新的父节点
    TreeNdoe newParent = node.right;

    // 原右结点的左子结点成为原父节点的右结点
    node.right = newParent.left;
    node.right.parent = node;

    // 右结点成为父节点，原父结点成为新父节点的左子结点
    newParent.left = node;
    newParent.parent = node.parent;
    node.parent = newParent;

    if (newParent.parent = nil) {
        // 根结点
        treeRoot = newParent;
    } else if (newParent.parent.left == node) {
        // 设置原父结点的父结点的左右子结点为新的父结点
        newParent.parent.left = newParent;
    } else {
        newParent.parent.right = newParent;
    }
}

插入

想红黑树中插入一个新的结点的时间复杂度为O(logn)，新的结点插入的方法与二叉查找树的插入方法基本相同，只不过多了几个步骤来保证红黑树的性质不会被破坏。在插入新结点之后，将新结点着色为红色，然后调用修复修复函数来对结点重新着色与旋转，保证红黑树的性质。

public void insert(TreeNdoe newNode) {
    TreeNode currRoot = treeRoot;
    TreeNode newParent = nil;
    while (currRoot != nil) {
        newParent = currRoot;
        if (newNode.value > currRoot.value) {
            // 插入到当前结点的右边
            currRoot = currRoot.right;
        } else if (newNode.value < currRoot.value) {
            // 插入到当前结点的左边
            currRoot = currRoot.left;
        } else {
            // 已经存在该结点，返回
            return;
        }
    }
    newNode.parent = newParent;
    if (newParent == nil) {
        // 新的结点成为根结点
        treeRoot = newNode;
    } else if (newParent.value > newNode.value) {
        // 新结点成为左结点
        newParent.left = newNdoe;
    } else {
        // 新结点成为右结点
        newParent.right = newNode;
    }
    newNode.left = nil;
    newNode.right = nil;
    newNode.color = red;
    fixUp(newNode);
}

private void fixUp(TreeNode newNode) {
    TreeNode currNode = newNode;
    // 直到结点的父结点颜色为黑色
    while (currNode.parent.color == red) {
        if (currNode.parent.left == currNode.parent) {
            // 当前结点的父结点是左结点
            TreeNode uncleNode = currNode.parent.parent.right;
            // 如果当前结点的叔结点是红色的，那么可以把红色结点上浮
            // 然后新的红色结点成为当前结点继续处理
            if (uncleNode.color == red) {
                uncleNode.color = black;
                currNode.parent.color = black;
                currNode = currNode.parent;
            } else if(currNode.parent.right == currNode) {
                // 如果当前结点是父节点的右子结点，则进行左旋操作
                currNode = currNode.parent;
                leftRotate(currNode);
                // 左旋之后右旋，然后黑结点上浮
                currNode.parent.color = black;
                currNode.parent.parent.color = red;
                rightRotate(currNode.parent.parent);
            }
        } else {
            // 跟上面对称的操作
        }
    }
    treeRoot.color = red;
}

删除

结点的删除比插入要复杂一些，分为两种情况讨论。一种是删除的结点为红色，这种情况下无需对红黑树进行修复操作，因为不影响黑高度。一种是删除的结点为黑色，删除黑结点之后黑高度势必会发生改变，因此要进行调整。

…未完待续