二叉树

树

比如下面这幅图，A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。B、C、D 这三 个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。我们把没有父节点的节点叫 作根节点，也就是图中的节点 E。我们把没有子节点的节点叫作叶子节点或者叶节点，比如 图中的 G、H、I、J、K、L 都是叶子节点。

二叉树

二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右 子节点。

二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左 右两个子节点，这种二叉树就叫作满二叉树。

二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除 了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。

二叉树的遍历

遍历方式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//前序遍历
void preOrder(Node* root) {
if (root == null) return;
print root // 此处为伪代码，表示打印 root 节点
preOrder(root->left);
preOrder(root->right);
}

//中序遍历
void inOrder(Node* root) {
if (root == null) return;
inOrder(root->left);
print root // 此处为伪代码，表示打印 root 节点
inOrder(root->right);
}

//后序遍历
void postOrder(Node* root) {
if (root == null) return;
postOrder(root->left);
postOrder(root->right);
print root // 此处为伪代码，表示打印 root 节点
}

二叉查找树（Binary Search Tree）

二叉查找树要求，在树中的任意一个节点，其左子树 中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

查找操作

首先，我们看如何在二叉查找树中查找一个节点。我们先取根节点，如果它等于我们要查找 的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要 查找的数据比根节点的值大，那就在右子树中递归查找。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public class BinarySearchTree {
    private Node tree;
    
    public Node find(int data) {
        Node p = tree;
        while (p != null) {
            if (data < p.data) p = p.left;
            else if (data > p.data) p = p.right;
            else return p;
        }   
        return null;
    }
    public static class Node {
        private int data;
        private Node left;
        private Node right;
        public Node(int data) {
            this.data = data;
        }
    }
}

插入操作

如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点 的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节 点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再 递归遍历左子树，查找插入位置。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public void insert(int data) {
    if (tree == null) {
        tree = new Node(data);
        return;
    }
    Node p = tree;
    while (p != null) {
        if (data > p.data) {
          if (p.right == null) {
            p.right = new Node(data);
            return;
          }
          p = p.right;
        } else { // data < p.data
            if (p.left == null) {
                p.left = new Node(data);
                 return;
            }
            p = p.left;
        }
    }
}

删除操作

 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

public void delete(int data) {
    Node p = tree; // p 指向要删除的节点，初始化指向根节点
    Node pp = null; // pp 记录的是 p 的父节点
    while (p != null && p.data != data) {
        pp = p;
        if (data > p.data) p = p.right;
        else p = p.left;
    }
    if (p == null) return; // 没有找到
    
    // 要删除的节点有两个子节点
    if (p.left != null && p.right != null) { // 查找右子树中最小节点
        Node minP = p.right;
        Node minPP = p; // minPP 表示 minP 的父节点
        while (minP.left != null) {
        minPP = minP;
        minP = minP.left;
        }
        p.data = minP.data; // 将 minP 的数据替换到 p 中
        p = minP; // 下面就变成了删除 minP 了
        pp = minPP;
    }
    
    // 删除节点是叶子节点或者仅有一个子节点
    Node child; // p 的子节点
    if (p.left != null) child = p.left;
    else if (p.right != null) child = p.right;
    else child = null;
    
    if (pp == null) tree = child; // 删除的是根节点
    else if (pp.left == p) pp.left = child;
    else pp.right = child;
}

其他操作

支持快速地查找最大节点和最小节 点、前驱节点和后继节点。

支持重复数据的二叉查找树

针对的都是不存在键值相同的情况。那如果存储的两个对 象键值相同，这种情况该怎么处理呢？

第一种方法比较容易。二叉查找树中每一个节点不仅会存储一个数据，因此我们通过链表和 支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。

第二种方法比较不好理解，不过更加优雅。

每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插 入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新 插入的数据当作大于这个节点的值来处理。

当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查 找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来

对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方 法，依次删除。

什么是“平衡二叉查找树”？

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。

平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比 较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说 低一些，相应的插入、删除、查找等操作的效率高一些。

