二叉树

定义

  • 二叉树由节点的有限集合构成
  • 这个有限集合或者为空集
  • 或者为由一个根节点(root)及两棵互不相交、分别称为这个根的左子树和右子树的二叉树组成的集合

在 java 中用代码定义为：

1
2
3
4
5
6
7
8
class TreeNode {
    Object val;
    TreeNode leftNode;
    TreeNode rightNode;
    
    ...
        
}

性质

  1. 在二叉树中，第 i 层上最多有2^i^ 个节点(i>=0)
  2. 深度为 k 的二叉树至多有2^k+1^-1个节点(k>=0)
  3. 有 n 个节点的完全二叉树的高度为 log2(n+1)

它主要有五种基本形态：

二叉树的五种基本形态

满二叉树

定义：除最后一层无任何子节点外，每一层上的所有节点都有两个子节点的二叉树。

大体的意思就是：一颗二叉树的节点要么是叶子节点（也就是最后一层），要么它就要有两个子节点。如果这个二叉树的层数为 k，且节点总数是(2^k^-1)，则它就是满二叉树。

满二叉树

完全二叉树

定义：设二叉树的深度为 k，除第 k 层外，其他各层(1~(k-1)层)的节点都都达到最大值，其第 k 层所有的节点都连续集中在最左边，这样的树就是完全二叉树

完全二叉树

这些是二叉树的一些基本定义以及变形，它对于数据的存储并没有要求，只是要求了结构。所以对于实际应用中还存在很多的不足，比如对于一个 n 个节点的树，判断一个节点是不是在树里面，它的复杂度还是 o(n)。所以我们下面介绍几种对于存储有要求的树。

二叉树的遍历

树的几种遍历方式

我们以这样的一个二叉树为例，来进行不同形式的遍历

中序

我们以一个节点为例，它分别有该节点本身，左节点，右节点。

中序遍历的顺序为：

  1. 访问左节点（如果左节点为树，则继续递归访问）
  2. 访问自身节点
  3. 访问右节点（如果右节点为树，则继续递归访问）

拿我们上面的例子来说：首先拿到 A 节点。根据上面的规则，先访问左节点 B，左节点 B 为树，那么继续访问 B 的左节点 C，最终我们可以访问到 E。E 没有左子树了，那么将 E 放到结果集中。

然后访问自身节点，这时的自身节点是 D，将 D 放到结果集中，然后访问右节点 F。

一步一步的返回到 A，这时结果集里的顺序是(E,D,F,C,B,G,I,H,A)。

然后访问右节点J，这时 J 是一个树，然后访问 J 的左节点 K，将它放到结果集中，然后访问自身，最后访问右节点 L。

那么最终得到的结果集是：(E,D,F,C,B,G,I,H,A,K,J,L)

前序

中序遍历的顺序为：

  1. 访问自身节点
  2. 访问左节点（如果左节点为树，则继续递归访问）
  3. 访问右节点（如果右节点为树，则继续递归访问）

继续拿上面的例子：首先拿到 A 节点，然后将它放到结果集中。然后访问左节点 B，将 B 放到结果集中。然后访问做节点 C，将 C 放到结果集中，然后访问 D，然后 E。这时 E 没有子节点，向上返回到 D。继续访问右节点 F，F 也没有子节点，向上返回到 B，访问 B 的右节点 G。

最后返回到 A，这时结果集里的顺序为(A,B,C,D,E,F,G,H,I)

然后访问右节点 J，将 J 放到结果集中，继续访问左节点 K，k 没有子节点，向上返回然后访问右节点 L。最后完成遍历

最终得到的结果为:(A,B,C,D,E,F,G,H,I,J,K,L)

后序

后序遍历的顺序为：

  1. 访问左节点（如果左节点为树，则继续递归访问）
  2. 访问右节点（如果右节点为树，则继续递归访问）
  3. 访问自身节点

继续拿上面的例子：首先拿到根节点 A。然后访问左节点B，B 还有左节点，所以继续向下访问，一直到 E，将 E 放到结果集中。然后向上返回到 D，接下来访问 D 的右节点F，将 F 放到结果集中。然后访问自身节点 D，将值放到结果集中，然后返回 C，由于 C 没有右节点，所以将 C 放到结果集中，一直返回。

返回到 A 的时候，结果集里面的值为：(E,F,D,C,I,H,G,B)

然后需要访问 A 的右节点 J，J 还有子节点，所以再进行递归。访问 J 的左节点 K，访问右节点 L，访问自身节点。完成 J 的访问后再回到 A，将 A 添加到结果集中

最终得到的结果是：(E,F,D,C,I,H,G,B,K,L,K,A)

