Jared's blog
Jared H
2020-09-01

基本数据结构

# 基础

# 概念

程序=数据结构+算法

# 算法复杂度

算法复杂度分为时间复杂度和空间复杂度。

算法的复杂性体运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。

# 时间复杂度

是指执行算法所需要的计算工作量，指时间增长的趋势。

T(n) = O( f ( n ) )

  • 常用时间复杂度量级：

  1. 常数阶O(1)： 算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。

    int x = 0; 
int y = 1; 
int temp = x; 
x = y ;
y = temp;
    1
    2
    3
    4
    5

    该程序段的执行时间是一个与问题规模n无关的常数

  2. 对数阶$O(logN)$ ：由于计算机使用二进制的记数系统，对数常常以2为底（即 $ log_2n $，有时写作 $logn$ ）。然而，由对数的换底公式，$log_an$ 和 $ log_bn$只有一个常数因子不同，这个因子在大O记法中被丢弃。因此记作 $ O（logn）$，而不论对数的底是多少，是对数时间算法的标准记法。

    典型的二分查找法：假如有32份试卷，你丢一次，还剩16份 ，丢两次，还剩下8 份，丢三次，就只剩下4份了，可以这么一直丢下去，丢到第五次，就只剩下一份了。而$log_2(32)=5 $。也就是我们一次丢一半，总要丢到只有一份的时候才能出结果，如果有n份，那么显然我们就有 $n/2^k =1 => l=log_2n $

  3. 线性阶O(n)： 随着样本数量的增加，复杂度也随之线性增加

    for(int i = 1;i<=n;i++){
    x++;		//O(1+3N)=O(N)
}
    1
    2
    3

  4. 线性对数阶O(nlogN)：

    比如对一堆带有序号的书进行排序。先选一本，然后把号码大于这本书的扔右边，小于这本书的扔左边。因为每本书都要比较一次，所以这么搞一次的复杂度是 O(n)，那么快排需要我们搞多少次呢？这个又回到了二分查找的逻辑了，每次都把书堆一分为二，请问分多少次手里才能只剩下一本书呢？答案还是logn。而从代码的角度来说，在到达大小为一的数列之前，我们也是需要作logn次嵌套的调用。

  5. 方阶$O(n^2)$： 计算的复杂度随着样本个数的平方数增长

    在比如说构建一个网络，每个点都和其他的点相连。显然，每当我们增加一个点，其实就需要构建这个点和所有现存的点的连线，而现存的点的个数是n，所以每增加1，就需要增加n个连接，那么如果我们增加n个点呢，那这个连接的个数自然也就是 $n^2$ 量级了。

----------------TODO---------------

  • 立方阶 $O( n^3 )$

  • k次方阶 $O(n^k)$

  • 指数阶$ O(2^n)$

  • 阶乘 O( n!)

----------------TODO---------------

# 空间复杂度

是指对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势。

S(n) = O( f ( n ) )

  • 常见的空间复杂度$O(1)、O(n)、O(n^2)$:

  1. O(1)

    如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

    int x = 0;
int y = 0;
x++;
y++;
    1
    2
    3
    4

    代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

  2. O(n)

    int[] newArray = new int[n];
for(int i = 0; i < 0; i++){
    newArray[i]=i;
}
    1
    2
    3
    4

    上面这段代码中，new了一个数组出来，占用空间大小为n，后面的for循环只是给这个数组赋值并没有分配新的空间，因此这段代码的空间复杂度主要取决于 n 的大小。

  3. $O(n^2)$

    比如说二维数组...

# 结构

# 线性结构

# 数组

数组是列表的实现方式之一，数组中的元素在内存中是连续存储的，且每个元素占用相同大小的内存。

数组的优点:

  • 检索效率高

数组的缺点:

  • 随机增删元素的效率较低

  • 事先必须知道数组的长度

  • 空间通常是有限制的

  • 需要大块连续的内存块

# 链表

链表中每一个节点都包含此节点的数据和指向下一节点地址的指针。由于是通过指针进行下一个数据元素的查找和访问，使得链表的自由度更高。