如何定义一棵“红黑树”？

红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找 树

一棵红黑 树还需要满足这样几个要求：

• 根节点是黑色的；
• 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
• 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
• 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

为什么说红黑树是“近似平衡”的？

平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会 退化的太严重。

二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉 树（满二叉树或完全二叉树）的高度大约是 log2n，所以如果要证明红黑树是近似平衡的， 我们只需要分析，红黑树的高度是否比较稳定地趋近 log2n 就好了。

首先，我们来看，如果我们将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高 度是多少呢？

红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点 的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。

前面红黑树的定义里有这么一条：从任意节点到可达的叶子节点的每个路径包含相同数目的 黑色节点。我们从四叉树中取出某些节点，放到叶节点位置，四叉树就变成了完全二叉树。 所以，仅包含黑色节点的四叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。

我们现在知道只包含黑色节点的“黑树”的高度，那我们现在把红色节点加回去，高度会变 成多少呢？

在红黑树中，红色节点不能相邻，也就是说，有一个 红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。红黑树中包含最多黑色节点 的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说， 红黑树的高度近似2log2n

实现红黑树的基本思想

插入操作的平衡调整

红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节 点上。所以，关于插入操作的平衡调整，有这样两种特殊情况，但是也都非常好处理。

• 如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。
• 如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了 除此之外，其他情况都会违背红黑树的定义，于是我们就需要进行调整，调整的过程包含两 种基础的操作：左右旋转和改变颜色

CASE 1：如果关注节点是 a，它的叔叔节点 d 是红色

1. 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；
2. 将关注节点 a 的祖父节点 c 的颜色设置成红色；
3. 关注节点变成 a 的祖父节点 c；
4. 跳到 CASE 2 或者 CASE 3。

CASE 2：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点

1. 关注节点变成节点 a 的父节点 b；
2. 围绕新的关注节点b 左旋；
3. 跳到 CASE 3。

CASE 3：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点

1. 围绕关注节点 a 的祖父节点 c 右旋；
2. 将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。
3. 调整结束。

删除操作的平衡调整

1. 针对删除节点初步调整

2. 针对关注节点进行二次调整

递归树与时间复杂度分析

递归的思想就是，将大问题分解为小问题来求解，然后再将小问题分解为小 小问题。这样一层一层地分解，直到问题的数据规模被分解得足够小，不用继续递归分解为 止。

如果我们把这个一层一层的分解过程画成图，它其实就是一棵树。我们给这棵树起一个名 字，叫作递归树。

实战一：分析快速排序的时间复杂度

快速排序的过程中，每次分区都要遍历待分区区间的所有数据，所以，每一层分区操作所遍 历的数据的个数之和就是n。我们现在只要求出递归树的高度 h,这个快排过程遍历的数据个数 就是 h * n，也就是说，时间复杂度就是 O(h * n)

我们知道，快速排序结束的条件就是待排序的小区间，大小为1,也就是说叶子节点里的数据规模是 1。 从根节点n到叶子节点 1，递归树中最短的一个路径每次都乘以1/10，最长的一个路径每次都乘以9/10. 通过计算，我们可以得到，从根节点到叶子节点的最短路径是 log10n,最长的路径是 log10/9 n

当分区比例是1 : 9时， 快速排序的时间复杂度仍然是 O(n log n)

实战二：分析斐波那契的时间复杂度

f(n)分解为 f(n-1)和f(n-2)，每次数据规模都是 -1 或者-2.叶子节点的数据规模是 1 或者 2， 所以，从跟节点到叶子节点，每条的路径都是长短不一的

每次分解之后的合并操作只需要一次加法计算，我们把这次加法运算的时间消耗记作 1，从上往下，第一层的总时间消耗为 1， 第二层的总时间消耗为 2，第三层的总时间消耗就是 依次类推，第 k层的时间消耗就是 2^k-1,那整个算法的总的时间就是每层时间消耗之和

所以，该算法的时间复杂度就介于O(2^n)和O(2^(n/2))之间