红黑树的实现原理及应用

算法红黑树

创建时间:2018-12-29 15:12

字数:2k 阅读:

什么是红黑树
红黑树的应用和时间复杂度
红色树的操作

完整实现

参考文献

@OTC

什么是红黑树

红黑树(R-B Tree, 全称 Red-Black Tree)是一种特殊的二叉查找树, 其中每个节点都有颜色, 红色或者黑色.
红黑树的特性:

树的节点是黑色或者红色
树的根节点和指向null的叶子节点都是黑色
不能有两个红色节点是连续的
每个节点至为null的子节点的任何路径, 都含有相同数量的黑色节点

示例:

             8B
            / \
           4R  9B
          /  \
        2B    6B
       /  \   / \
      1R  3R 5R  7R

红黑树的应用和时间复杂度

主要是 Java 中的 TreeMap 和 TreeSet. jdk1.8 之后, HashMap 的table中的链表长度大于8的时候也是用红黑树.
时间复杂度: 查找, 插入, 删除都可以在 O(log n) 内完成. 且节点数为 n 的数高度最大为 2log(n+1).

红色树的操作

节点的基本定义

    //节点定义
    public class RBTNode<T extends Comparable<T>> {
        public boolean isBlack;
        public T key;
        public RBTNode<T> parent;
        public RBTNode<T> left;
        public RBTNode<T> right;

        public RBTNode(T key, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right, boolean isBlack) {
            this.isBlack = isBlack;
            this.key = key;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }

        public String toString() {
            return "key: " + key + (isBlack ? " B " : " R ") +
                    (parent != null ? (
                            ((parent.left != null && parent.left == this) ?
                                    parent.key + " Left" :
                                    (parent.right != null && parent.right == this) ?
                                    parent.key + " Right" : ""))
                            : "");
        }
    }

旋转 - 左旋转的两种情况

旋转的中心思想是: 从新设置 x 节点, y 节点的左父右节点, 并设置关联变化的节点的父节点.

    px                   px             |                px                    px                     
     \                    \             |               /                     /                  
      x                    y            |              x           ->        y                                 
     / \      ->          / \           |             / \                   / \                       
   lx   y                x  ry          |            lx  y                 x   ry                        
       / \              / \             |               / \               / \                           
     ly  ry            lx  ly           |              ly  ry            lx ly                       

    // 对 x 进行左旋转, 将 x 是 y 的父节点变成, y 是 x 的父节点.
    private void rotateLeft(RBTNode<T> x) {
        RBTNode<T> y = x.right;
        // 1. 设置x 的 左 父 右 节点
        // 1-1 x的左节点无变化
        // 1-2 x的右节点, 设置x右节点的父节点
        x.right = y.left;
        if(y.left != null) y.left.parent = x;
        // 1-3 x的父节点无变化

        //2. 设置y 的 左 父 右 节点
        //2-1: 设置y的父节点
        y.parent = x.parent;

        if (x.parent == null) this.root = y;
        else if (x.parent.left == x) x.parent.left = y;
        else x.parent.right = y;

        //2-2: 设置y 的左节点
        y.left = x;
        x.parent = y;

        //2-3: y节点的右节点无变化
    }

旋转 - 右旋转的两种情况

          py                py         |              py                   py           
         /                 /           |               \                    \         
        y                 x            |                y        ->          x        
       / \        ->     / \           |               / \                  / \       
      x   ry           lx   y          |              x  ry               lx   y      
     / \                   / \         |             / \                      / \     
    lx rx                 rx  ry       |            lx rx                    rx  ry   

    // 对 y 进行右旋转, 将 y 是 x 的父节点 变成 x 是 y 的父节点                                                                                                                  
    private void rotateRight(RBTNode<T> y) {
        RBTNode<T> x = y.left;

        //1: 设置y 的左 父 右 节点
        //1-1: 设置y 的左节点, 并设置其父节点
        y.left = x.right;
        if (x.right != null) x.right.parent = y;

        //2-2: 设置x的父节点
        x.parent = y.parent;
        //1-3: y的右节点无变化

        //2: 设置x 的左 右 父节点

        //2-2: 设置x 的父节点, 及其父节点的子节点
        if (y.parent == null) this.root = x;
        else if (y == y.parent.right) y.parent.right = x;
        else y.parent.left = x;

        //2-1: 设置 x的右节点, 并设置其父节点
        x.right = y;
        //1-2: 设置y 的父节点
        y.parent = x;
        //2-3 x的左节点无变化
    }

