数据结构与算法-红黑树

作者: 星空下奔跑 | 来源:发表于2018-04-18 23:29 被阅读0次

R-B Tree简介：

红黑树（Red-Black Tree），它是一种特殊的二叉查找树。红黑树的每个记录都有表示结点颜色的关键字，可以是红色(Red)或者黑色(Black)。
红黑树是一种特殊的平衡二叉树。

 //红黑树颜色
    enum Color {
        RED, BLACK
    }

    //红黑树节点
    class Node {
        Node rChild;
        Node lChild;
        Node parent;
        Color color;
        Object obj;
        int hash;

        Node(Color color) {
            this.color = color;

        }
    }

    //根结点
    class Root {
        Node node;
    }

红黑树的特性

1.每个结点或者是红色，或者是黑色。
2.根结点是黑色。
3.每个叶子结点（为空的结点）是黑色。
4.如果一个结点是红色的，则它的子结点必须是黑色的。
5.从一个结点到该结点的子孙结点的所有路径上包含相同数量的黑色结点。

红黑树的应用

红黑树的应用比较广泛，主要用来存储有序数据，它的时间复杂度为O(logn)，效率高。
例如，Java集合框架中的TreeSet，TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树实现的。

红黑树的基本操作

红黑树的左旋

与AVL树左旋一样。

 private void leftRotate(Node node) {
        Node rchild = node.rChild;
        rchild.parent = node.parent;
        rchild.rChild = node;

        node.parent = node.rChild;
        node.rChild = node.rChild.lChild;


        if (rchild.parent.lChild == node) {
            rchild.parent.lChild = rchild;
        } else {
            rchild.parent.rChild = rchild;
        }
        if (root.node == node) {
            root.node = node.parent;
        }

    }

红黑树的右旋

与AVL树的右旋一样

private void rightRotate(Node node) {
        //zuo haizi
        Node lchild = node.lChild;
        lchild.parent = node.parent;
        lchild.rChild = node;
        //ziji
        node.parent = lchild;
        node.lChild = lchild.rChild;


        //zufu
        if (lchild.parent.lChild == node) {
            lchild.parent.lChild = lchild;
        } else {
            lchild.parent.rChild = lchild;
        }
        if (root.node == node) {
            root.node = node.parent;
        }
    }

红黑树的插入

红黑树的插入与AVL的插入类似，先搜索红黑树找到插入位置进行插入，然后重新调整使之平衡（成为新的红黑树）。

情况1

当新插入的结点是根结点：直接将此结点涂黑。

Node newNode = new Node(Color.RED);
 if (root == null) {
            turnColorTo(newNode, Color.BLACK);
            root.node = newNode;
        }

情况2

当新插入的结点的父结点是黑色：满足红黑树性质。

情况3

当新插入的结点父结点是红色：该情况会破坏性质4和性质5。需要进行平衡和调整。
case1：
当父结点是红色，叔叔结点也是红色：
step1：将父结点设为黑色。
step2：将叔叔结点设为黑色。
step3：将祖父结点设为红色。
step4：将祖父结点设为“当前结点”（下一轮要调整的结点）。

if (current.parent.lChild == current && current.parent.rChild.color == Color.RED) {
            turnColorTo(current.parent, Color.BLACK);
            turnColorTo(current.parent.parent, Color.RED);
            turnColorTo(current.parent.parent.rChild, Color.BLACK);
            balanceRBT(current.parent.parent);
        } else if (current.parent.rChild == current && current.parent.lChild.color == Color.RED) {
            turnColorTo(current.parent, Color.BLACK);
            turnColorTo(current.parent.parent, Color.RED);
            turnColorTo(current.parent.parent.lChild, Color.BLACK);
            balanceRBT(current.parent.parent);
        }

case2：
当前结点的父结点是红色，叔叔结点是黑色，且当前结点是父结点的右孩子：
step1：将父结点作为“当前结点”。
step2：左旋。

if (current.parent.rChild == current && (current.parent.lChild == null || current.parent.lChild.color == Color.BLACK)) {
            leftRotate(current.parent);
            balanceRBT(current.parent);
            //当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子
        }

case3：当前结点的父结点是红色，叔叔结点是黑色，且当前结点是其父结点的左孩子：
step1：将父结点设为黑色。
step2：将祖父结点设为红色。
step3：设祖父结点为当前结点。
step4：右旋。