这表现在对节点进行增加和删除时，只需要对上一节点的指针地址进行修改，而无需变动其它的节点。不过事物皆有两极，指针带来高自由度的同时，自然会牺牲数据查找的效率和多余空间的使用。

链表的优点：

  • 随机增删元素效率较高（因为增删元素不涉及到大量元素的位移）

链表的缺点：

  • 查询效率低，每一次查找某个元素的时候都需要从头节点开始往下遍历

# 队列

队列是一种 FIFO 式的数据结构：第一个元素将被首先处理。有两个重要操作：入队和出队。我们可以使用带有两个指针的动态数组来实现队列。

我们可以使用广度优先搜索（BFS）。

  • 使用数组实现的叫静态队列
  • 使用链表实现的叫动态队列

# 栈

栈是一种 LIFO 式的数据结构：最后一个元素将被首先处理。有两个重要操作：push 和 pop。栈的实现非常简单，使用动态数组就足以实现栈。

当满足 LIFO 原则时，我们使用栈。深度优先搜索（DFS）是栈的一个重要应用。

  • 使用数组实现的叫静态栈
  • 使用链表实现的叫动态栈

# 散列表

散列表（Hash table，也叫哈希表）是一种查找算法，与链表、树等算法不同的是，散列表算法在查找时不需要进行一系列和关键字（关键字是数据元素中某个数据项的值，用以标识一个数据元素）的比较操作。

散列表算法希望能尽量做到不经过任何比较，通过一次存取就能得到所查找的数据元素， 因而必须要在数据元素的存储位置和它的关键字（可用 key 表示）之间建立一个确定的对应关系，使每个关键字和散列表中一个唯一的存储位置相对应。因此在查找时，只要根据这个对应关系找到给定关键字在散列表中的位置即可。这种对应关系被称为散列函数(可用 h(key)表示)。

有两种不同类型的哈希表：哈希集合和哈希映射。

  • 哈希集合是集合数据结构的实现之一，用于存储非重复值。
  • 哈希映射是映射 数据结构的实现之一，用于存储(key, value)键值对。

用的构造散列函数的方法有：

（1）直接定址法： 取关键字或关键字的某个线性函数值为散列地址。

即：h(key) = key 或 h(key) = a * key + b，其中 a 和 b 为常数。

（2）数字分析法：找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

（3）平方取值法： 取关键字平方后的中间几位为散列地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址

例：我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11，E的内部编码为05，Y的内部编码为25，A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501，同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后，取出第7到第9位作为该关键字哈希地址，如下所示

关键字 内部编码 内部编码的平方值 H(k)关键字的哈希地址
KEYA 11052501 122157778355001 778
KYAB 11250102 126564795010404 795
AKEY 01110525 001233265775625 265
BKEY 02110525 004454315775625 315

（4）折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址。

例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。

（5）除留余数法：取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址，

即：h(key) = key MOD p p ≤ m

（6）随机数法：选择一个随机函数，取关键字的随机函数值为它的散列地址，

即：h(key) = random(key)

# 逻辑结构

# 树

树是一种数据结构，它是n(n>=0)个节点的有限集。n=0时称为空树。n>0时，有限集的元素构成一个具有层次感的数据结构。

img

区别于线性表一对一的元素关系，树中的节点是一对多的关系。树具有以下特点:

  • n>0时，根节点是唯一的，不可能存在多个根节点。
  • 每个节点有零个至多个子节点；除了根节点外，每个节点有且仅有一个父节点。根节点没有父节点。

# 树的相关概念

树有许多相关的术语与概念，在学习树的结构之前，我们要熟悉这些概念。

  • 子树: 除了根节点外，每个子节点都可以分为多个不相交的子树。(图二)
  • 孩子与双亲: 若一个结点有子树，那么该结点称为子树根的"双亲"，子树的根是该结点的"孩子"。在图一中，B、H是A的孩子，A是B、H的双亲。
  • 兄弟: 具有相同双亲的节点互为兄弟，例如B与H互为兄弟。
  • 节点的度: 一个节点拥有子树的数目。例如A的度为2，B的度为1，C的度为3.
  • 叶子: 没有子树，也即是度为0的节点。
  • 分支节点: 除了叶子节点之外的节点，也即是度不为0的节点。
  • 内部节点: 除了根节点之外的分支节点。
  • 层次: 根节点为第一层，其余节点的层次等于其双亲节点的层次加1.
  • 树的高度: 也称为树的深度，树中节点的最大层次。
  • 有序树: 树中节点各子树之间的次序是重要的，不可以随意交换位置。
  • 无序树: 树种节点各子树之间的次序是不重要的。可以随意交换位置。
  • 森林: 0或多棵互不相交的树的集合。例如图二中的两棵树为森林。