插入并修正

若root 是null , 则插入节点就是root 节点.
若root 不是null, 则向下查找node 的父节点, 并根据与父节点的大小关系, 写入待插入节点. 插入的节点都是红色
修正插入的树.
修正过程, 修正的核心思想是: 将红色节点移动到根节点, 将根节点设为黑色.

违背原则4	现象说明	处理策略
情况1	isRed(parent), isRed(uncle)	1. setBlack(parent); 2. setBlack(uncle); 3. setRed(grandParent); 4. current = grandParent; 5. 检测 current 是否违背原则并处理
情况2	isRed(parent), isBlack(uncle), uncle == grandParent.left, current == parent.right	1. setBlack(parent); 2. setRed(grandParent); 3. rotateLeft(grandParent);
情况3	isRed(parent), isBlack(uncle), uncle == grandParent.left, current == parent.left	1. current = parent; 2. rotateRight(current); 3. 检测 current 是否违背原则并处理
情况4	isRed(parent), isBlack(uncle), uncle == grandParent.right, current == parent.right	1. current = parent; 2. rotateLeft(current); 3. 检测 current 是否违背原则并处理
情况5	isRed(parent), isBlack(uncle), uncle == grandParent.right, current == parent.left	1. setBlack(parent); 2. setRed(grandParent); 3. rotateRight(grandParent);


    // 插入修正
    private void insertFix(RBTNode<T> node) {
        RBTNode<T> parent;
        RBTNode<T> grandParent;
        while (isRed(parentOf(node))) {
            parent = parentOf(node);
            grandParent = parentOf(parent);
            RBTNode<T> uncle;
            if (parent == grandParent.left) {
                uncle = grandParent.right;
                if (isRed(uncle)) {  // 情况 1
                    setBlack(parent);
                    setBlack(uncle);
                    setRed(grandParent);
                    node = grandParent;
                    continue;
                }
                if (isBlack(uncle)) {
                    if (parent.right == node) { // 情况 4
                        node = parent;
                        rotateLeft(grandParent);
                    } else { // 情况 5
                        setBlack(parent);
                        setRed(grandParent);
                        rotateRight(grandParent);
                    }
                }
            } else {
                uncle = grandParent.left;
                if (isRed(uncle)) { // 情况 1
                    setBlack(uncle);
                    setBlack(parent);
                    setRed(grandParent);
                    node = grandParent;
                    continue;
                }
                if (isBlack(uncle)) {
                    if (parent.left == node) { // 情况 2
                        node = parent;
                        rotateRight(node);
                    } else { // 情况 3
                        setBlack(parent);
                        setRed(grandParent);
                        rotateLeft(grandParent);
                    }
                }
            }
        } 
    }   

    // 插入
    public void insert(RBTNode<T> node) {
        if (this.root == null) {
            this.root = node;
        } else {
            int compare = 0;
            RBTNode<T> temp = null;
            RBTNode<T> current = this.root;

            //1. 先查找二叉树, 确定node的插入位置
            while (current != null) {
                temp = current;
                compare = node.getKey().compareTo(current.getKey());
                if (compare < 0) current = current.getLeft(); 
                else current = current.getRight(); 
            }

            node.setParent(temp);
            compare = node.getKey().compareTo(temp.getKey());
            if (compare < 0) temp.setLeft(node);
            else temp.setRight(node);
        } 
        insertFix(node);
        setBlack(root);
    }

删除并修正

核心思想: 将被删节点所包含的额外黑色节点(右节点)不断往根节点方向移动并按照情况修正
修正的方法