if (current.parent.lChild == current && (current.parent.rChild == null || current.parent.rChild.color == Color.BLACK)) {
            turnColorTo(current.parent, Color.BLACK);
            turnColorTo(current.parent.parent, Color.RED);
            rightRotate(current.parent.parent);
            balanceRBT(current);
        }

我们可以看出，如果是从情况1开始发生的，必然会走完情况2和3，也就是说这是一整个流程，当然咯，实际中可能不一定会从情况1发生，如果从情况2开始发生，那再走个情况3即可完成调整，如果直接只要调整情况3，那么前两种情况均不需要调整了。故变色和旋转之间的先后关系可以表示为：变色->左旋->右旋。

红黑树的删除

红黑树的删除与二叉查找树的删除是一样的，只不过删除之后多了平衡操作而已。
1.如果删除的结点没有子结点，直接删除。
2.如果待删除结点只有一个结点，用子结点代替，然后删除子结点即可。
3.如果待删除结点有两个结点，首先找到其后继结点（前驱也可以），然后用后继节点或前驱节点替换这个节点，之后再平衡红黑树。

 public void delete(Object obj) {
        int hash = hash(obj);
        Node root = this.root.node;
        Node cur = root;
        while (cur != null) {
            int h = hash(cur);

            if (hash < h) {
                cur = cur.lChild;
            } else if (hash > h) {
                cur = cur.rChild;
            }
        }
        cur = cur.parent;

        //两个孩子都是为空，是叶子节点
        if (cur.rChild == null && cur.lChild == null) {
            if (cur.parent.rChild == cur) {
                cur.parent.rChild = null;
            } else {
                cur.parent.lChild = null;
            }
        } else if (cur.rChild == null) {//左孩子不为空
            if (cur.parent.rChild == cur) {
                cur.parent.rChild = cur.lChild;
            } else {
                cur.parent.lChild = cur.lChild;
            }

        } else if (cur.lChild == null) {//右孩子不为空
            if (cur.parent.rChild == cur) {
                cur.parent.rChild = cur.rChild;
            } else {
                cur.parent.lChild = cur.rChild;
            }
        } else {//两个孩子非空
            Node forward = getForward(cur);


            if (cur.parent.rChild == cur) {
                cur.parent.rChild = forward;
            } else {
                cur.parent.lChild = forward;
            }

            forward.parent.rChild = null;
            forward.parent = cur.parent;
            forward.lChild = cur.lChild;
            forward.rChild = cur.rChild;

            //调整红黑树重新达到平衡
            balanceRBT(forward);
        }

    }

以下是自己实现的红黑树（未验证）

public class RedBlackTree {
    //红黑树颜色
    enum Color {
        RED, BLACK
    }

    //红黑树节点
    class Node {
        Node rChild;
        Node lChild;
        Node parent;
        Color color;
        Object obj;
        int hash;

        Node(Color color) {
            this.color = color;

        }
    }

    //根结点
    class Root {
        Node node;
    }

    private Root root;


    public void put(Object obj) {
        Node newNode = new Node(Color.RED);
        int hash = hash(obj);
        newNode.hash = hash;
        if (root == null) {
            turnColorTo(newNode, Color.BLACK);
            root.node = newNode;
        }

        insertNode(newNode, root.node);

        if (!isBalance(newNode)) {
            balanceRBT(newNode);
        }
    }

    public Node get(int hash) {

        Node cur = this.root.node;
        if (cur == null) return null;
        while (true) {

            if (hash > hash(cur)) {
                cur = cur.rChild;
            } else {
                cur = cur.lChild;
            }
            if (cur == null) return null;

        }

    }