所以这里的前中后，对于的就是根节点对于左右节点的顺序。如果根节点在左右节点之间则为中序、如果根节点在左右节点之前则为前序、在左右节点后面就是后序

其他遍历方式

还是一些其他的遍历方式，比如深度优先、广度优先等。

二叉搜索树（BST）

为了解决二叉树在搜索上的效率问题，我们定义了二叉搜索树。

二叉搜索树

定义：

  • 可以是一颗空树
  • 或者是具有下列性质的二叉树
    • 对于任何一个节点，设其值为 k
    • 则该节点的左子树(若不为空)的任意一个节点的值都小于 k
    • 该节点的右子树(若不为空)的任意一个节点的值都大于 k
    • 而且它的左右子树也分别为二叉搜索树

性质

  • 中序遍历是正序的(由小到大的排列)

  • 搜索的时候使用二分搜索法

  • 插入也是一遍检索的过程

  • 删除时，可以使用左子树的最大或者右子树的最小值作为被删除值的替换，然后将左子树最大或者右子树最小进行删除（比如删除 35，我们可以用右子树最小 51 来替换 35 的值，然后将 51 节点删除）

  • 最优的情况下，我们搜索的时间复杂度是 o(log2N)，最坏的情况下是 o(N)

平衡二叉树（AVL）

当我们给定一个正序的数组[1,2,3,4,5,6,7]然后将他们顺序插入到二叉搜索树中。它就变成了如下的结构：

它从我们的树退化成了链表，我们对于这样的数据结构访问的时间复杂度也变成了 o(n)。但我们希望它能变成这样的数据结构，那么我们就可以使用 o(log2N)的复杂度去访问了。

平衡二叉树

这就是我们引入平衡二叉树的意义。

定义

  1. 一颗平衡二叉树或者是空树，或者是具有以下性质的二叉排序树
    • 左子树与右子树的高度之差的绝对值小于等于 1
    • 左子树与右子树也是平衡二叉树

所以平衡的关键点就是在二叉搜索树的基础上，实现左右子树的高度差不超过 1

实现

为了方便起见，给每个节点附加一个数字，给出该节点左子树与右子树的高度差。这个数组称为节点的平衡因子(BF)

平衡因子 = 节点左子树的高度-节点右子树的高度

根据平衡二叉树的定义，平衡二叉树上所有节点的平衡因子只能是 -1,0,1;

如果在一颗 AVL 树中插入一个新节点后造成失衡，则必须重新调整树的结构，使之恢复平衡。平衡调整分为以下四种类型：

平衡调整的四种类型

当出现失衡时就需要进行调整，而调整的原则就是：

  • 降低高度
  • 保持二叉排序树的性质

所以可以将上面四种情况分别调整为：

上面的调整都是在简单的情况或者理想情况下的图，当我们实际操作起来 A,B 节点还可能有其他的子节点。这时又该如何调整呢？我们继续来看：

例子

我们以一个例子来看一下平衡二叉树的构造过程。

我们用一个数组：[16,3,7,11,9,26,18,14,15]顺序插入到二叉平衡树中。

2-3 树

学习 2-3 树是为了下面红黑树的学习。2-3 树在完美平衡的情况下所有空链接到根节点的距离都是相同的。我们接下来描述的也都是完美平衡的 2-3 树。

定义

首先我们知道二叉树的节点是有一个值，有两个子节点。我们在 2-3 树中将这样的节点称为 2-节点(因为有两个子节点)，然后我们再引入一个定义 3-节点（这个节点里面有两个值，有三个子节点，左节点小于两个值，右节点大于两个值，中节点介于两个值之间）

2-3树

所以它也是一颗二叉搜索树，它的查找和二叉搜索树的查找基本上没区别

插入过程

  1. 向一颗空树插入

    当向空树插入时，新建一个 2-节点即可。

  2. 向 2-节点插入

    把这个 2-节点替换为一个 3-节点即可。

  3. 向 3-节点插入

    先将这个 3-节点临时变为 4-节点(节点里面有 3 个值，两个旧值，一个新值)。然后将三个值的中间值作为父节点，父节点的左节点为这三个值中的最小值，父节点的右节点为这三个值中的最大值。这时树的高度增加了 1。

  4. 向一个父节点为 2-节点的 3-节点插入

    首先我们看第三步，我们向一个 3-节点插入，会将其分解为 3 个 2-节点，然后树高加 1。但是我们这次有一个父节点，并且它是一个 2-节点。那我们是不是可以把它看做，向一个 2-节点插入一个新键(这个新键是从子节点分解上来的中间值)。那么这样就可以按照第二步，将这个 2-节点替换为 3-节点。这时父节点变成了 3-节点。

  5. 向一个父节点为 3-节点的 3-节点插入

    首先它是向一个 3-节点插入，我们再按照第三步操作，得到了一个中间值向上传递。这时父节点又是一个 3-节点。我们继续按照第三步来操作。一直向上传递，直到遇到一个父节点为 2-节点，或者到达根节点。

    当我们到达根节点后，如果根节点也是 3-节点，就需要分解根节点，变成 3个 2-节点。此时树的高度加 1。

