浅谈红黑树

1.写在前面

今天我们来简单的了解一下一种比较难的数据结构，红黑树，因为最近在看1.8的hashmap的树化的操作，这儿的树就是红黑树，所以我们这儿先看看对应红黑树的前置的知识，让我们在看hashmap的源码的时候没有那么的吃力，好了，废话不多说，直接上干货。

2.什么是红黑树

红黑树是平衡二叉查找树的一种。为了深入理解红黑树，我们需要从二叉查找树开始讲起。

3.BST

二叉查找树（Binary Search Tree，简称BST）是一棵二叉树，它的左子节点的值比父节点的值要小，右节点的值要比父节点的值大。它的高度决定了它的查找效率。可以理解为有序的二叉树，相对来说查找的效率比较高

在理想的情况下，二叉查找树增删查改的时间复杂度为O(logN)（其中N为节点数），最坏的情况下为O(N)。

平衡二叉树

特殊的BST：倾斜的BST

3.BST的Java代码

public class BstTest {

    static class Node {
      // 节点的内容
      public String content;
      // 父亲节点
      public Node parent;
      // 左节点
      public Node left;
      // 右节点
      public Node right;
      
      public Node(String content) {
        this.content = content;
      }
    }

    public Node root;

    // BST的查找操作
    public Node search (String content) {
      // 从根节点开始搜素
      Node r = root;
     // 根节点不为空的时候循环查询
      while (r != null) {
        // 如果当前的节点等于要查找的内容
        if (r.content.equals(content)) {
          return r;
        } else if (content.compareTo(r.content) > 1) { // 比当前的大，查右边的
          r = r.right;
        } else if (content.compareTo(r.content) <= 1) { // 比当前的小，查左边的
          r = r.left;
        }
      }
      
      return null;
    }

    // BST的插入操作
    public void insert (String content) {
      // 创建新的节点
      Node newNode = new Node(content);
      // 赋值新的根的节点
      Node r = root;
      // 父级节点
      Node parent = null;
      
      // 如果根的节点为空的时候，就是第一次插入的根节点
      if (r == null) {
        root = newNode;
        return;
      }

      // 如果根的节点不为空
      while (r != null) {
        // 父的节点先从根节点开始
        parent = r;
        if (newNode.content.compareTo(r.content) > 1) { // 比当前的大，查右边
          r = r.right;
        } else if (newNode.content.compareTo(r.content) < 1){ // 比当前的小，查左边
          r = r.left;
        } else { // 等于当前的，也是查左边
          r = r.left;
        }
      }

      // 遍历完了直接最下面的节点了，然后准备挂上节点
      if (parent.content.compareTo(newNode.content) > 1) {
        parent.left = newNode;
        newNode.parent = parent;、
      } else {
        parent.right = newNode;
        newNode.parent = parent;
      }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

4.红黑树-RBTree

基于BST存在的问题，一种新的树——平衡二叉查找树(Balanced BST)产生了。平衡树在插入和删除的时候，会通过旋转操作将高度保持在logN。其中两款具有代表性的平衡树分别为AVL树和红黑树。AVL树由于实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树。

红黑树（Red-Black Tree，以下简称RBTree）的实际应用非常广泛，比如Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等，各种语言的函数库如Java的TreeMap和TreeSet，C++ STL的map、multimap、multiset等。

RBTree也是函数式语言中最常用的持久数据结构之一，在计算几何中也有重要作用。值得一提的是，Java 8中HashMap的实现也因为用RBTree取代链表，性能有所提升。

5.红黑树定义

算法导论》中对于红黑树的定义如下：

1. 每个结点或是红的，或是黑的
2. 根节点是黑的
3. 每个叶结点是黑的
4. 如果一个结点是红的，则它的两个儿子都是黑的
5. 对每个结点，从该结点到其子孙节点的所有路径上包含相同数目的黑结点

对与第4点，网上有些定义是：父子节点之间不能出现两个连续的红节点，这种定义和《算法导论》中定义的效果是一样的

RBTree在理论上还是一棵BST树，但是它在对BST的插入和删除操作时会维持树的平衡，即保证树的高度在[logN,logN+1]（理论上，极端的情况下可以出现RBTree的高度达到2*logN，但实际上很难遇到）。这样RBTree的查找时间复杂度始终保持在O(logN)从而接近于理想的BST。RBTree的删除和插入操作的时间复杂度也是O(logN)。RBTree的查找操作就是BST的查找操作。

6.插入数据

向红黑树中插入新的结点。具体做法是，将新结点的 color 赋为红色，然后以BST的插入方法插入到红黑树中去。之所以将新插入的结点的颜色赋为红色，是因为：**如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑结点，这个是很难调整的。**但是设为红色结点后，可能会导致出现两个连续红色结点的冲突，那么可以通过颜色调换和树旋转来调整，这样简单多了。

接下来，讨论一下插入以后，红黑树的情况。**设要插入的结点为N，其父结点为P，其祖父结点为G，其父亲的兄弟结点为U（即P和U 是同一个结点的两个子结点）。**如果P是黑色的，则整棵树不必调整就已经满足了红黑树的所有性质。如果P是红色的（可知，其父结点G一定是黑色的），则插入N后，违背了红色结点只能有黑色孩子的性质，需要进行调整。

7.怎么调整

调整时分以下三种情况：

新结点N的叔叔结点U是红色的

处理方式是：将P和U修改为黑色，G修改为红色。

现在新结点N有了一个黑色的父结点P，因为通过父结点P或叔父结点U的任何路径都必定通过祖父结点G，在这些路径上的黑结点数目没有改变。

但是，红色的祖父结点G的父结点也有可能是红色的，这就违反了性质3。为了解决这个问题，我们从祖父结点G开始递归向上调整颜色。

新结点N的叔叔结点U是黑色的，且N是左孩子。

处理方式：对祖父结点G进行一次右旋转

在旋转后产生的树中，以前的父结点P现在是新结点N和以前的祖父节点G的父结点，然后交换以前的父结点P和祖父结点G的颜色，结果仍满足红黑树性质。如图 2.15。在(b)中，虚线代表原来的指针，实线代表旋转过后的指针。所谓旋转就是改变图中所示的两个指针的值即可。当然，在实际应用中，还有父指针p也需要修改，这里为了图示的简洁而省略掉了。

新结点N的叔叔结点U是黑色的，且N是右孩子。

处理方式：**对P进行一次左旋转，就把问题转化成了第二种情况。**如图 2.16所示。

红黑树插入数据的代码与二叉查找树是相同的，只是在插入以后，会对不满足红黑树性质的结点进行调整。

8.写在最后

本篇博客主要介绍了红黑树一些常用的特性，以及插入的几种情况，以及如何处理的。