    public void delete(Object obj) {
        int hash = hash(obj);
        Node root = this.root.node;
        Node cur = root;
        while (cur != null) {
            int h = hash(cur);

            if (hash < h) {
                cur = cur.lChild;
            } else if (hash > h) {
                cur = cur.rChild;
            }
        }
        cur = cur.parent;

        //两个孩子都是为空，是叶子节点
        if (cur.rChild == null && cur.lChild == null) {
            if (cur.parent.rChild == cur) {
                cur.parent.rChild = null;
            } else {
                cur.parent.lChild = null;
            }
        } else if (cur.rChild == null) {//左孩子不为空
            if (cur.parent.rChild == cur) {
                cur.parent.rChild = cur.lChild;
            } else {
                cur.parent.lChild = cur.lChild;
            }

        } else if (cur.lChild == null) {//右孩子不为空
            if (cur.parent.rChild == cur) {
                cur.parent.rChild = cur.rChild;
            } else {
                cur.parent.lChild = cur.rChild;
            }
        } else {//两个孩子非空
            Node forward = getForward(cur);


            if (cur.parent.rChild == cur) {
                cur.parent.rChild = forward;
            } else {
                cur.parent.lChild = forward;
            }

            forward.parent.rChild = null;
            forward.parent = cur.parent;
            forward.lChild = cur.lChild;
            forward.rChild = cur.rChild;

            //调整红黑树重新达到平衡
            balanceRBT(forward);
        }

    }

    private Node getForward(Node node) {
        Node cur = node.lChild;
        do {
            if (cur.rChild != null)
                cur = cur.rChild;
            else
                return cur;
        } while (true);
    }

    private void balanceRBT(Node current) {
        if (current == null || isBalance(current)) {
            return;
        }
        //当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子
        if (current.parent.rChild == current && (current.parent.lChild == null || current.parent.lChild.color == Color.BLACK)) {
            leftRotate(current.parent);
            balanceRBT(current.parent);
            //当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子
        } else if (current.parent.lChild == current && (current.parent.rChild == null || current.parent.rChild.color == Color.BLACK)) {
            turnColorTo(current.parent, Color.BLACK);
            turnColorTo(current.parent.parent, Color.RED);
            rightRotate(current.parent.parent);
            //当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。
        } else if (current.parent.lChild == current && current.parent.rChild.color == Color.RED) {
            turnColorTo(current.parent, Color.BLACK);
            turnColorTo(current.parent.parent, Color.RED);
            turnColorTo(current.parent.parent.rChild, Color.BLACK);
            balanceRBT(current.parent.parent);
        } else if (current.parent.rChild == current && current.parent.lChild.color == Color.RED) {
            turnColorTo(current.parent, Color.BLACK);
            turnColorTo(current.parent.parent, Color.RED);
            turnColorTo(current.parent.parent.lChild, Color.BLACK);
            balanceRBT(current.parent.parent);
        }

    }

    private boolean isBalance(Node current) {
        return current.parent.color != Color.RED;
    }

    private Node insertNode(Node src, Node node) {
        if (node == null) {
            return null;
        } else {
            Node next;
            if (node.hash > src.hash) {
                next = insertNode(src, node.lChild);
            } else {
                next = insertNode(src, node.rChild);
            }
            if (next == null) {
                insertTo(src, node);
            }
            return next;
        }

    }

    private void insertTo(Node src, Node dst) {
        if (src.hash < dst.hash) {
            dst.lChild = src;
        } else {
            dst.rChild = src;
        }
        src.parent = dst;
    }

    //利用对象的hash值作为排序依据
    public int hash(Object object) {
        return object == null ? -1 : object.hashCode();
    }

    private void turnColorTo(Node node, Color color) {
        if (node.color == Color.RED) {
            node.color = Color.BLACK;
        } else {
            node.color = Color.RED;
        }
    }

    private void rightRotate(Node node) {
        //zuo haizi
        Node lchild = node.lChild;
        lchild.parent = node.parent;
        lchild.rChild = node;
        //ziji
        node.parent = lchild;
        node.lChild = lchild.rChild;


        //zufu
        if (lchild.parent.lChild == node) {
            lchild.parent.lChild = lchild;
        } else {
            lchild.parent.rChild = lchild;
        }
        if (root.node == node) {
            root.node = node.parent;
        }
    }

    private void leftRotate(Node node) {
        Node rchild = node.rChild;
        rchild.parent = node.parent;
        rchild.rChild = node;

        node.parent = node.rChild;
        node.rChild = node.rChild.lChild;


        if (rchild.parent.lChild == node) {
            rchild.parent.lChild = rchild;
        } else {
            rchild.parent.rChild = rchild;
        }
        if (root.node == node) {
            root.node = node.parent;
        }

    }

数据结构与算法-红黑树

R-B Tree简介：

红黑树的特性

红黑树的应用

红黑树的基本操作

红黑树的左旋

红黑树的右旋

红黑树的插入

情况1

情况2

情况3

红黑树的删除

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读