数据机构基础之红黑树实现

介绍

二叉搜索树

二叉树:树的每个节点最多只能有两个子节点

二叉搜索树:

  • 左子树不为空,左子树上所有节点的值均小于它的根节点的值
  • 右子树不为空,右子树上所有节点的值均大于它的根节点的值

参考图片

查找:搜索值小于当前节点搜左子树,大于当前节点搜右子树,等于表示搜到
插入:类似查找,直到左子树或右子树为空时认为找到了插入位置

遍历:

  • 中序遍历:左-根-右(使用较多)
  • 前序遍历:根-左-右
  • 后序遍历:左-右-根

参考图片

最值:

  • 最小值:最左边的节点
  • 最大值:最右边的节点

删除:

  • 叶节点:直接删(父节点指向空)
  • 有一个子节点:由于二叉搜索树的特性,可以直接子承父位
  • 有两个子节点:找到后继节点替换(大于该节点的最小节点)

二分查找

二分查找:数组有序情况下,对半查,参考下图

缺点:必须是有序的,而且是数组,不可以是链表

可以看出,二叉搜索树和二分查找有一定的相似度

AVL树

二叉搜索树存在一种极端情况,这种情况下会退化为一个有序链表

由于退化成链表后搜索效率过低,需要设计一种树,在插入元素的时候自动调整两边平衡,保持高查询性能。这里暂不分析AVL树,本节重点是红黑树

AVL树特点:

  1. 具有二叉树全部特性
  2. 左子树和右子树高度差最多是1
  3. 插入或删除时,会涉及到左旋和右旋操作

虽然AVL树解决了二叉搜索树的极端情况,但是由于高度差限制过于严格,导致效率过低

于是引出了红黑树的概念

基础

性质

红黑树具有以下的性质,如果满足那么这棵树就是趋于平衡状态的:

  • 每个节点是黑色或红色
  • 根节点是黑色
  • 叶节点是黑色
  • 每个红色节点的两个子节点是黑色,红色节点不能相连
  • 任意节点到每个叶节点的路径都包含相同的黑节点,又称黑高
  • 如果一个节点存在黑子节点,那么该节点一定有两个子节点

自平衡

  1. 变色:节点颜色红黑变化
  2. 左旋:某节点右子节点变成父节点,右子节点的左节点变为它的右节点,左子节点保持不变
  3. 右旋:某节点左子节点变成父节点,左子节点的右节点变为它的左节点,右子节点保持不变

实现

红黑树的插入等操作会涉及到多种情况,暂不分析,直接上代码,在代码中分析

树节点

// 树节点
static class RBNode<K extends Comparable<K>, V> {
    private RBNode parent;
    private RBNode left;
    private RBNode right;
    private boolean color;

    private K key;
    private V value;

    // 构造 get set
    // ......
}

左旋实现

/**
* 左旋
*      p              p
*      |              |
*      x              y
*     / \   --->     / \
*    lx  y          x   ry
*   / \            / \
*  ly ry          lx ly
*
* (1) x.right=y.left
* (2) y.left.parent=x
* (3) y.parent=x.parent
* (4) x.parent=y
*
* @param x 左旋节点
*/
private void leftRotate(RBNode x) {
    RBNode y = x.right;
    // (1)
    x.right = y.left;
    // (2)
    if (y.left != null) {
        y.left.parent = x;
    }
    // (3)
    if (x.parent != null) {
        y.parent = x.parent;
        if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
    } else {
        // root
        this.root = y;
    }
    // (4)
    x.parent = y;
    y.left = x;
}

右旋实现

/**
* 右旋
*      p              p
*      |              |
*      y              x
*     / \   --->     / \
*    x  ry          lx  y
*   / \                / \
*  lx ly              ly ry
*
* (1) y.left=x.right
* (2) x.right.parent=y
* (3) x.parent=y.parent
* (4) y.parent=x
*
* @param y 右旋节点
*/
private void rightRotate(RBNode y) {
    RBNode x = y.left;
    // (1)
    y.left = x.right;
    // (2)
    if (x.right != null) {
        x.right.parent = y;
    }
    // (3)
    if (y.parent != null) {
        x.parent = y.parent;
        if (y == y.parent.left) {
            y.parent.left = x;
        } else {
            y.parent.right = x;
        }
    } else {
        // root
        this.root = x;
        this.root.parent = null;
    }
    // (4)
    y.parent = x;
    x.right = y;
}

插入