只看这个步骤可能有些晦涩，我们就直接上例子(1,3,5,7,9,2,4,6,8)的插入过程。

2-3树的插入过程

我们只要记住，首先按照二叉搜索树的性质来进行插入。小就往左子树，大就向右子树，中间就想中间的树。然后遇到 2-节点就变 3-节点。遇到 3-节点就分解向上传递，然后就又变成了向 2-或 3-节点插入的问题。

红黑树

性质

  1. 节点是红色或黑色
  2. 根节点是黑色
  3. 所有叶子节点都是黑色
  4. 每个红色节点必须有两个黑色的子节点（从每个叶子到根的所有路径上不能有两个连续的红色节点）
  5. 从任意节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点

我们为什么在上面要学习一下 2-3 树呢，因为在《算法》第四版中，它将红黑树看成 2-3 树的变形。我们知道 2-3 树中有一个 3-节点。它在一个节点中有两个值，这两个值肯定是一个大，一个小。我们如果把这个小的值分离出来，并且将它的颜色设置成红色，因为它小，所以它是大值的左节点，这样就形成了一颗红黑树。

将上面的 2-3 树的例子拿过来对比一下

红黑树与 2-3 树对比

有一个重要的点是：红黑树不是完美的平衡二叉树，它只是近似平衡，我刚开始以为它是一颗平衡二叉树，在进行转换的时候就有了一下困难。

我们可以将它的结构用代码定义一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private class Node {
    Key key;
    Val val;
    Node left,right;
    boolean color; // true 为红，false 为黑
    
    Node(Key key,Val val,boolean color){
        this.key = key;
        this.val = val;
        this.color = color;
    }
    
    private boolean isRed(Node x){
        if(x==null){ return false;}
        return x.color;
    }
    
    ...
            
}

插入

首先我们明确，新插入的节点都是红色的，然后经过一系列操作它可能会改变颜色，但是我们在新建节点来插入时它是红色的。

我们在讲插入之前先来讲一下插入过程中需要的变换

旋转

左旋转

左旋转

代码简单实现如下：

1
2
3
4
5
6
7
8
9
10
Node rotateLeft(Node h){
    //变换位置
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    //变色
    x.color = h.color;
    h.color = true;
    return x;
}

右旋转

右旋转

代码简单实现如下：

1
2
3
4
5
6
7
8
9
10
Node rotateRight(Node h){
    //变换位置
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    //变色
    x.color = h.color;
    h.color = true;
    return x;
}

旋转操作可以保持红黑树的两个重要性质：有序性和完美平衡性

那我们就开始一个红黑树的插入：

  1. 向单个2-节点插入

  1. 向树底部的 2-节点插入

  2. 向 3-节点插入

    上面的第二、三种情况用到了颜色转换，将两个孩子节点变成黑色，将父节点变成红色，简单代码如下：

    1
    2
    3
    4
    5
    void flipColors(Node h){
        h.color = true;
        h.left.color=false;
        h.right.color = false;
    }

接下来我们用一个例子来说明一下这个过程：[1,3,5,7,9,2,4,6,8]

并且简单代码如下：

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
public void put(Key key,Val val){
    root = put(root,key,val);
    //最终保证根节点为黑色
    root.color = false;
}

private Node put(Node h,Key key,Val val){
    if(h==null){
        return new Node(key,val,true); //每次都插入一个红节点
    }
    int cmp = compareTo(h.key);
    //判断大小关系后递归调用
    //需要返回值的原因是 当添加值之后可能会影响性质，需要旋转变色等。也就是节点发生了变换，需要重新赋值。
    if(cmp<0){
        h.left = put(h.left,key,val);
    }else if(cmp>0){
        h.right = put(h.right,key,val);
    }else {
        h.val = val;
    }
    
    if( isRed(h.right) && !isRed(h.left) ){
        //右节点为红色，左节点为空或者黑色时需要左旋转
        h = rotateLeft(h);
    }
    if( isRed(h.left) && isRed(h.left.left) ){
        //当左节点为红色，左节点的左节点也为红色时，需要进行右旋转
        h = rotateRight(h);
    }
    if( isRed(h.left) && isRed(h.right) ){
        //当两个子节点都为红色时，将两个子节点变黑，根节点变红
        flipColors(h);
    }
}

然后我们来看一下图示过程：

后续

关于节点删除的部分后面继续添加

参考