树的遍历

  • 先(根)序遍历（根左右）

  • 中(根)序遍历（左根右）

  • 后(根)序遍历（左右根）

  • 层次遍历：逐层按一定顺序访问节点

    ​

# 二叉树、完全二叉树、满二叉树

  • 二叉树: 最多有两棵子树的树被称为二叉树

img

  • 斜树: 所有节点都只有左子树的二叉树叫做左斜树，所有节点都只有右子树的二叉树叫做右斜树。(本质就是链表)

img

  • 满二叉树: 二叉树中所有非叶子结点的度都是2，且叶子结点都在同一层次上

    可以看出满二叉树的各个层的结点数形成一个首项为1，公比为2的等比数列，所以由等比公式![](img/00.数据结构/Equilibrium formula.jpg)

    得出一个二叉树的层数为K，则节点总数是$2^k$-1，第k层的节点数为 $2^{k-1}$,非叶子节点数为 $2^{k-1}-1$

img

  • 完全二叉树: 如果一个二叉树与满二叉树前m个节点的结构相同，这样的二叉树被称为完全二叉树

img

# 二叉查找树（BST）

BST的定义:

  • 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 任意节点的左、右子树也分别为二叉查找树。
  • 没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低为 O ( log ⁡ n ) 。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。

BST的实现：

  1. **节点 **

    BSTree是二叉树，它保护了二叉树的根节点mRoot；mRoot是BSTNode类型，而BSTNode是二叉查找树的节点，它是BSTree的内部类。BSTNode包含二叉查找树的几个基本信息:

    • key -- 它是关键字，是用来对二叉查找树的节点进行排序的。
    • left -- 它指向当前节点的左孩子。
    • right -- 它指向当前节点的右孩子。
    • parent -- 它指向当前节点的父结点。
    public class BSTree<T extends Comparable<T>> {

    private BSTNode<T> mRoot;    // 根结点

    public class BSTNode<T extends Comparable<T>> {
        T key;                // 关键字(键值)
        BSTNode<T> left;      // 左孩子
        BSTNode<T> right;     // 右孩子
        BSTNode<T> parent;    // 父结点

        public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
            this.key = key;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }

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

  2. **遍历 **

    • 前序遍历

      private void preOrder(BSTNode<T> tree) {
    if(tree != null) {
        System.out.print(tree.key+" ");
        preOrder(tree.left);
        preOrder(tree.right);
    }
}
//根节点开始
public void preOrder() {
    preOrder(mRoot);
}
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12

    • 中序遍历

      private void inOrder(BSTNode<T> tree) {
    if(tree != null) {
        inOrder(tree.left);
        System.out.print(tree.key+" ");
        inOrder(tree.right);
    }
}

public void inOrder() {
    inOrder(mRoot);
}
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12

    • 后序遍历

      private void postOrder(BSTNode<T> tree) {
    if(tree != null)
    {
        postOrder(tree.left);
        postOrder(tree.right);
        System.out.print(tree.key+" ");
    }
}

public void postOrder() {
    postOrder(mRoot);
}
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13

    • 例如：

      对于上面的二叉树而言，

      • 前序遍历结果: 8 3 1 6 4 7 10 14 13
      • 中序遍历结果: 1 3 4 6 7 8 10 13 14
      • 后序遍历结果: 1 4 7 6 3 13 14 10 8

  3. **查找 **

  • 递归版本的代码
/*
 * (递归实现)查找"二叉树x"中键值为key的节点
 */
private BSTNode<T> search(BSTNode<T> x, T key) {
    if (x==null)
        return x;

    int cmp = key.compareTo(x.key);
    if (cmp < 0)
        return search(x.left, key);
    else if (cmp > 0)
        return search(x.right, key);
    else
        return x;
}

public BSTNode<T> search(T key) {
    return search(mRoot, key);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  • 迭代版本的代码
/*
 * （迭代）查找"二叉树x"中键值为key的节点
 */
private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
    while (x!=null) {
        int cmp = key.compareTo(x.key);

        if (cmp < 0) 
            x = x.left;
        else if (cmp > 0) 
            x = x.right;
        else
            return x;
    }

    return x;
}

public BSTNode<T> iterativeSearch(T key) {
    return iterativeSearch(mRoot, key);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

  1. **最大值和最小值 **

  • 查找最大结点
/* 
 * 查找最大结点: 返回tree为根结点的二叉树的最大结点。
 */
private BSTNode<T> maximum(BSTNode<T> tree) {
    if (tree == null)
        return null;

    while(tree.right != null)
        tree = tree.right;
    return tree;
}

public T maximum() {
    BSTNode<T> p = maximum(mRoot);
    if (p != null)
        return p.key;

    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  • 查找最小结点
/* 
 * 查找最小结点: 返回tree为根结点的二叉树的最小结点。
 */
private BSTNode<T> minimum(BSTNode<T> tree) {
    if (tree == null)
        return null;

    while(tree.left != null)
        tree = tree.left;
    return tree;
}

public T minimum() {
    BSTNode<T> p = minimum(mRoot);
    if (p != null)
        return p.key;

    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  1. **前驱和后继 **

节点的前驱: 是该节点的左子树中的最大节点。 节点的后继: 是该节点的右子树中的最小节点。

  • 查找前驱节点
public BSTNode<T> predecessor(BSTNode<T> x) {
    // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
    if (x.left != null)
        return maximum(x.left);
    // 如果x没有左孩子。则x有以下两种可能: 
    // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
    // (02) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。
    BSTNode<T> y = x.parent;
    while ((y!=null) && (x==y.left)) {
        x = y;
        y = y.parent;
    }
    return y;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • 查找后继节点
public BSTNode<T> successor(BSTNode<T> x) {
    // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
    if (x.right != null)
        return minimum(x.right);

    // 如果x没有右孩子。则x有以下两种可能: 
    // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
    // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
    BSTNode<T> y = x.parent;
    while ((y!=null) && (x==y.right)) {
        x = y;
        y = y.parent;
    }

    return y;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

  1. 插入

/* 
 * 将结点插入到二叉树中
 *
 * 参数说明: 
 *     tree 二叉树的
 *     z 插入的结点
 */
private void insert(BSTree<T> bst, BSTNode<T> z) {
    int cmp;
    BSTNode<T> y = null;
    BSTNode<T> x = bst.mRoot;

    // 查找z的插入位置
    while (x != null) {
        y = x;
        cmp = z.key.compareTo(x.key);
        if (cmp < 0)
            x = x.left;
        else
            x = x.right;
    }

    z.parent = y;
    if (y==null)
        bst.mRoot = z;
    else {
        cmp = z.key.compareTo(y.key);
        if (cmp < 0)
            y.left = z;
        else
            y.right = z;
    }
}

/* 
 * 新建结点(key)，并将其插入到二叉树中
 *
 * 参数说明: 
 *     tree 二叉树的根结点
 *     key 插入结点的键值
 */
public void insert(T key) {
    BSTNode<T> z=new BSTNode<T>(key,null,null,null);

    // 如果新建结点失败，则返回。
    if (z != null)
        insert(this, z);
}
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
  1. 删除

img

/* 
 * 删除结点(z)，并返回被删除的结点
 *
 * 参数说明: 
 *     bst 二叉树
 *     z 删除的结点
 */
private BSTNode<T> remove(BSTree<T> bst, BSTNode<T> z) {
    BSTNode<T> x=null;
    BSTNode<T> y=null;

    if ((z.left == null) || (z.right == null) )
        y = z;
    else
        y = successor(z);

    if (y.left != null)
        x = y.left;
    else
        x = y.right;

    if (x != null)
        x.parent = y.parent;

    if (y.parent == null)
        bst.mRoot = x;
    else if (y == y.parent.left)
        y.parent.left = x;
    else
        y.parent.right = x;

    if (y != z) 
        z.key = y.key;

    return y;
}


public void remove(T key) {
    BSTNode<T> z, node; 

    if ((z = search(mRoot, key)) != null)
        if ( (node = remove(this, z)) != null)
            node = null;
}
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
  1. 打印
/*
 * 打印"二叉查找树"
 *
 * key        -- 节点的键值 
 * direction  --  0，表示该节点是根节点;
 *               -1，表示该节点是它的父结点的左孩子;
 *                1，表示该节点是它的父结点的右孩子。
 */
private void print(BSTNode<T> tree, T key, int direction) {

    if(tree != null) {

        if(direction==0)    // tree是根节点
            System.out.printf("%2d is root\n", tree.key);
        else                // tree是分支节点
            System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");

        print(tree.left, tree.key, -1);
        print(tree.right,tree.key,  1);
    }
}

public void print() {
    if (mRoot != null)
        print(mRoot, mRoot.key, 0);
}
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
  1. 销毁
/*
 * 销毁二叉树
 */
private void destroy(BSTNode<T> tree) {
    if (tree==null)
        return ;

    if (tree.left != null)
        destroy(tree.left);
    if (tree.right != null)
        destroy(tree.right);

    tree=null;
}

public void clear() {
    destroy(mRoot);
    mRoot = null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 平衡二叉树（AVL）

# 什么是AVL树

AVL树是高度平衡的二叉树。它的特点是: AVL树中任何节点的两个子树的高度最大差别为1。

img

上面的两张图片，左边的是AVL树，它的任何节点的两个子树的高度差别都<=1；而右边的不是AVL树，因为7的两颗子树的高度相差为2(以2为根节点的树的高度是3，而以8为根节点的树的高度是1)。

# AVL树的实现
  1. 节点
  • 节点定义

AVLTree是AVL树对应的类，而AVLTreeNode是AVL树节点，它是AVLTree的内部类。AVLTree包含了AVL树的根节点，AVL树的基本操作也定义在AVL树中。AVLTreeNode包括的几个组成对象:

  • key -- 是关键字，是用来对AVL树的节点进行排序的。
  • left -- 是左孩子。
  • right -- 是右孩子。
  • height -- 是高度。
public class AVLTree<T extends Comparable<T>> {
    private AVLTreeNode<T> mRoot;    // 根结点

    // AVL树的节点(内部类)
    class AVLTreeNode<T extends Comparable<T>> {
        T key;                // 关键字(键值)
        int height;         // 高度
        AVLTreeNode<T> left;    // 左孩子
        AVLTreeNode<T> right;    // 右孩子

        public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.height = 0;
        }
    }
    
    ......
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  1. 树的高度

关于高度，有的地方将"空二叉树的高度是-1"，而本文采用维基百科上的定义: 树的高度为最大层次。即空的二叉树的高度是0，非空树的高度等于它的最大层次(根的层次为1，根的子节点为第2层，依次类推)。

/*
 * 获取树的高度
 */
private int height(AVLTreeNode<T> tree) {
    if (tree != null)
        return tree.height;

    return 0;
}

public int height() {
    return height(mRoot);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
  1. 比较大小
/*
 * 比较两个值的大小
 */
private int max(int a, int b) {
    return a>b ? a : b;
}
1
2
3
4
5
6
  1. 旋转

如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡。这种失去平衡的可以概括为4种姿态: LL(左左)，LR(左右)，RR(右右)和RL(右左)。下面给出它们的示意图:

img

上图中的4棵树都是"失去平衡的AVL树"，从左往右的情况依次是: LL、LR、RL、RR。除了上面的情况之外，还有其它的失去平衡的AVL树，如下图:

img

上面的两张图都是为了便于理解，而列举的关于"失去平衡的AVL树"的例子。总的来说，AVL树失去平衡时的情况一定是LL、LR、RL、RR这4种之一，它们都由各自的定义:

(1) LL: LeftLeft，也称为"左左"。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。 例如，在上面LL情况中，由于"根节点(8)的左子树(4)的左子树(2)还有非空子节点"，而"根节点(8)的右子树(12)没有子节点"；导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

(2) LR: LeftRight，也称为"左右"。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。 例如，在上面LR情况中，由于"根节点(8)的左子树(4)的左子树(6)还有非空子节点"，而"根节点(8)的右子树(12)没有子节点"；导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

(3) RL: RightLeft，称为"右左"。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。 例如，在上面RL情况中，由于"根节点(8)的右子树(12)的左子树(10)还有非空子节点"，而"根节点(8)的左子树(4)没有子节点"；导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

(4) RR: RightRight，称为"右右"。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。 例如，在上面RR情况中，由于"根节点(8)的右子树(12)的右子树(14)还有非空子节点"，而"根节点(8)的左子树(4)没有子节点"；导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡。AVL失去平衡之后，可以通过旋转使其恢复平衡，下面分别介绍"LL(左左)，LR(左右)，RR(右右)和RL(右左)"这4种情况对应的旋转方法。

4.1 LL的旋转

LL失去平衡的情况，可以通过一次旋转让AVL树恢复平衡。如下图:

img

图中左边是旋转之前的树，右边是旋转之后的树。从中可以发现，旋转之后的树又变成了AVL树，而且该旋转只需要一次即可完成。 对于LL旋转，你可以这样理解为: LL旋转是围绕"失去平衡的AVL根节点"进行的，也就是节点k2；而且由于是LL情况，即左左情况，就用手抓着"左孩子，即k1"使劲摇。将k1变成根节点，k2变成k1的右子树，"k1的右子树"变成"k2的左子树"。

/*
 * LL: 左左对应的情况(左单旋转)。
 *
 * 返回值: 旋转后的根节点
 */
private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2) {
    AVLTreeNode<T> k1;

    k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;

    k2.height = max( height(k2.left), height(k2.right)) + 1;
    k1.height = max( height(k1.left), k2.height) + 1;

    return k1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4.2 RR的旋转

理解了LL之后，RR就相当容易理解了。RR是与LL对称的情况！RR恢复平衡的旋转方法如下:

img

图中左边是旋转之前的树，右边是旋转之后的树。RR旋转也只需要一次即可完成。

/*
 * RR: 右右对应的情况(右单旋转)。
 *
 * 返回值: 旋转后的根节点
 */
private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1) {
    AVLTreeNode<T> k2;

    k2 = k1.right;
    k1.right = k2.left;
    k2.left = k1;

    k1.height = max( height(k1.left), height(k1.right)) + 1;
    k2.height = max( height(k2.right), k1.height) + 1;

    return k2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  1. 3 LR的旋转

LR失去平衡的情况，需要经过两次旋转才能让AVL树恢复平衡。如下图:

img

第一次旋转是围绕"k1"进行的"RR旋转"，第二次是围绕"k3"进行的"LL旋转"。

/*
 * LR: 左右对应的情况(左双旋转)。
 *
 * 返回值: 旋转后的根节点
 */
private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3) {
    k3.left = rightRightRotation(k3.left);

    return leftLeftRotation(k3);
}
1
2
3
4
5
6
7
8
9
10
  1. 4 RL的旋转

RL是与LR的对称情况！RL恢复平衡的旋转方法如下:

img

第一次旋转是围绕"k3"进行的"LL旋转"，第二次是围绕"k1"进行的"RR旋转"。

/*
 * RL: 右左对应的情况(右双旋转)。
 *
 * 返回值: 旋转后的根节点
 */
private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1) {
    k1.right = leftLeftRotation(k1.right);

    return rightRightRotation(k1);
}
1
2
3
4
5
6
7
8
9
10
  1. 插入

插入节点的代码

/* 
 * 将结点插入到AVL树中，并返回根节点
 *
 * 参数说明: 
 *     tree AVL树的根结点
 *     key 插入的结点的键值
 * 返回值: 
 *     根节点
 */
private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
    if (tree == null) {
        // 新建节点
        tree = new AVLTreeNode<T>(key, null, null);
        if (tree==null) {
            System.out.println("ERROR: create avltree node failed!");
            return null;
        }
    } else {
        int cmp = key.compareTo(tree.key);

           if (cmp < 0) {    // 应该将key插入到"tree的左子树"的情况
            tree.left = insert(tree.left, key);
            // 插入节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.left) - height(tree.right) == 2) {
                if (key.compareTo(tree.left.key) < 0)
                    tree = leftLeftRotation(tree);
                else
                    tree = leftRightRotation(tree);
            }
        } else if (cmp > 0) {    // 应该将key插入到"tree的右子树"的情况
            tree.right = insert(tree.right, key);
            // 插入节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.right) - height(tree.left) == 2) {
                if (key.compareTo(tree.right.key) > 0)
                    tree = rightRightRotation(tree);
                else
                    tree = rightLeftRotation(tree);
            }
        } else {    // cmp==0
            System.out.println("添加失败: 不允许添加相同的节点！");
        }
    }

    tree.height = max( height(tree.left), height(tree.right)) + 1;

    return tree;
}

public void insert(T key) {
    mRoot = insert(mRoot, key);
}
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
  1. 删除

删除节点的代码

/* 
 * 删除结点(z)，返回根节点
 *
 * 参数说明: 
 *     tree AVL树的根结点
 *     z 待删除的结点
 * 返回值: 
 *     根节点
 */
private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z) {
    // 根为空 或者 没有要删除的节点，直接返回null。
    if (tree==null || z==null)
        return null;

    int cmp = z.key.compareTo(tree.key);
    if (cmp < 0) {        // 待删除的节点在"tree的左子树"中
        tree.left = remove(tree.left, z);
        // 删除节点后，若AVL树失去平衡，则进行相应的调节。
        if (height(tree.right) - height(tree.left) == 2) {
            AVLTreeNode<T> r =  tree.right;
            if (height(r.left) > height(r.right))
                tree = rightLeftRotation(tree);
            else
                tree = rightRightRotation(tree);
        }
    } else if (cmp > 0) {    // 待删除的节点在"tree的右子树"中
        tree.right = remove(tree.right, z);
        // 删除节点后，若AVL树失去平衡，则进行相应的调节。
        if (height(tree.left) - height(tree.right) == 2) {
            AVLTreeNode<T> l =  tree.left;
            if (height(l.right) > height(l.left))
                tree = leftRightRotation(tree);
            else
                tree = leftLeftRotation(tree);
        }
    } else {    // tree是对应要删除的节点。
        // tree的左右孩子都非空
        if ((tree.left!=null) && (tree.right!=null)) {
            if (height(tree.left) > height(tree.right)) {
                // 如果tree的左子树比右子树高；
                // 则(01)找出tree的左子树中的最大节点
                //   (02)将该最大节点的值赋值给tree。
                //   (03)删除该最大节点。
                // 这类似于用"tree的左子树中最大节点"做"tree"的替身；
                // 采用这种方式的好处是: 删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。
                AVLTreeNode<T> max = maximum(tree.left);
                tree.key = max.key;
                tree.left = remove(tree.left, max);
            } else {
                // 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1)
                // 则(01)找出tree的右子树中的最小节点
                //   (02)将该最小节点的值赋值给tree。
                //   (03)删除该最小节点。
                // 这类似于用"tree的右子树中最小节点"做"tree"的替身；
                // 采用这种方式的好处是: 删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。
                AVLTreeNode<T> min = maximum(tree.right);
                tree.key = min.key;
                tree.right = remove(tree.right, min);
            }
        } else {
            AVLTreeNode<T> tmp = tree;
            tree = (tree.left!=null) ? tree.left : tree.right;
            tmp = null;
        }
    }

    return tree;
}

public void remove(T key) {
    AVLTreeNode<T> z; 

    if ((z = search(mRoot, key)) != null)
        mRoot = remove(mRoot, z);
}
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

# 哈夫曼树

哈夫曼又称最优二叉树, 是一种带权路径长度最短的二叉树。(注意带权路径WPL是指叶子节点)

img

  • 路径与路径长度: 从树中一个节点到另一个节点之间的分支构成了两个节点之间的路径，路径上的分支数目称作路径长度。若规定根节点位于第一层，则根节点到第H层的节点的路径长度为H-1。如到40 的路径长度为1；30的路径长度为2；20的路径长度为3。
  • 节点的权: 将树中的节点赋予一个某种含义的数值作为该节点的权值，该值称为节点的权；
  • 带权路径长度: 从根节点到某个节点之间的路径长度与该节点的权的乘积。例如上图节点10的路径长度为3,它的带权路径长度为10 * 3 = 30；
  • 树的带权路径长度: 树的带权路径长度为所有叶子节点的带权路径长度之和，称为WPL。上图的WPL = 1x40+2x30+3x10+3x20 = 190，而哈夫曼树就是树的带权路径最小的二叉树。
# 哈夫曼树的构建

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，哈夫曼树的构造规则为:

  • 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
  • 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
  • 从森林中删除选取的两棵树，并将新树加入森林；
  • 重复上面两步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

上图中，它的叶子节点为{10，20，30，40}，以这4个权值构建哈夫曼树的过程为:

img

# 哈夫曼编码

为{10，20，30，40}这四个权值构建了哈夫曼编码后，我们可以由如下规则获得它们的哈夫曼编码:

从根节点到每一个叶子节点的路径上，左分支记为0，右分支记为1，将这些0与1连起来即为叶子节点的哈夫曼编码。如下图:

(字母)权值 编码
10 100
20 101
30 11
40 0

由此可见，出现频率越高的字母(也即权值越大)，其编码越短。这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

具体流程如下:

img

# 多叉树

减少树的高度，能对二叉树进行优化

# B树、B+树、B*树

2-3树（最简单的B树结构）

  • 2-3树的所有叶子节点都在同一层（只要是B树都满足这个条件）
  • 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个字节点，以此类推，234树等也是一种B树

B树的介绍

B树通过重新组织节点，降低树的高度，并且减少 i/o 读写次数来提升效率。

  • 如图B树通过重新组织节点，降低了树的高度

  • 文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页（页的大小通常为4k），这样每个节点只需要一次I/O 就可以完全载入

  • 将树的度M设置为1024,在600亿个元素中最多只需要4次I/O操作就可以读取到想要的元素,B树（B+）广泛应用于文件存储系统以及数据库系统中

对上图的说明：

**1）B树的阶：**节点的最多字节点个数。比如2-3树的阶是3，2-3-4树的阶是4

2）B树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结

3）关键字集合分布在整颗树中，即叶子节点和非叶子节点都存放数据

4）搜索有可能在非叶子结点结束

5）其搜索性能等价于在关键字全集内做一次二分查找

B+树的介绍

  • B+树是B树的变体，也是一种多路搜索树。

  • B+树的说明：

    • B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找
    • 所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字(数据)恰好是有序的。
    • 不可能在非叶子结点命中
    • 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
    • B+树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录
    • B+树更适合文件索引系统，B树和B+树各有自己的应用场景，不能说B+树完全比B树好，反之亦然

    B*树的介绍

    • B* 树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针。
    • B* 树的说明：
      • B* 树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3，而B+树的块的最低使用率为B+树的1/2。
      • 从第1个特点我们可以看出，B* 树分配新结点的概率比B+树要低，空间使用率更高

# 红黑树(R-B Tree)

红黑树与AVL树的比较:

  • AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异
  • 红黑树的插入删除比AVL树更便于控制操作
  • 红黑树整体性能略优于AVL树(红黑树旋转情况少于AVL树)

红黑树的性质: 红黑树是一棵二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。

具体性质如下:

  • 每个节点颜色不是黑色，就是红色
  • 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
  • 根节点是黑色的
  • 如果一个节点是红色，那么它的两个子节点就是黑色的(没有连续的红节点)
  • 对于每个节点，从该节点到其后代叶节点的简单路径上，均包含相同数目的黑色节点

# 图

图的常用概念

  1. 顶点（vertex）

  2. 边（edge）

  3. 路径

  4. 无向图

  5. 有向图

  6. 带权图

图的表示方式

  1. 邻接矩阵

    邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是row和col表示的1....n个点。

  2. 邻接表

    • 邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在，会造成空间的一定损失。

    • 邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成

参考-JAVA全栈知识体系 (opens new window)

上次更新: 2021/05/03, 17:04:23
JavaThread3
计算机网络

← 计算机网络→

Theme by Vdoing Copyright © 2020-2021 Jared H
粤ICP备20046800号
×