/**
* 对外的插入
* @param key key
* @param value value
*/
public void insert(K key, V value) {
    RBNode node = new RBNode();
    node.setKey(key);
    node.setValue(value);
    // 新节点一定是红色
    node.setColor(RED);
    insert(node);
}

/**
* 插入实现
* @param node 插入节点
*/
private void insert(RBNode node) {
    RBNode parent = null;
    RBNode x = this.root;

    while (x != null) {
        parent = x;
        // cmp>0:node.key>x.key->遍历右子树
        // cmp=0:node.key=x.key->replace
        // cmp<0:node.key<x.key->遍历左子树
        int cmp = node.key.compareTo(x.key);
        if (cmp > 0) {
            x = x.right;
        } else if (cmp == 0) {
            x.setValue(node.getValue());
            return;
        } else {
            x = x.left;
        }
    }
    node.parent = parent;
    if (parent != null) {
        // cmp>0:node.key>parent.key->node在parent右子节点
        // cmp<0:node.key<parent.key->node在parent左子节点
        int cmp = node.key.compareTo(parent.key);
        if (cmp > 0) {
            parent.right = node;
        } else {
            parent.left = node;
        }
    } else {
        this.root = node;
    }

    // 恢复平衡
    insertFixup(node);
}

恢复平衡

private void insertFixup(RBNode node) {
    this.root.setColor(BLACK);
    // 父节点
    RBNode parent = parentOf(node);
    // 父节点的父节点
    RBNode gparent = parentOf(parent);
    // 父节点为黑色直接平衡
    // 父节点为红色应分多种情况
    if (parent != null && isRed(parent)) {
        // 父节点的父节点的另一个子节点(叔叔)
        RBNode uncle = null;
        // 父节点是爷节点左节点
        if (parent == gparent.left) {
            uncle = gparent.right;
            /**
            *         |                      |
            *      gp(B)                   gp(R)
            *      /   \      --->         /   \
            *    p(R)  u(R)              p(B)  u(B)
            *    /                       /
            *  n(R)                    n(R)
            */
            if (uncle != null && isRed(uncle)) {
                // 重新染色后下一轮处理
                setBlack(parent);
                setBlack(uncle);
                setRed(gparent);
                insertFixup(gparent);
                return;
            }
            if (uncle == null || isBlack(uncle)) {
                /**
                *         |                      |
                *      gp(B)                    p(B)
                *      /   \      --->         /   \
                *    p(R)  u(B)              n(R)  gp(R)
                *    /                               \
                *  n(R)                              u(B)
                */
                if (node == parent.left) {
                    setBlack(parent);
                    setRed(gparent);
                    // 右旋
                    rightRotate(gparent);
                    return;
                }
                /**
                *         |                      |
                *      gp(B)                    gp(B)
                *      /   \      --->         /   \       ---> 上一步
                *    p(R)  u(B)              n(R)  u(B)
                *       \                    /
                *       n(R)               p(R)
                */
                if (node == parent.right) {
                    leftRotate(parent);
                    insertFixup(parent);
                    // 右旋
                    return;
                }
            }
        } else {
            // 父节点是右节点
            uncle = gparent.left;
            /**
            *         |                      |
            *      gp(B)                   gp(R)
            *      /   \      --->         /   \
            *    u(R)  p(R)              u(B)  p(B)
            *    /                       /
            *  n(R)                    n(R)
            */
            if (uncle != null && isRed(uncle)) {
                // 重新染色后下一轮处理
                setBlack(parent);
                setBlack(uncle);
                setRed(gparent);
                insertFixup(gparent);
                return;
            }
            // 不存在叔节点
            if (uncle == null || isBlack(uncle)) {
                /**
                *         |                      |
                *      gp(B)                    p(B)
                *      /   \      --->         /   \
                *    u(B)  p(R)              gp(R) n(R)
                *            \               /
                *            n(R)          u(R)
                */
                if (node == parent.right) {
                    setBlack(parent);
                    setRed(gparent);
                    leftRotate(gparent);
                    return;
                }
                /**
                *         |                      |
                *      gp(B)                    gp(B)
                *      /   \      --->         /   \     ---> 上一步
                *    u(B)  p(R)              u(B)  n(R)
                *          /                         \
                *        n(R)                        p(R)
                */
                if (node == parent.left) {
                    rightRotate(parent);
                    insertFixup(parent);
                    return;
                }
            }
        }
    }
}

代码

最终代码参考链接:https://github.com/EmYiQing/RBTree