情况	现象说明	处理策略
情况1	isRed(current)&&isBlack(brother) or isRed(brother)&&isBlack(current)	1. setBlack(current); 2. 执行核心思想移动其子节点
情况2	isBlack(current) isBlack(brother) current==root	执行核心思想移动子节点
情况3	isBlack(current) isBlack(brother) current!=root	执行下面4中情况
情况3-1	isRed(brother)	1. setBlack(brother); 2. setRed(parent); 3. rotateLeft(parent); 4. 重新设置current的brother
情况3-2	isBlack(brother), isBlack(brother.left), isBlack(brother.right)	1. setRed(brother); 2. current = parent
情况3-3	isBlack(brother), isBlack(brother.right), isRed(brother.left)	1. setBlack(brother.left); 2. setRed(brother); 3. rotateRight(brother); 4. 重新设置current的brother
情况3-4	isBlack(brother), isRed(brother.right)	1. brother.color = parent.color; 2. setBlack(parent); 3. setBlack(brother.right); 4. rotateLeft(brother); 5. root = x

完整实现

public class RBTree<T extends Comparable<T>> {

    private RBTNode<T> root;

    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(RBTNode<T> node) {
        if (node != null) {
            System.out.println(node + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(RBTNode<T> node) {
        if (node != null) {
            inOrder(node.left);
            System.out.println(node.toString());
            inOrder(node.right);
        }
    }

    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(RBTNode<T> node) {
        if (node != null) {
            preOrder(node.left);
            preOrder(node.right);
            System.out.println(node + " ");
        }
    }

    public void insert(T key) {
        insert(new RBTNode<T>(key, null, null, null, false));
    }

    private void insert(RBTNode<T> node) { 
    }

    private RBTNode<T> parentOf(RBTNode<T> x) {
        return (x == null ? null : x.parent);
    }

    private boolean isRed(RBTNode<T> x) {
        if (x == null) return false;
        return !x.isBlack;
    }

    private boolean isBlack(RBTNode<T> x) {
        return (x == null || x.isBlack);
    }

    private void setRed(RBTNode<T> x) {
        if (x != null)
            x.isBlack = false;
    }

    private void setBlack(RBTNode<T> x) {
        if (x != null)
            x.isBlack = true;
    }

    private void insertFix(RBTNode<T> node) { 
    }

    private void rotateRight(RBTNode<T> y) {
    }

    private void rotateLeft(RBTNode<T> x) { 
    }

    public void remove(RBTNode<T> node) {
    }
}

//测试代码
public static void main(String[] args) {
        RBTree<Integer> tree = new RBTree<>();
        int[] arr = new int[]{9, 8, 3, 5, 4, 2, 7, 6, 1};
        for (int item : arr)
            tree.insert(9);
        System.out.println("前序");
        tree.preOrder();
        System.out.println("----------------------");
        System.out.println("中序");
        tree.inOrder();
        System.out.println("----------------------");
        System.out.println("后序");
        tree.postOrder();
    }

// 前序
// key: 8 B  
// key: 4 R 8 Left 
// key: 2 B 4 Left 
// key: 1 R 2 Left 
// key: 3 R 2 Right 
// key: 6 B 4 Right 
// key: 5 R 6 Left 
// key: 7 R 6 Right 
// key: 9 B 8 Right 
// ----------------------
// 中序
// key: 1 R 2 Left
// key: 2 B 4 Left
// key: 3 R 2 Right
// key: 4 R 8 Left
// key: 5 R 6 Left
// key: 6 B 4 Right
// key: 7 R 6 Right
// key: 8 B 
// key: 9 B 8 Right
// ----------------------
// 后序
// key: 4 R 8 Left 
// key: 2 B 4 Left 
// key: 1 R 2 Left 
// key: 3 R 2 Right 
// key: 6 B 4 Right 
// key: 5 R 6 Left 
// key: 7 R 6 Right 
// key: 9 B 8 Right 
// key: 8 B

参考文献

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 zhao4xi@126.com