乐趣区

关于java:每次面试都被问什么是红黑树

jiezi

前言

了解红黑树须要把握上面常识

  • 二分查找算法
  • 二叉查找树
  • 自均衡树（AVL 树和红黑树）

基于二分算法设计出了二叉查找树，为了补救二叉查找树歪斜毛病，又呈现了一些自均衡树，比方 AVL 树，红黑树等。

二分查找算法

在 40 亿数据中查找一个指定数据最多只须要 32 次，这就是二分查找算法的魅力。

二分查找算法 （又叫 折半查找算法 ）是一种在 有序数组 中查找某一特定元素的 搜索算法 。留神 有序数组 的前提。

下图中查找 4，查找从两头元素开始 4 < 7，从右边查找 4 > 3，从左边查找 4 < 6，而后找到元素。

二分查找算法工夫和空间复杂度，\({n} \) 是数组长度。

均匀工夫复杂度 \({O(\log n)} \)

最坏工夫复杂度 \({O(\log n)} \)

最优工夫复杂度 \({O(1)} \)

循环空间复杂度 \({O(1)} \)

递归空间复杂度 \({O(\log n)} \)

Java 递归实现二分查找。

    public static int binarySearch(int[] arr, int start, int end, int hkey) {if (start > end) {return -1;}
        int mid = start + (end - start) / 2;    // 避免溢位
        if (arr[mid] > hkey) {return binarySearch(arr, start, mid - 1, hkey);
        }
        if (arr[mid] < hkey) {return binarySearch(arr, mid + 1, end, hkey);
        }
        return mid;
    }

Java 循环实现二分查找。

    public static int binarySearch(int[] arr, int start, int end, int hkey) {
        int result = -1;
        while (start <= end) {int mid = start + (end - start) / 2;    // 避免溢位
            if (arr[mid] > hkey) {end = mid - 1;} else if (arr[mid] < hkey) {start = mid + 1;} else {
                result = mid;
                break;
            }
        }
        return result;
    }

二叉查找树

二叉查找树（Binary Search Tree，简称 BST）是一棵二叉树，它具备以下性质：

  1. 若任意节点的左子树不空，则左子树上所有节点的值都小于它的根节点的值；
  2. 若任意节点的右子树不空，则右子树上所有节点的值都大于它的根节点的值；
  3. 任意节点的左、右子树也别离为二叉查找树。

二叉树：每个节点最多只有两个分支，别离称为“左子树”或“右子树”。

二叉查找树操作（搜寻，插入，删除）效率依赖树高度。

最坏状况，树向一边歪斜，树高度 $n$（节点数量），此时操作工夫复杂度为 $O(n)$

现实状况，树高度 $log(n)$，操作工夫复杂度 $O(log(n))$，此时它是一棵 均衡 的二叉查找树。

算法 均匀 最差
空间 O(n) O(n)
搜寻 O(log n) O(n)
插入 O(log n) O(n)
删除 O(log n) O(n)

为了让二叉查找树尽可能达到现实状况，呈现了一些自均衡二叉查找树，如 AVL 树 和红黑树。

AVL 树

AVL 树中的每个节点都有一个 均衡因子 属性（左子树高度减去右子树高度）。每次元素插入删除操作后，会从新进行均衡计算，如果节点均衡因子不为 [1,0,-1] 时，须要通过 旋转 使树达到均衡。AVL 树中有 4 种旋转操作。

  1. 左旋（Left Rotation）
  2. 右旋（RightRotation）
  3. 左右旋转（Left-Right Rotation）
  4. 左右旋转（Right-Left Rotation）

上面是 Java AVL 树的例子

    private Node insert(Node node, int key) {
          .....
        return rebalance(node); // 从新均衡计算
    }

    private Node delete(Node node, int key) {
          .....
        node = rebalance(node); // 从新均衡计算
        return node;
    }

        private Node rebalance(Node z) {updateHeight(z);
        int balance = getBalance(z);
        if (balance > 1) {if (height(z.right.right) > height(z.right.left)) {z = rotateLeft(z);
            } else {z.right = rotateRight(z.right);
                z = rotateLeft(z);
            }
        } else if (balance < -1) {if (height(z.left.left) > height(z.left.right)) {z = rotateRight(z);
            } else {z.left = rotateLeft(z.left);
                z = rotateRight(z);
            }
        }
        return z;
    }

https://github.com/eugenp/tut…

红黑树

性质

红黑树中的每个节点都有一个 色彩 属性。每次元素插入删除操作后，会进行从新 着色 和旋转 达到均衡。

红黑树属于二叉查找树，它蕴含二叉查找树性质，同时还蕴含以下性质：

  1. 每个节点要么是彩色，要么是红色。
  2. 所有的叶子节点（NIL）被认为是彩色的。
  3. 每个红色节点的两个子节点肯定都是彩色（不会呈现两个间断红色节点）。
  4. 从根到叶子节点（NIL）的每条门路都蕴含雷同数量的彩色节点。

查找

