DS05.4:红黑树

概述

红黑树的定义与性质

红黑树与AVL树一样，也是一个自平衡的二叉搜索树，其中节点使用“红”与“黑”进行标注。

关于对红黑树的理解，根据23树的相关定义可以很快的认识。

基本性质

1. 每个节点或者是红色的，或者是黑色的。
2. 根节点是黑色的。
3. 每一个叶子节点（最后的空节点）是黑色的。
4. 如果一个节点是红色的，那么他的孩子节点都是黑色的
5. 从任意一个节点到叶子节点，经过的黑色节点是一样的。

显然，根据第5条性质，可以知道红黑树是保持“黑平衡”的二叉树。因此严格意义上不是平衡二叉树，最大高度2log n（每个黑节点都带个红节点）

时间复杂度

红黑树执行查找、插入、删除等操作的时间复杂度为 O(logN)

与AVL树的比较

显然，如果单纯按照树的高度这一标准看，红黑树似乎比不上AVL树的性能，但红黑树添加元素、删除元素较AVL树更快（由于没有AVL树要求那么严格，因此为维护平衡进行的旋转操作相对较少），在整体性能上优于AVL树，所以这是一个相当重要的数据结构。

• 当元素偏向于固定，主要进行查询等操作时，使用AVL树更优

• 当需要频繁的进行插入与删除操作时，则使用红黑树更优。

操作

红黑树的操作绝大部分与二叉搜索树相同，不同的地方与AVL树相同，主要在维护自平衡上，集中表现在插入与删除的过程。维护的时机也与AVL树一致，在添加节点后回溯向上维护（简单来讲就是代码应该写在插入的递归业务之后，采用后序的思想）

辅助方法

基本Node类

设置插入节点的初始颜色：红色。

理由：红色在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。（得时刻记住，红黑树是一个黑节点平衡的树）

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

private class Node {
    public E e;
    public Node left, right;
    public boolean color;

    public Node(E e) {
        this.e = e;
        left = null;
        right = null;
        color = RED;	// 初始节点设置为红色
    }
}

判断当前节点是否为红色

private boolean isRed(Node node) {
    if(node == null)
        return BLACK;
    return RED;
}

左旋

//   node                     x
//  /   \     左旋转         /  \
// T1   x   --------->   node   T3
//     / \              /   \
//    T2 T3            T1   T2
private Node leftRotate(Node node) {
    Node x = node.right;

    node.right = x.left;
    x.left = node;

    x.color = node.color;
    node.color = RED;

    return x;
}

右旋

//     node                   x
//    /   \     右旋转       /  \
//   x    T2   ------->   y   node
//  / \                       /  \
// y  T1                     T1  T2
private Node rightRotate(Node node) {
    Node x = node.left;
    node.left = x.right;
    x.right = node;

    x.color = node.color;
    node.color = RED;

    return x;
}

颜色翻转

private void flipColors(Node node) {
    node.color = RED;
    node.left.color = BLACK;
    node.right.color = BLACK;
}

插入

插入时可能会遇到的情况下图已经总结的很清楚了。主要考虑情景4

而情景4主要可以分为以下①②③三种插入情况，其实是可以分别转化的

这三种操作具体可见辅助方法中的代码。同时应当注意，在这种代码实现下，红节点是只会出现在左孩子上的（由于颜色翻转的实现）

情况③

这种情况直接插入并进行颜色翻转操作。

情况②

这种情况先进行右旋再进行颜色翻转

情况①

先进行左旋转、再进行右旋转、最后进行颜色反转

// 向红黑树中添加新元素
public void add(E e) {
    root = add(root, e);
    root.color = BLACK;	// 设置根节点为黑
}
    
private Node add(Node node, E e) {
    if(node == null) {
        size++;
        return new Node(e);
    }
    if(e.compareTo(node.e) < 0) {
        node.left = add(node.left, e);
    }
    else if(e.compareTo(node.e) >0) {
        node.right = add(node.right, e);
    }

	// 情况1
    if(isRed(node.right) && !isRed(node.left))
        node = leftRotate(node);
    // 情况2
    if(isRed(node.left) && isRed(node.left.left))
        node = rightRotate(node);
    // 情况3
    if(isRed(node.left) && isRed(node.right))
        flipColors(node);
        
    return node;
}

参考链接

https://www.jianshu.com/p/e136ec79235c 这篇文章对红黑树阐述的特别详细，其实要了解红黑树看这一篇就行了。

Donate