查找不会毁坏树的均衡，逻辑也比较简单，通常有以下几个步骤。

  1. 从根节点开始查找，把根节点设置为以后节点；
  2. 以后节点为空，返回 null；
  3. 以后节点不为空，查找 key 小于以后节点 key，左子节点设为以后节点。
  4. 以后节点不为空，查找 key 大于以后节点 key，右子节点设为以后节点。
  5. 以后节点不为空，查找 key 等于以后节点 key，返回以后节点。

代码实现能够参考 Java 外面的 TreeMap。

    Entry<K,V> p = root;
    while (p != null) {int cmp = k.compareTo(p.key);
        if (cmp < 0){p = p.left;}else if (cmp > 0){p = p.right;}else{return p;}
  }
    return null;

插入

插入操作分两大块：一查找插入地位；二插入后自均衡。

  1. 将根节点赋给 以后节点，循环查找插入地位的节点；
  2. 当查找 key 等于 以后节点key，更新节点存储的值，返回；
  3. 当查找 key 小于 以后节点key，把以后节点的左子节点设置为以后节点；
  4. 当查找 key 大于 以后节点key，把以后节点的右子节点设置为以后节点；
  5. 循环完结后，结构新节点作为 以后节点 左(右)子节点；
  6. 通过旋转变色进行自均衡。

代码实现能够参考 Java 外面的 TreeMap。

    Entry<K,V> t = root;
  Entry<K,V> parent;
    int cmp;
    do {
        parent = t;
        cmp = k.compareTo(t.key);
    if (cmp < 0){t = t.left;}else if (cmp > 0){t = t.right;}else {return t.setValue(value);   // 更新节点的值，返回
    }
  } while (t != null);

    Entry<K,V> e = new Entry<>(key, value, parent);
        if (cmp < 0){parent.left = e;}else {parent.right = e;}
  fixAfterInsertion(e); // 通过旋转变色自均衡

插入场景剖析

  1. 根节点为空，将插入节点设置为根节点并设置为彩色；
  2. 插入节点的 key 已存在，只须要更新插入值，无需再自均衡；
  3. 插入节点的父节点为彩色，直接插入，无需自均衡；
  4. 插入节点的父节点为红色。

场景 4 插入节点后呈现 两个间断的红色节点 ，所以须要 从新着色 和旋转。这外面又有很多种状况，具体看上面。

先申明下节点关系，祖节点（10），叔节点（20），父节点（9），插入节点（8）。

个别通过判断插入节点的叔节点来确定适合的均衡操作。

叔叔节点存在且为红色。

  1. 先查找地位将 节点 8 插入；
  2. 将 父节点 9 和 叔节点 20 变为彩色，祖节点 10 变为红色；
  3. 祖节点 10 是根节点，所以又变为彩色。

叔叔节点不存在或为彩色，父节点是祖节点的左节点，插入节点是父节点的左子节点。

  1. 先查找地位将 节点 7 插入；
  2. 将 祖节点 9 进行右旋转；
  3. 将 父节点 8 变为彩色，祖节点 9 变为红色；

叔叔节点不存在或为彩色，父节点是祖节点的左节点，插入节点是父节点的右子节点。

  1. 先查找地位将 节点 8 插入；
  2. 将 父节点 7 进行左旋转；
  3. 将 祖节点 9 进行右旋转；
  4. 将插入 节点 8 变为彩色，祖节点 9 变为红色；

叔叔节点不存在或为彩色，父节点是祖节点的右节点，插入节点是父节点的右子节点。

  1. 先查找地位将 节点 9 插入；
  2. 将 祖节点 8 进行左旋转；
  3. 将 父节点 9 变为彩色，祖节点 8 变为红色；

叔叔节点不存在或为彩色，父节点是祖节点的右节点，插入节点是父节点的左子节点。

  1. 先查找地位将 节点 9 插入；
  2. 将 父节点 10 进行右旋转；
  3. 将 祖节点 8 进行左旋转；
  4. 将插入 节点 9 变为彩色，祖节点 8 变为红色；

删除

删除操作分两大块：一查找节点删除；二删除后自均衡。删除节点后须要找节点来代替删除的地位。

依据二叉查找树性质，删除节点之后，能够用 左子树中的最大值 或右子树中的最小值 来替换删除节点。如果删除的节点无子节点，能够间接删除，无需替换；如果只有一个子节点，就用这个子节点替换。

思考一些删除场景，应用上面可视化工具模仿场景。

https://www.cs.csubak.edu/~ms…

替换节点和删除节点其中一个红色

  1. 查找到 删除节点 3 ，将它删除；
  2. 节点 2 替换删除地位，并变为 删除节点 3 的彩色。

替换节点和删除节点都是彩色，它兄弟节点是彩色，兄弟节点的子节点至多有一个红色。

替换节点和删除节点都是彩色，它兄弟节点是彩色，兄弟节点的子节点至多有一个红色。

替换节点和删除节点都是彩色，它兄弟节点是彩色，兄弟节点的两个子节点都是彩色。

替换节点和删除节点都是彩色，它兄弟节点是红色。

AVL 树和红黑树比照

上面是 [1-10] 别离存储在 AVL 树 和红黑树 的图片。能够看出：

  • AVL 树 更严格均衡，带来查问速度快。为了保护严格的均衡，须要付出频繁旋转的性能代价。
  • 红黑树 相较于要求严格的 AVL 树来说，它的旋转次数少。

退出移动版