参考资料:

1. Java版数据结构与算法导论
2. OI Wiki

常用工具:

1. 在线运行
2. 速查手册

相关代码: HenryJi529/AlgorithmJourney

绪论

数据对象: 具有相同性质的数据元素的集合

数据结构: 相互之间存在一种或多种特定关系的数据元素的集合

数据结构三要素: 逻辑结构【线性、树形、图形】、存储结构(物理结构)【顺序结构、链式结构】、数据运算

数据的物理结构(存储结构): 顺序存储、链式存储、索引存储、散列存储(哈希存储)

数据类型、抽象数据类型: 数据类型是一种编程语言所支持的基本数据类型，如整数、浮点数、布尔型等，而抽象数据类型则是对数据类型的一种抽象描述，它是一种数据类型的抽象。

算法: 有穷性、确定性、可行性、输入输出、【正确性、可读性、健壮性、高效率与低存储】

算法的度量:

1. 时间复杂度
   • 只考虑N很大的情况: 算法的性能问题只有在n很大时才会暴露出来
2. 空间复杂度
   • 原地工作: 算法所需内存为常量

排序算法

具体实现

冒泡排序(Bubble Sort)

原理: 从列表的未排序部分第一个到最后一个元素，比较相邻元素，大的放后面。

实现:

def bubble_sort(arr):
    array = deepcopy(arr)
    for i in range(len(array)):
        for j in range(0, len(array) - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]

    return array

选择排序(Selection Sort)

原理: 选择列表未排序部分最小的元素放在未排序部分的开头

实现:

def selection_sort(arr):
    array = deepcopy(arr)
    for i in range(len(array) - 1):
        min_index = i
        for j in range(i + 1, len(array)):
            if array[min_index] > array[j]:
                min_index = j
        array[min_index], array[i] = array[i], array[min_index]
    return array

插入排序(Insertion Sort)

原理: 将列表未排序部分的元素依次插入已排序部分

实现:

def insertion_sort(arr):
    array = deepcopy(arr)
    for i in range(len(array) - 1):
        for j in range(i + 1, 0, -1):
            if array[j - 1] > array[j]:
                array[j - 1], array[j] = array[j], array[j - 1]
            else:
                break
    return array

希尔排序(Shell Sort)

原理: 通过一个逐渐减小的步长将数据分成几组，对每组进行插入排序后减小步长继续分组与排序直至步长为1的操作完成

实现:

def shell_sort_stupid(arr):
    array = deepcopy(arr)
    gap = int(len(array) / 2)

    # 针对每个不为0的gap，分组排序
    while gap > 0:
        for start in range(0, gap):
            for i in range(start, len(array) - gap, gap):
                for j in range(i + gap, start, -gap):
                    if array[j - gap] > array[j]:
                        array[j - gap], array[j] = array[j], array[j - gap]
                    else:
                        break
        gap = int(gap / 2)
    return array

def shell_sort_clever(arr):
    array = deepcopy(arr)
    gap = int(len(array) / 2)

    while gap > 0:
        for i in range(0, len(array) - gap):
            for j in range(i + gap, 0, -gap):
                if array[j - gap] > array[j]:
                    array[j - gap], array[j] = array[j], array[j - gap]
                else:
                    break
        gap = int(gap / 2)
    return array

步长序列/增量序列(gap sequence):

1. 希尔增量: \(n/2, n/4, n/8, \ldots, 1\)
2. Hibbard增量: \(1, 3, 7, 15, 31, \ldots, 2^k-1\), 其中\(2^k-1 \leq n\)
3. Sedgewick增量: \(1, 5, 19, 41, 109, \ldots, 4^k+3 \cdot 2^{k-1}+1,2^k \cdot\left(2^{k+1}-3\right)+1, \ldots\)
4. Knuth增量: \(1, 4, 13, 40, 121, \ldots,\left(3^k-1\right) / 2\), 其中 \(3^k-1 \leq n\) 。

通常来说，希尔排序的性能取决于增量序列的选择，不同的增量序列可能导致不同的性能表现(尽量避免整除关系)。Hibbard增量在实践中通常表现得比较好，但也可以根据具体情况进行调整。

归并排序(Merge Sort)

原理: 二分，排序，合并

实现:

def merge_sort(arr):
    def sort(
        array: List,
        low: int,
        high: int,
    ):
        if low > high:
            return
        mid = low + (high - low) // 2
        if not low == mid:
            sort(array, low, mid)
        if not mid + 1 == high:
            sort(array, mid + 1, high)

        merge(array, low, mid, high)

    def merge(array: List, low: int, mid: int, high: int):
        array1_low, array1_high = low, mid
        array2_low, array2_high = mid + 1, high

        p1 = array1_low
        p2 = array2_low
        p3 = low

        while True:
            if p1 > array1_high:
                assist[p3 : high + 1] = array[p2 : array2_high + 1]
                break
            if p2 > array2_high:
                assist[p3 : high + 1] = array[p1 : array1_high + 1]
                break

            if array[p2] < array[p1]:
                assist[p3] = array[p2]
                p2 += 1
            else:
                assist[p3] = array[p1]
                p1 += 1
            p3 += 1

        array[low : high + 1] = assist[low : high + 1]

    array = deepcopy(arr)
    assist = [0] * len(array)

    sort(array, 0, len(array) - 1)

    return array

快速排序(Quick Sort)

原理: 选择基准值，分解列表为大区和小区，每个区使用快排排序

实现:

def quick_sort(arr):
    def sort(array, low: int, high: int):
        if low >= high:
            return
        partitionIndex = partition(array, low=low, high=high)
        sort(array, low, partitionIndex - 1)
        sort(array, partitionIndex + 1, high)

    def partition(array, low: int, high: int):
        pivot = array[low]
        left = low + 1
        right = high

        while True:
            if array[left] <= pivot:
                if left == high:
                    break
                left += 1
                continue

            if array[right] > pivot:
                if right == low:
                    break
                right -= 1
                continue

            if right < left:
                break

            array[left], array[right] = array[right], array[left]

        array[low], array[right] = array[right], array[low]
        return right

    array = deepcopy(arr)

    sort(array, 0, len(array) - 1)

    return array

进阶版本:

• 平衡快排:
  • 思想: 在进行快速排序的过程中，尽可能地保持子数组的大小平衡，以防止递归深度过深。
  • 方法:
    • 三数取中法: 指的是选取基准点之前我们可以拿出数列中间位置元素的值，将它和首尾的元素进行比较，之后将这三个数中的中间大的数交换到数列首位的位置，之后将这个数作为基准点，尽量减小之后的分区后左右两边的区间长度之差。
    • 随机交换法: 指的是选取基准点之前设计随机种子，通过随机函数得到一个在数列长度内的数，将这个随机数作为索引所指的数和第一个元素进行交换，之后将首位元素作为基准点。

桶排序(Bucket Sort)

思想: 透过键值的部份资讯，将要排序的元素分配至某些"桶"中，藉以达到排序的作用。

流程:

1. 初始化k个桶，将n个元素分配到k个桶中。
2. 对每个桶分别执行排序。
3. 按照桶从小到大的顺序合并结果。

要点: 实现每个桶的平均分配

1. 将每个桶的区间用递归树表示
2. 根据数据概率分布设置每个桶的区间

性质:

• 时间复杂度:
  • 平均复杂度\(O(n \log \frac{n}{k})\): 假设元素在各个桶内平均分布, 那么每个桶内的元素数量为\(\frac{n}{k}\) 。假设排序单个桶使用\(O(\frac{n}{k} \log \frac{n}{k})\)时间, 则排序所有桶使用 \(O(n \log \frac{n}{k})\) 时间。
  • 最好时间复杂度: 当桶数量\(k\)比较大时, 时间复杂度则趋向于\(O(n)\)。
  • 最坏时间复杂度\(O(n^2)\): 在最差情况下，所有数据被分配到一个桶中。
• 空间复杂度为\(O(n+k)\): (非原地排序) 需要借助\(k\)个桶和总共\(n\)个元素的额外空间。
• 稳定性: 是否稳定取决于排序桶内元素的算法是否稳定。

计数排序(Counting Sort)

步骤:

1. 遍历数组，找出其中的最大数字，记为m，然后创建一个长度为m+1的辅助数组 counter。
2. 借助counter统计nums中各数字的出现次数，其中counter[num]对应数字num的出现次数。
3. 由于counter的各个索引天然有序，因此相当于所有数字已经排序好了。接下来，我们遍历counter，根据各数字出现次数从小到大的顺序填入nums即可。

特性:

• 时间复杂度: \(O(n+m)\)
• 空间复杂度: \(O(n+m)\)
• 稳定性: 稳定

局限性:

1. 计数排序只适用于非负整数。
2. 计数排序适用于数据量大但数据范围较小的情况: 如果\(m\)过大，那么\(O(m)\)甚至会超过\(O(n \log n)\)。

基数排序(Radix Sort)

原理: 根据元素的每一位(个位、十位、百位等)进行排序，从最低位到最高位依次进行排序，直到最高位。【由于数字的高位优先级高于低位，因此应该先排序低位再排序高位。】

方法:

性质:

• 时间复杂度: \(O(nk)\)，其中n是排序元素的个数，k是每个元素的最大位数。
• 空间复杂度: \(O(n+d)\)(非原地排序) 需要借助\(d\)个桶和总共\(n\)个元素的额外空间。
• 稳定性: 稳定

局限性:

1. 数据类型限制: 基数排序适用于整数或字符串等固定长度的数据类型，对于浮点数、变长字符串、负数以及结构体等数据类型，实现radix_trait操作非常复杂。【主要原因】
2. 数据范围限制: 基数排序通常适用于每个位置的取值范围较小的情况，如果数据分布不均匀，可能会导致一些桶非常大而另一些桶非常小，影响排序效率。

稳定性分析

• 定义: 数组arr中有若干元素，其中A元素和B元素相等，并且A元素在B元素前面，如果使用某种排序算法排序后，能够保证A元素依然在B元素的前面，那么可以说这个该算法是稳定的。
• 意义: 不同维度的多次排序中，维度1排序完成后，维度2中两个相等的元素应该保持维度1中的顺序
• 分析:
  • 冒泡排序: 只有当\(arr[i]>arr[i+1]\)的时候，才会交换元素的位置，而相等的时候并不交换位置，所以冒泡排序是一种稳定排序算法。
  • 选择排序: 选择排序是给每个位置选择当前元素最小的,例如有数据{\(5(1)\), \(8\), \(5(2)\), \(2\), \(9\)}，第一遍选择到的最小元素为\(2\)，所以\(5(1)\)会和\(2\)进行交换位置，此时\(5(1)\)到了\(5(2)\)后面，破坏了稳定性，所以选择排序是一种不稳定的排序算法。
  • 插入排序: 比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么把要插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
  • 希尔排序: 希尔排序是按照不同步长对元素进行插入排序，虽然一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
  • 归并排序: 归并排序在归并的过程中，只有\({arr}[i]>arr[i+1]\)的时候才会交换位置，如果两个元素相等则不会交换位置，所以它并不会破坏稳定性，归并排序是稳定的。
  • 快速排序: 快速排序需要一个基准值，在基准值的右侧找一个比基准值小的元素，在基准值的左侧找一个比基准值大的元素，然后交换这两个元素，此时会破坏稳定性，所以快速排序是一种不稳定的算法。
  • 桶排序: 不确定桶内的排序算法，所以不一定稳定。
  • 计数排序: 无随意交换元素，因此稳定。
  • 基数排序: 由于其桶内排序的过程不会交换相等元素，所以是稳定的。

综合评价

array容器

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	\(O(n^2)\)	\(O(n^2)\)	\(O(n)\)	\(O(1)\)	稳定
选择排序	\(O(n^2)\)	\(O(n^2)\)	\(O(n)\)	\(O(1)\)	不稳定
插入排序	\(O(n^2)\)	\(O(n^2)\)	\(O(n)\)	\(O(1)\)	稳定
希尔排序	\(O(n^{1.3～2})\)	\(O(n^2)\)	\(O(n)\)	\(O(1)\)	不稳定
归并排序	\(O(n\log n)\)	\(O(n\log n)\)	\(O(n\log n)\)	\(O(n)\)	稳定
快速排序	\(O(n\log n)\)	\(O(n^2)\)	\(O(n\log n)\)	\(O(\log n)\)	不稳定
堆排序	\(O(n\log n)\)	\(O(n\log n)\)	\(O(n\log n)\)	\(O(1)\)	不稳定
桶排序	\(O(n \log \frac{n}{k})\)	\(O(n^2)\)	\(O(n)\)	\(O(n+k)\)	看情况
计数排序	\(O(n+m)\)	\(O(n+m)\)	\(O(n+m)\)	\(O(n+m)\)	稳定
基数排序	\(O(nk)\)	\(O(nk)\)	\(O(nk)\)	\(O(n+d)\)	稳定

不同容器的对比

线性表(Linear List)

逻辑结构:

线性表是具有相同数据类型(struct A)的 \(n(n \geq 0)\) 个数据元素的有限序列, 其中 \(n\) 为表长, 当 \(n=0\) 时线性表是一个空表。若用 \(L\) 命名线性表, 则其一般表示为 $$ L=\left(a_1, a_2, \ldots, a_i, a_{i+1}, \ldots, a_n\right) $$

1. \(a_i\)是线性表中的“第\(\mathrm{i}\)个”元素线性表中的位序【位序从1开始，\(a_1\)是表头元素; \(a_n\) 是表尾元素】
2. 除第一个元素外, 每个元素有且仅有一个直接前驱; 除最后一个元素外, 每个元素有且仅 有一个直接后继

基本操作: 创销、增删改查、长度、判空、打印、遍历

存储结构: 可以分为顺序表与链表

顺序表(Sequential List)

基本概念: 用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中, 元素之间的关系由存储单元的邻接关系来体现。

api设计:

• 构造: SequenceList(capacity: int)
• 属性
  • eles: 元素数组
  • N: 线性表长度
• 方法
  • clear: 清空元素
  • isEmpty: 判断是否为空
  • length(): 获取元素个数
  • get(ind): 获取ind索引处的元素
  • append(ele): 末尾添加元素
  • insert(ind, ele): ind索引处插入元素
  • remove(ind): 删除索引ind处的元素
  • indexOf(ele): 获取第一个ele元素的位置，不存在就返回-1
• 操作
  • resize(newSize): 扩容
  • 遍历
    • java:
      1. Iterable<T>接口中的iterator方法[返回一个Iterator<T>对象]
      2. 通过内部类SIterator实现Iterator<T>接口
         1. cursor: 当前指向
         2. hasNext()
         3. next()
    • python:
      • 通过生成器实现__iter__魔法方法
      • 通过__next__与raise StopIteration手动实现__iter__

链表(Linked List)

基本概念: 通过指针链接顺序实现顺序存储

单向链表

api设计:

1. Node<T>

   • 构造方法: Node(T t, Node next)(创建Node对象)
   • 成员变量: T item(存储数据), Node next(指向下一个节点)

2. LinkedList<T>

   • 构造方法
   • 成员方法:
     1. public void clear()
     2. public boolean isEmpty()
     3. public int length()
     4. public T get(int i)
     5. public void insert(T t)
     6. public void insert(int i, T t)
     7. public T remove(int i)
     8. public int indexOf(T t)
   • 成员内部类: public class Node
   • 成员变量:
     1. private Node head
     2. private int N

双向列表

注意: java.util.LinkedList官方使用双向链表实现【节点类有三个域】

api设计:

1. Node<T>:

   • 构造方法: Node(T t, Node pre, Node next)(创建Node对象)
   • 成员变量: T item(存储数据), Node next(指向下一个节点), Node pre(指向上一个节点)

2. TowWayLinkList<T>:

   • 构造方法: TowWayLinkList(创建TowWayLinkList对象)
   • 成员方法:
     1. public void clear()(空置线性表)
     2. public boolean isEmpty()(判断线性表是否为空，是返回true，否返回false)
     3. public int length()(获取线性表中元素的个数)
     4. public T get(int i)(读取并返回线性表中的第i个元素的值)
     5. public void insert(T t)(往线性表中添加一个元素)
     6. public void insert(int i, T t)(在线性表的第1个元素之前插入一个值为t的数据元素)
     7. public T remove(int i)(删除并返回线性表中第个数据元素)
     8. public int indexof(T t)(返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回-1)
     9. public T getFirst()(获取第一个元素)
     10. public T getLast()(获取最后一个元素)
   • 成员内部类
     1. private class Node<T>(结点类)
   • 成员变量:
     1. private Node head(记录首结点)
     2. private Node last(记录尾结点)
     3. private int N(记录链表的长度)

性能分析

1. get(int i): 每一次查询，都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多，时间复杂度为O(n)
2. insert(int i,T t): 每一次插入，需要先找到位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)
3. remove(int i): 每一次移除，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)。相比较顺序表，链表插入和删除的时间复杂度虽然一样，但仍然有很大的优势，因为链表的物理地址是不连续的，它不需要预先指定存储空间大小，或者在存储过程中涉及到扩容等操作，同时它并没有涉及的元素的交换。

相比较顺序表，链表的查询操作性能会比较低。因此，如果我们的程序中查询操作比较多，建议使用顺序表，增删操作比较多，建议使用链表。

单链表反转

1. 递归: 当节点没有next时，走到出口，将该节点作为head的后继；存在next时，调整前后节点的指向
2. 迭代: 构造辅助引用

快慢指针

用途:

1. 找中间节点
2. 判断单向链表是否有环
3. 寻找单向链表中环的入口节点: 在快慢指针相遇的地方设为慢指针的新起点，再设置一个新指针(步长为1)，慢新指针相遇的地方就是环的入口

循环链表

定义:

案例: 约瑟夫问题

• 问题描述: 传说有这样一个故事，在罗马人占领乔塔帕特后，39个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆图，第一个人从1开始报数，依次往后，如果有人报数到3，那么这个人就必须自杀，然后再由他的下一个人重新从1开始报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位買，从而逃过了这场死亡游戏。
• 问题转换: 41个人坐一圈，第一个人编号为1，第二个人编号为2，第n个人编号为n。
  1. 编号为1的人开始从1报数，依次向后，报数为3的那个人退出图；
  2. 自退出那个人开始的下一个人再次从1开始报数，以此类推；
  3. 求出最后退出的那个人的编号。

• 图示:

• 解题思路:

  1. 构建含有41个节点的单向循环链表，分别存储1~41的值，分别代表这41个人；
  2. 使用计数器count，记录当前报数的值；
  3. 遍历链表，每循环一次，count++；
  4. 判断count的值，如果是3，则从链表中删除这个节点并打印结点的值，把count重置为0；

栈(Stack)

定义: 栈是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。

api设计:

• 构造方法: Stack<T>
• 成员方法:
  • public boolean isEmpty()
  • public int size()
  • public T pop()
  • public void push(T t)
• 成员变量:
  • private Node head
  • private int N
• 成员内部类: private class Node

案例: 括号匹配问题

• 问题描述: 查表达式中的括号是否正确匹配和嵌套
• 解题思路:
  • 用栈存储左括号
  • 遇到左括号就压栈，遇到右括号就弹栈
  • 如果遍历结束，栈内还有元素，或者遍历过程中出现弹空的情况，代表不匹配

案例: 逆波兰表达式的求值问题

• 问题描述:

  • 中缀表达式: 中缀表达式就是我们平常生活中使用的表达式，例如: 1+3*2, 2-(1+3)等等，中缀表达式的特点是: 二元运算符总是位于两个操作数中间。 中缀表达式是人们最喜欢的表达式方式，因为简单，易样。但是对于计算机来说就不是这样了，因为中缀表达式的运算顺序不具有规律性。不同的运算符具有不同的优先级，如果计算机执行中缀表达式，需要解析表达式语义，做大量的优先級相关操作。
  • 逆波兰表达式(后缀表达式): 运算符总是放在跟他相关的操作数之后

  中缀表达式	逆波兰表达式
  a+b	ab+
  a+(b-c)	abc-+
  a+（b-c）*d	abc-d*+
  a*（b-c）+d	abc-*d+

• 解题思路:

  • 用栈存储操作数
  • 遇到操作数就压栈，遇到操作符就弹出相关的操作数，运算完再压栈【运算要注意操作数顺序】
  • 遍历结束后弹出最后的一个操作数

队列(Queue)

定义: 队列是一种基干先进先出(FIFO)的数据结构，是一种只能在一端进行插入，在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先读被读出来。

api设计:

• 构造方法: Queue<T>
• 成员方法:
  • public boolean isEmpty()
  • public int size()
  • public T dequeue()
  • public void enqueue(T t)
• 成员变量:
  • private Node head
  • private int N
  • private Node last
• 成员内部类: private class Node

符号表(Symbol Table)

定义: 符号表最主要的目的就是将一个健和一个值联系起来，符号表能够将存储的数据元素是一个键和一个值共同组成的健值对数据，我们可以根据键来查找对应的值。【键具有唯一性】

api设计:

• 结点类: Node<Key, Value>
  • 构造方法: Node(Key key, Value value, Node next)
  • 成员变量:
    1. public Key key:存储键
    2. public Value value: 存储值
    3. public Node next: 存储下一个结点
• 符号表: SymbolTable<Key, Value>
  • 构造方法: SymbolTable()
  • 成员方法:
    1. public Value get(Key key): 根据键key，找对应的值
    2. public void put(Key key, Value val): 向符号表中插入一个键值对
    3. public void delete(Key key): 删除键为key的健值对
    4. public int size: 获取符号表的大小
  • 成员变量:
    1. private Node head: 记录首结点
    2. private int N: 记录符号表中健值对的个数

有序符号表(Ordered Symbol Table): 根据插入的Key，判断替换或插入以及插入的位置

用途: 编译器或解释器使用符号表来管理程序中的标识符，确保在程序的不同部分正确引用和使用这些标识符。符号表还有助于解析器在代码中找到变量或函数的信息。

哈希表(Hash Map)

定义: 基于哈希表和哈希函数，通过将键映射到特定桶中，来实现高效的键值对存储和查找操作的一种混合数组与链表的书结构。

分类:

• HashMap
  • 用Array + LinkedList(chaining)实现的能在平均O(1)时间内快速增删查的数据结构
  • 表内存储的数据需要实现equals()和hashCode()
• LinkedHashMap
  • 有顺序的hashmap，遍历顺序是key插入的顺序
  • 所有的key按顺序存成一个LinkedList
• HashSet
  • 没有value的HashMap

还有一种常见的Map就是TreeMap:

• 有顺序的map，遍历顺序是key从小到大
• 所有的key存成一个红黑树(self-balancing binary tree)
• 增删查\(O(\log n)\)

实现:

• 位置选择:
  1. Open Addressing:
     1. 插入: 如果hash(key)%size的位置被占用，就尝试hash(key)%size+1、hash(key)%size+2...
     2. 查找: 如果hash(key)%size的位置不是要找的key，就逐次+1。
  2. Chaining: 把哈希表的每个位置做成一个LinkedList
• 扩容: java中引入load factor(0.75)，当表内元素超过size * load factor时扩容(size * 2)。
• 优化: 当某个链表长度大于8时，改变链表为红黑树

原理介绍

概念:

1. 哈希表: HashMap内部使用一个哈希表来存储键值对。哈希表是一个数组，每个元素通常被称为桶(bucket)。通过一个哈希函数，将键映射到特定的桶位置，以便进行快速查找。

2. 哈希函数: 哈希函数接受一个键作为输入，然后返回一个整数，这个整数通常称为哈希码。哈希码决定了键在哈希表中的存储位置。良好的哈希函数应该能够将键均匀分布到不同的桶中，以避免碰撞(多个键映射到同一个桶的情况)。

3. 冲突处理: 由于哈希函数不一定能完美地将键分散到各个桶中，所以会发生冲突。HashMap使用链表或红黑树来解决冲突，具体取决于每个桶中的元素数量。通常，如果一个桶中的元素较少，就使用链表来存储；如果元素数量超过一个阈值，就将链表转化为红黑树，以提高查找性能。

4. 插入和查找: 插入一个键值对时，首先计算键的哈希码，然后找到对应的桶，如果桶为空，就将键值对直接存入; 如果桶不为空，就根据键来查找对应的元素。查找操作也是通过哈希码找到桶，然后再在桶内查找对应的元素。

5. 扩容: 为了防止哈希表过度拥挤，当元素数量超过一定阈值时，HashMap会自动扩容。扩容通常会创建一个新的更大的哈希表，将所有现有元素重新分配到新的桶中，以保持哈希表的性能。

哈希算法

• 直接寻址法: 使用key本身或key的某个线性函数值作为散列地址 $$ f(key) = a \times k e y+b(a, b\text{为常数}) $$
  • 优点就是简单，均匀也不会产生冲突，但问题是这需要事先知道关键字的分布情况
  • 适合查找表较小且连续的情况，由于这样的限制，此方法并不常用
• 数字分析法: 通常用于处理大量数字类型的key，它利用数字中的一些特征或模式来计算散列地址
  • 例如，如果关键字是一组电话号码，数字分析法可能会根据号码的某些位数或者号码中的某些数字来计算散列地址
  • 数字分析法通常适合处理key位数比较大的情况，如果事先知道key的分布且key的若干位分布较均匀，就可以考虑用这个方法
• 平方取中法: 取关键字平方的中间位数作为散列地址
  • 例如，假设关键字是4321，那么它的平方就是18671041，抽取中间的3位就可以是 671，也可以是710，用做散列地址
  • 比较适合于不知道key的分布，而位数又不是很大的情况
• 折叠法: 折叠法将关键字分成固定长度的片段，然后将这些片段相加，取结果的后几位作为散列地址
  • 假设关键字是9876543210，散列表表长为三位，则我们可以将它分为四组987|654|321|0，然后将它们叠加求和987+654+321+0=1962，再取后3位得到散列地址即为962
  • 这种方法通常用于处理事先不需要知道关键字的分布，适合关键字位数较多的情况
• 除留余数法: 对于散列表长为m的散列函数公式为 $$ f(\text{key})=\text { key mod p }(p \leq m) $$
  • 本方法的关键就在于选择合适的p，根据前辈们的经验，通常p为小于或等于表长(最好接近)的最小质数或不包含小于20质因子的合数
  • 此方法为最常用的构造散列函数方法
• 乘余取整法: 将关键字乘以一个常数，然后取结果的整数部分作为哈希值
  • 这个常数通常是一个介于0到1之间的数，以便将关键字映射到哈希表的索引范围内
• 随机数法: 使用随机数生成散列地址 $$ f(\text{key})=\operatorname{random}(\text { key }) $$
  • 优势在于可以避免一些常规方法可能导致的碰撞，但也需要额外的随机数生成器

复杂度分析

1. 插入(Insertion): 向哈希表中插入一个键-值对的平均时间复杂度通常是\(O(1)\)。这意味着在平均情况下，插入操作需要常数时间。然而，如果哈希表装载因子过高，可能需要重新调整哈希表的大小，这会引入一定的开销。

2. 查找(Retrieval): 从哈希表中查找一个特定键的值的平均时间复杂度通常也是\(O(1)\)。这是哈希表的主要优点之一。

3. 删除(Deletion): 删除一个键-值对的平均时间复杂度通常也是\(O(1)\)。

需要注意的是，上述复杂度是在平均情况下的估算。在实际应用中，哈希表的性能取决于多个因素，包括哈希函数的质量、冲突解决策略、装载因子等。如果哈希冲突(多个键映射到同一个哈希桶)发生频繁，查找和插入操作的时间复杂度可能会退化为\(O(n)\)，其中\(n\)是哈希表的大小。因此，设计一个好的哈希函数和有效的冲突解决策略对哈希表的性能至关重要。

此外，装载因子(Load Factor)是一个关键因素，它表示已经存储在哈希表中的元素数量与哈希表总容量的比例。当装载因子超过某个阈值时，通常需要重新调整哈希表的大小，以保持性能。

综上所述，哈希表在平均情况下具有\(O(1)\)的插入、查找和删除复杂度，但在实际应用中，需要谨慎选择哈希函数和合理管理装载因子以确保性能维持在理想水平。

二叉树(Binary Tree)

树的基本概念:

1. 树的度: 所有节点的度的最大值，未必是根的度
2. 节点的深度: 当前节点到根节点的路径长度
3. 树的高度: 根节点到最远子节点的路径长度(一般通过左右子数计算)
4. 森林: m(m>=0)个互不相交的树的集合，将一颗非空树的根结点删去，树就变成一个森林; 给森林增加一个统一的根结点，森林就变成一棵树

二叉树定义: 度不超过2的树

分类:

1. 二叉搜索树(Binary Search Tree，BST): 在BST中，每个节点的左子树包含的值都小于该节点的值，而右子树包含的值都大于该节点的值。这种特性使得在BST中进行搜索、插入和删除操作都非常高效。

2. 完全二叉树(Complete Binary Tree): 完全二叉树是一种二叉树，除了最后一层，其他所有层的节点都是满的，并且最后一层的节点尽量集中在树的左侧。完全二叉树常用于堆数据结构的实现。

3. 满二叉树(Full Binary Tree): 满二叉树是一种二叉树，每个节点都有0或2个子节点，没有节点有只有一个子节点。满二叉树中的节点数是2的幂次方。

4. 平衡二叉树(Balanced Binary Tree): 平衡二叉树是一种二叉搜索树，其左子树和右子树的高度差不超过1。平衡二叉树的目的是确保在进行搜索等操作时，树的高度不会变得太大，从而保持操作的效率。

5. 红黑树(Red-Black Tree): 红黑树是一种自平衡的二叉搜索树，它通过一些规则来确保树的高度始终保持在可接受范围内，从而保持高效的操作。

6. 2-3树(2-3 Tree): 2-3树是一种多路搜索树，它允许每个节点包含两个或三个子节点。2-3树可以用来实现动态的有序集合。

7. 二叉堆(Binary Heap): 二叉堆是一种特殊的完全二叉树，用于实现堆数据结构，通常用于优先队列的实现。

8. B树和B+树: B树和B+树是一种多叉搜索树，它们通常用于数据库和文件系统中，以支持高效的插入、删除和搜索操作。

二叉查找树(Binary Search Tree)

api设计:

• 节点类: Node<Key, Value>

  • 构造方法: Node(Key key, Value value, Node left, Node right)
  • 成员变量:
    • public Node left
    • public Node right
    • public Key key
    • public Value value

• 二叉查找树: BinaryTree<Key implements Comparable<Key>, Value value>

  • 构造方法: BinaryTree()
  • 成员变量:
    • private Node root
    • private int N
  • 成员方法:
    • public void put(Key key, Value value): 向树中插入一个键值对
    • private Node put(Node x, Key key, Value val): 给指定树x上，添加键一个键值对，并返回添加后的新树
    • public Value get(key key): 根据key，从树中找出对应的值
    • private Value get(Node x, Key key): 从指定的树x中，找出key对应的值
    • public void delete(Key key): 根据key，删除树中对应的键值对
    • private Node delete(Node X, Key key): 删除指定树x上的键为key的键值对，并返回删除后的新树
    • public int size(): 获取树中元素的个数
    • public key max()
    • public Node max(Node x)
    • public key min()
    • public Node min(Node x)
    • public int maxDepth(): 计算整个树的最大深度
    • private int maxDepth(Node x): 计算制定树x的最大深度

树的遍历(Ergodic/Traversal)

• 前序遍历(preErgodic/Preorder Traversal): 根->左->右
• 中序遍历(midErgodic/Inorder Traversal): 左->根->右【对于BST来说，是有序的遍历】
• 后序遍历(afterErgodic/Postorder Traversal): 左->右->根
• 层序遍历(layerErgodic/Levelorder Traversal): 从上往下，从左往右【通过队列实现】

案例: 折纸问题

问题描述: 请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕凸起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。给定一个输入参数\(N\)，代表纸条都从下边向上方连续对折\(N\)次，请从上到下打印所有折痕的方向【例如: \(N=1\) 时，打印down；\(N=2\) 时，打印: down down up】

解决思路:

• 分析:
  1. 根结点为下折痕；
  2. 每一个结点的左子结点为下折痕；
  3. 每一个结点的右子结点为上折痕；
• 解法:
  1. 层序遍历构建树
  2. 中序遍历打印树

哈夫曼树与哈夫曼编码

带权路径长度-定义: (Weighted Path Length, WPL) 设二叉树具有\(n\)个带权值的叶结点, 那么从根结点到各个叶结点的路径长度与相应结点权值的乘积的和, 叫做二叉树的带权路径长度。

带权路径长度-计算:

哈夫曼树-定义: 具有最小带权路径长度的二叉树称为哈夫曼树(也称最优树)

哈夫曼树-构造原则:

• 权值越大的叶结点越靠近根结点。
• 权值越小的叶结点越远离根结点。

哈夫曼树-构造步骤:

1. 构建频率表: 首先需要有一个包含所有字符及其出现频率的表
2. 构建最小堆: 将频率表中的元素构建成一个最小堆，以便总是能够快速找到频率最小的元素
3. 合并节点: 从堆中取出两个频率最小的节点，将它们合并为一个新的节点，其频率是两个节点频率之和
4. 重新加入堆: 将新合并的节点重新加入到堆中
5. 重复步骤3和4: 直到堆中只剩下一个节点，这个节点就是哈夫曼树的根节点

哈夫曼树-性质:

1. 哈夫曼树的结点个数为: \(n=2n_0-1\)

哈夫曼编码-定义: 规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。

哈夫曼编码-优点:

1. 前缀编码: 在一组字符的哈夫曼编码中，不可能出现一个字符的哈夫曼编码是另一个字符哈夫曼编码的前缀。
2. 根据频度来编码，可以让编码尽可能短

树、二叉树和森林间的转换

树转换为二叉树

由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。

将树转换成二叉树的步骤是:

1. 加线: 就是在所有兄弟结点之间加一条连线
2. 抹线: 就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线
3. 旋转: 就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明

森林转换为二叉树

森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。

将森林转换为二叉树的步骤是:

1. 先把每棵树转换为二叉树；
2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程，其步骤是：

1. 若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来；
2. 删除原二叉树中所有结点与其右孩子结点的连线；
3. 整理(1)和(2)两步得到的树，使之结构层次分明

二叉树转换为森林

假如一棵二叉树的根节点有右孩子，则这棵二叉树能够转换为森林，否则将转换为一棵树。

二叉树转换为森林比较简单，其步骤如下:

1. 从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除。直到所有这些根节点与右孩子的连线都删除为止
2. 将每棵分离后的二叉树转换为树

遍历关系

根据树与二叉树的转换关系以及二叉树的遍历定义可以推知，树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同；树的后序遍历与其转换的二叉树的中序遍历的结果序列相同；树的层序遍历与其转换的二叉树的后序遍历的结果序列相同。

由森林与二叉树的转换关系以及森林与二叉树的遍历定义可知，森林的先序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序遍历的结果序列相同。

堆(Heap)

分类:

• 最大堆(Max Heap): 在最大堆中，父节点的值大于或等于其子节点的值。这意味着堆的根节点包含了堆中的最大元素。
• 最小堆(Min Heap): 在最小堆中，父节点的值小于或等于其子节点的值。这意味着堆的根节点包含了堆中的最小元素。

特性:

1. 它是完全二叉树，除了树的最后一层节点不需要是满的，其他的每一层从左到右都是满的，如果最后一层不是满的，那么要求左满右不满。
2. 通常用数组来实现: 将二叉树的节点按照层级顺序放入熟组中，根节点在位置1，它的子节点在位置2和3，而子节点的子节点则分别在位置4、5、6。
   如果一个结点的位置为\(k\)。则它的父结点的位置为\(k/2\),而它的两个子结点的位置则分别为\(2k\)和\(2k+1\)。这样，在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动。
3. 每个结点都大于等于它的两个子结点。【这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的顺序并没有做规定，与二叉查找树不同】

堆的实现

api设计:

• 类名: Heap<T extends Comparable<T>>
• 构造方法: Heap(int capacity)
• 成员方法:
  1. private boolean less(int i,int j): 判断堆中索引i处的元素是否小于索引j处的元素
  2. private void exch（int i,int j）: 交换堆中索引i和索引j处的值
  3. public T delMax(): 删除堆中最大的元素，并返回这个最大元素
  4. public void insert(T t): 往堆中插入一个元素
  5. private void swim(int k): 使用上浮算法，使索引k处的元索能在堆中处于一个正确的位置【逐次与父节点对比交换】
  6. private void sink(int k): 使用下沉算法，使索引k处的元索能在堆中处于一个正确的位置【逐次与最大的子节点对比交换】
• 成员变量
  1. private T[] items: 用来存储元素的数组
  2. private int N: 记录堆中元素的个数

堆排序(Heap Sort)

api设计:

• 类名: HeapSort<T extends Comparable<T>>
• 成员方法:
  1. public static void sort(Comparable[] source): 对source数组中的数据从小到大排序
  2. private static void createHeap(Comparable[] source, Comparable[] heap): 根据原数组source，构造出堆heap
  3. private static boolean less(Comparable[] heap, int i, int j）: 判断heap堆中索引i处的元素是否小于索引j处的元素
  4. private static void exch(Comparable[] heap, int i, int j): 交换heap堆中索引i和索引j处的值
  5. private static void sink(Comparable[] heap, int target, int range): 在heap堆中，对target处的元素做下沉，范围是0-range。

步骤:

1. 完全复制原始数组为堆
2. 从一半的索引处开始下沉【这一步完成后堆有序】
3. N次有范围的堆下沉，每次都将最大的元素放在堆的末尾

优先队列(Priority Queue)

场景:

1. 任务调度
2. 图算法: 在图论中，例如Dijkstra算法和Prim算法，需要根据节点的权重来选择下一个节点。优先队列可以用来高效地管理候选节点，以便找到最短路径或最小生成树。
3. 数据压缩: 在数据压缩算法中，如Huffman编码，需要根据符号的频率来构建编码树。优先队列用于维护频率最低的符号，以便构建有效的编码。
4. 网络路由: 在网络通信中，路由器需要决定如何转发数据包，通常基于目的地的优先级。优先队列可用于路由表的管理。

注意: 优先队列并不一定FIFO，也可能是在同优先级中随机选择元素

优先队列的实现

• 基于堆的实现: 使用堆数据结构来维护元素的优先级，通常是二叉堆或二项堆。这种实现具有较好的时间复杂度，插入和删除的平均复杂度为O(log n)
• 基于有序数组或有序链表的实现: 元素按照优先级有序排列。插入操作较慢，平均复杂度为O(n)，但删除最高优先级元素的操作较快，平均复杂度为O(1)

api设计(以最大优先队列为例):

• 类名: MaxPriorityQueuesT extends Comparable<T>>
• 构造方法: MaxPriorityQueue(int capacity)
• 成员方法:
  1. private boolean less(int i, int j): 判断堆中索引i的元素是否小于索引j处的元素
  2. private void exch(int i,int j): 交换堆中索引i和索引j处的值
  3. public T delMax(): 删除队列中最大的元素，并返回这个最大元素
  4. public void insert(T t): 往队列中插入一个元素
  5. private void swim(int k): 使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
  6. private void sink(int k): 使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
  7. public int size(): 获取队列中元素的个数
  8. public boolean isEmpty(): 判断队列是否为空
• 成员变量:
  1. private T[] items: 用来存储元素的数组
  2. private int N: 记录堆中元素的个数

索引优先队列(Index Priority Queue)

需求: 快速的更新元素的值

原理: 构建一个索引数组来存储元素排序的索引

api设计:

• 类名: IndexMinPriorityQueue<T extends Comparable<T>>
• 构造方法: IndexMinPriorityQueue(int capacity)
• 成员方法:
  1. private boolean less(int i,int j): 判断堆中索引i处的元素是否小于索引j处的元素
  2. private void exch(int i,int j): 交换堆中索引和索引处的值
  3. public int delMin(): 删除队列中最小的元素，并返回该元素关联的索引
  4. public void insert(int i, T t): 往队列中插入一个元素，并关联索引
  5. private void swim(int k): 使用上浮算法，使素引k处的元素能在堆中处于一个正确的位置
  6. private void sink(int k): 使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
  7. public int size(): 获取队列中元素的个数
  8. public boolean isEmpty(): 判断队列是否为空
  9. public boolean contains(int k): 判断k对应的元素是否存在
  10. public void changeItem(int i, T t): 把与索引i关联的元素修改为t
  11. public int minIndex(): 最小元素关联的索引
  12. public void delete(int i): 删除索引i关联的元素
• 成员变量:
  1. private T[] items: 用来存储元素的数组
  2. private int[] pq: 保存每个元索在items数组中的索引，pq数组需要堆有序
  3. private int[] qp: 保存pq的逆序，pq的值作为索引，pq的索引作为值
  4. private int N: 记录堆中元素的个数

平衡树(Balanced Tree)

定义: 在增加或删除元素时保持树的平衡，以确保树的高度(或深度)相对较小，从而保持高效的查找、插入和删除操作。

AVL树

• 定义: 最早被发明的自平衡二叉查找树，由Adelson-Velsky和Landis于1962年发明
• 特性:
  • 平衡性: 对于树中的任何节点，其左子树和右子树的高度差(平衡因子)不能超过1
  • 二叉搜索树: AVL树同时满足二叉搜索树的性质，即对于任何节点，其左子树上的所有节点的值都小于该节点的值，右子树上的所有节点的值都大于该节点的值
  • 自平衡: 在插入和删除操作中，如果违反了平衡性，AVL树会通过旋转操作自动调整自身以恢复平衡。
• 旋转:
  • 左旋(Left Rotation): 当节点的右子树比左子树高时，进行左旋操作
  • 右旋(Right Rotation): 当节点的左子树比右子树高时，进行右旋操作
  • 左右旋(Left-Right Rotation): 当节点的左子树的右子树比左子树高时，先对左子树进行右旋，再对节点进行左旋
  • 右左旋(Right-Left Rotation): 当节点的右子树的左子树比右子树高时，先对右子树进行左旋，再对节点进行右旋
• 操作:
  • 插入:
    • 讲解: 如何理解AVL树这个数据结构
  • 删除:
    • 讲解: AVL树如何删除元素

2-3查找树(Two Three Tree)

特点: 每个节点可以包含两个或三个子节点

• 2节点: 包含一个键和两条链
• 3节点: 包含两个键和三条链【左链接指向的键都小于该节点；中链接指向的键位于该节点两个键之间，右链接指向的键都大于该节点】

插入:

• 向2-节点中插入新键，变成3-节点
• 向一个只含有3-节点的树中插入新键，转换为三个2-节点
• 向一个父节点为2-节点的3-节点中插入新键，将父节点转换为3-节点
• 向一个父节点为3-节点的3-节点中插入新键，但凡提升后，变成4-节点的都需要提升【根节点则需要分解】
• 分解根节点

性质:

1. 任意空链接到根节点的路径长度都是相等的
2. 4-节点变换为3-节点时，树的高度不会产生变化，只有当根节点是临时的4-节点时，分解根节点会导致树高+1
3. 2-3树与普通二叉树的最大区别在于，普通二叉树是自顶向下生长，而2-3树是自底向上生长

红黑树

思想: 对2-3树进行编码，使用标准的二叉查找树和一些额外的信息(替换3-节点)来表示2-3查找树:

• 红链接: 将两个2-节点连接起来构成一个3-节点
• 黑连接: 就是普通链接

定义: 含有红黑链接且满足以下条件的二叉查找树

1. 红链接均为左链接
2. 没有任何一个节点同时和两条红链接相连
3. 该树是完美黑色平衡的，即任意空链接到根节点的路径上的黑链接数量相同

平衡化:

1. 当某个节点的左子节点为黑色，右子节点为红色，此时需要左旋
2. 当某个节点的左子节点为红色，且左子节点的左子节点也是红色，需要右旋

插入实现:

1. 向2-节点中插入新键: 增加红色链接的左子节点/增加红色的右子节点并左旋
2. 平衡化的右旋带来的双红链接解决: 相当于4-节点的拆分，颜色反转即可
3. 向一个3-节点中插入新键: 大于最大的，插入后颜色反转；小于最小的，插入后右旋再颜色反转；介于二者中间，插入后先左旋，再右旋，最后颜色反转
4. 由于根节点不存在父节点，所以每次平衡化后，根节点颜色都要设置为黑色
5. 向树底部的3-节点中插入新键: ...

api设计:

• 节点
  • 类名: Node<Key, Value>
  • 构造方法: Node(Key key, Value value, Node left, Node right, boolean color)
  • 成员变量:
    1. public Node left: 记录左子结点
    2. public Node right: 记录右子结点
    3. public Key key: 存储键
    4. public Value value: 存储值
    5. public boolean color: 由其父结点指向它的链接的颜色
• 红黑树
  • 类名: RedBlackTree<Key extends Comparable<Key>, Value>
  • 构造方法: RedBlackTree()
  • 成员方法:
    1. private boolean isRed(Node x): 判断当前结点的父指向链接是否为红色【特别的，如果节点为空就为非】
    2. private Node rotateLeft(Node h): 左旋调整
    3. private Node rotateRight(Node h): 右旋调整
    4. private void flipColors(Node h): 颜色反转，相当于完成折分4-结点
    5. public void put(Key key, Value val): 在整个树上完成插入操作
    6. private Node put(Node h, Key key, Value val): 在指定树中，完成插入操作，并返回添加元素后新的树
    7. public Value get(Key key): 根据key，从树中找出对应的值
    8. private Value get(Node x, Key key): 从指定的树x中，找出key对应的值
    9. public int size(): 获取树中元素的个数
  • 成员变量:
    1. private Node root: 记录根结点
    2. private int N: 记录树中元素的个数
    3. private static final boolean RED: 红色链接标识
    4. private static final boolean BLACK: 黑色链接标识

AVL树、23查找树、红黑树三者对比

1. 基本结构:
2. AVL树: 一种自平衡的二叉搜索树，每个节点的左右子树的高度差不超过1
3. 2-3查找树: 一种多路搜索树，每个节点可以有两个孩子或三个孩子
4. 红黑树: 一种自平衡的二叉搜索树，边存在不同颜色
5. 平衡机制:
6. AVL树: 通过旋转操作(单旋转和双旋转)来保持节点的平衡
7. 2-3查找树: 通过节点的分裂和合并来保持平衡
8. 红黑树: 通过颜色变换和旋转操作来保持平衡
9. 查找效率:
10. AVL树: 由于保持严格的平衡，查找效率通常很高
11. 2-3查找树: 查找效率通常比AVL树更高，因为树的高度更小
12. 红黑树: 查找效率略低于AVL树和2-3查找树，但由于旋转操作较少，总体性能可能更优
13. 插入和删除操作:
14. AVL树: 可能需要多次旋转来保持平衡
15. 2-3查找树: 可能需要进行节点的分裂和合并
16. 红黑树: 通常只需要少量的旋转和颜色变换
17. 实现复杂性:
18. AVL树: 实现相对简单，主要涉及旋转操作
19. 2-3查找树: 实现更复杂，需要处理节点的分裂和合并
20. 红黑树: 实现复杂性介于AVL树和2-3查找树之间，需要处理颜色变换和旋转
21. 内存使用:
22. AVL树: 通常使用较少的内存，因为不需要存储额外的信息
23. 2-3查找树: 可能使用更多的内存，因为每个节点可能有多个子节点
24. 红黑树: 需要存储颜色信息，但通常比2-3查找树使用更少的内存
25. 应用场景:
26. AVL树: 适合查找操作非常频繁的场景，如数据库索引
27. 2-3查找树: 适合需要高查找效率的场景，如数据库索引和文件系统
28. 红黑树: 适合插入和删除操作频繁的场景，如内存分配器和某些编程语言的库
29. 性能特点:
30. AVL树: 查找性能最佳，但插入和删除操作可能较慢
31. 2-3查找树: 查找性能最佳，插入和删除操作也较为高效
32. 红黑树: 插入和删除性能最佳，查找性能略低于前两者

每种树结构都有其优势和适用场景。选择哪种树结构取决于具体的需求，包括对查找、插入和删除操作的效率要求，以及实现的复杂性和内存使用等因素。

B树(B-Tree)

B树中允许一个结点中包含多个key，可以是3个、4个、5个甚至更多，并不确定，需要看具体的实现。现在我们选择一个参数M，来构造一个B树，我们可以把它称作是M阶的B树，那么该树会具有如下特点:

1. 每个结点最多有M-1个key，井目以升序排列；
2. 每个结点最多能有M个子结点；
3. 根结点至少有两个子结点；

在实际应用中B树的阶数一般都比较大(通常大于100)，所以，即使存储大三的数据，B树的高度仍然比较小，这样在某些应用场景 下，就可以体现出它的优势。

插入思路:

1. 让树向上生长
2. 超出节点key超过M-1时需要提升中间元素

应用: 文件系统在管理磁盘上的文件

磁盘用磁头来读写存储在盘片表面的位，而磁头连按到一个移动臂上，移动臂沿着盘片半径前后移动，可以将磁头定位到任何磁道上，这称之为寻道操作。—旦定位到磁道后，盘片转动，磁道上的每个位经过磁头时，读写磁头就可以感知到该位的值，也可以修改值。对磁盘的访问时问分为寻道时间、旋转时间以及传送时间。

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，因此为了提高效率，要尽量减少磁盘I/O，减少读写操作。为了达到这个日的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理: 当一个数据被用到时，其附近的数据也通常会马上被使用。由于磁盘顺序该取的效率很高(不需要寻道时间，只需很少的旋转时间)，因此预读可以提高I/O效率。

页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页(1024个字节或其整数倍)，预读的长度一般为页的整倍数。主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

文件系统的设计者利用了磁盘预读原理，将一个结点的大小设为等于一个页(1024个字节或其整数倍)，这样每个结点只需要一次I/O就可以完全载入。那么3层的B树可以容纳\(1024 * 1024 * 1024\)养不多10亿个数据，如果换成二叉查找树，则常要30层！假定操作系统一 次读取一个节点，并且根节点保留在内存中，那么B树在10亿个数据中查找目标值，只需要小于3次磁盘读取就可以找到目标值，但红黑树需要小于30次，因此B树大大提高了I/O的操作效率。

B+树(B+ Tree)

特点:

1. 非叶节点仅具有索引作用，也就是说，非叶子节点只存储key，不存储value
2. 树的所有叶节点构成一个有序链表，可以按照key排序的次序遍历全部数据

插入思路: 其分裂与B树的区别在于它是先复制再分裂

对比:

1. 由于B+树在非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下，能够存放更多的key。
2. B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。
3. 由于B树的每一个节点都包含key和value，因此我们根据key查找value时，只需要找到key所在的位置，就能找到value，但B+树只有叶子结点存储数据，索引每一次查找，都必须一次一次，一直找到树的最大深度处，也就是叶子结点的深度，才能找到value。

应用: 数据库中的查询操作

在数据库的操作中，查询操作可以说是最频繁的一种操作，因此在设计数据库时，必须要考虑到查询的效率问题，在很多数据库中，都是用到了B+树来提高查询的效率。

1. 单值查询
2. 区间查询: 找到开头后，就可以利用叶子节点之间的链接遍历

并查集

并查集是一种树型的数据结构，可以高效地进行如下操作:

1. 查询元素p和元素q是否属于同一组
2. 合并元素p和元素q所在的组

结构: 并查集是一种树型结构，但这种树的要求比较简单:

1. 每个元素都唯一的对应一个结点；
2. 每一组数据中的多个元素都在同一颗树中；
3. 一个组中的数据对应的树和另外一个组中的数据对应的树之间没有任何联系；
4. 元素在树中并没有子父级关系的硬性要求；

api设计:

• 类名: DisjointSet
• 构造方法: DisjointSet(int N)
• 成员方法:
  1. public int count(): 获取当前并查集中的数据有多少个分组
  2. public boolean connected(int p,int q): 判断并查集中元素p和元素q是否在同一分组中
  3. public int find(int p): 元素p所在分组的标识符
  4. public void union(int p, int q): 把p元素所在分组和q元素所在分组合并
• 成员变量:
  1. private int[] group: 记录结点的group 标识
  2. private int count: 记录并查集中数据的分组个数

应用:

如果我们并查集存储的每一个整数表示的是一个大型计算机网络中的计算机，则我们就可以通过connected(int p, int q)来检测，该网络中的某两台计算机之间是否连通？如果连通，则他们之间可以通信，如集不连通，则不能通信，此时我们又可以调用union(int p, int q)使得p和q之间连通，这样两台计算机之间就可以通信了。

一般像计算机这样网络型的数据，我们要求网络中的每两个数据之间都是相连通的，也就是说，我们需要调用很多次union方法，使得网络中所有数据相连，其实我们很容易可以得出，如果要让网络中的数据都相连，则我们至少要调用\(N-1\)次union方法才可以，但由于我们的union方法中使用for循环遍历了所有的元素，所以很明显，我们之前实现的合并算法的时间复杂度是\(O(N^2)\)，如果要解决大规模问题，它是不合适的，所以我们需要对算法进行优化。

优化:

1. 用parent存储父节点，代替直接存储根节点:
   • union操作加快，find操作变慢【最坏: O(1)->O(N)】 2.用rank存储被节点标识的树的深度，实现路径压缩: 让小树合并到大树上【层数不增加】

图(Graph)

基本概念:

1. 子图: 一幅图的所有边的子集(包含这些边依附的顶点)构成的图
2. 路径: 是由边顺序连接的一系列的顶点组成
3. 环: 是一条至少含有一条边且终点和起点相同的路径
4. 连通图: 如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称之为连通图
5. 连通子图: 一个非连通图由若干连通的部分组成，每一个连通的部分都可以称为该图的连通子图

存储结构:

1. 邻接矩阵
2. 邻接表

api设计:

• 类名: Graph
• 构造方法: Graph(int V): 创建一个包含V个顶点但不包含边的图
• 成员方法:
  1. public int V(): 获取图中顶点的数量
  2. public int E(): 获取图中边的数量
  3. public void addEdge(int v, int w): 向图中添加一条边 v-w
  4. public Queue<Integer> adj(int v): 获取和顶点v相邻的所有顶点
• 成员变量:
  1. private final int V: 记录顶点数量
  2. private int E: 记录边数量
  3. private Queue<Integer>[] adj: 邻接表

图的搜索

深度优先搜索(Depth First Search)

定义: 在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找子结点，然后找兄弟结点。【栈】

api设计:

• 类名: DepthFirstSearch
• 构造方法: DepthFirstSearch(Graph G, int s)
• 成员方法:
  1. private void dfs(Graph G, int v): 使用深度优先搜索找出G图中v顶点的所有相通顶点
  2. public boolean marked(int w): 判断w顶点与s顶点是否相通
  3. public int count(): 获取与顶点s相通的所有顶点的总数
• 成员变量:
  1. private boolean[] marked: 索引代表顶点，值表示当前顶点是否已经被搜索
  2. private int count: 记录有多少个顶点与s顶点相通

广度优先搜索(Breadth First Search)

定义: 在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后找子结点。【队列】

• 类名: BreadthFirstSearch
• 构造方法: BreadthFirstSearch(Graph G, int s)
• 成员方法:
  1. private void bfs(Graph G, int v): 使用广度优先搜索找出G图中v顶点的所有相邻顶点
  2. public boolean marked(int w): 判断w顶点与s顶点是否相通
  3. public int count(): 获取与顶点s相通的所有顶点的总数
• 成员变量:
  1. private boolean[] marked: 索引代表顶点，值表示当前顶点是否已经被搜索
  2. private int count: 记录有多少个顶点与s顶点相通
  3. private Queue<Integer> waitSearch: 用来存储待搜索邻接表的点

路径查找

• 类名: DepthFirstPaths
• 构造方法: DepthFirstPaths(Graph G, int s)
• 成员方法:
  1. private void dfs(Graph G, int v): 使用深度优先搜索找出G图中v顶点的所有相邻顶点
  2. public boolean hasPathTo(int v): 判断v顶点与s顶点是否存在路径
  3. public Stack<Integer> pathTo(int v): 找出从起点s到顶点v的路径(就是该路径经过的顶点)
• 成员变量:
  1. private boolean[] marked: 索引代表顶点，值表示当前顶点是否已经被搜索
  2. private int s: 起点
  3. private int[] edgeTo：索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点

有向图

术语:

• 出度
• 入度
• 有向环: 一条至少含有一条边，且起点和终点相同

api设计:

• 类名: Digraph
• 构造方法: Digraph(int V)
• 成员方法:
  1. public int V(): 获取图中顶点的数量
  2. public int E(): 获取图中边的数量
  3. public void addEdge(int v, int w): 向有向图中添加一条边v->w
  4. public Queue<Integer> adj(int v): 获取由v指出的边所连接的所有顶点
  5. private Digraph reverse(): 该图的反向图
• 成员变量:
  1. private final int V: 记录顶点数量
  2. private int E: 记录边数量
  3. private Queue<integer>[] adj: 邻接表

拓扑排序

定义: 给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素。此时就可以明确的表示出每个顶点的优先级。

有向环检测

意义: 要想一个图可以拓扑排序，需要确保它没有环

api设计:

• 类名: DirectedCycle
• 构造方法: DirectedCycle(Digraph G)
• 成员方法:
  1. private void dfs(Digraph G, int v): 基于深度优先搜索，检测图G中是否有环
  2. public boolean hasCycle(): 判断图中是否有环
• 成员变量:
  1. private boolean[] marked: 索引代表顶点，值表示当前顶点是否已经被搜索
  2. private boolean hasCycle: 记录图中是否有环
  3. private boolean[] onStack: 索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上

基于深度优先的顶点排序

api设计:

• 类名: DepthFirstOrder
• 构造方法: DepthFirstOrder(Digraph G)
• 成员方法:
  1. private void dfs(Digraph G,int v): 基于深度优先搜索，生成顶点线性序列
  2. public Stack<Integer> reversePost(): 获取顶点线性序列
• 成员变量
  1. private boolean[] marked: 索引代表顶点，值表示当前顶点是否已经被搜索
  2. private Stack<Integer> reversePost: 使用栈，存储顶点序列

基于顶点排序的拓扑排序

api设计:

• 类名: TopoLogical
• 构造方法: TopoLogical(Digraph G)
• 成员方法
  1. public boolean isCycle(): 判断图G是否有环
  2. public Stack<Integer> order(): 获取拓扑排序的所有顶点
• 成员变量
  1. private Stack<Integer> order: 顶点的拓扑排序

加权无向图

api设计:

• Edge
  • 类名: Edge implements Comparable<Edge>
  • 构造方法: Edge(int v, int w, double weight)
  • 成员方法:
    1. public double weight()：获取边的权重值
    2. public int either(): 获取边上的一个点
    3. public int other(int vertex): 获取边上除了顶点vertex外的另外一个顶点
    4. public int compareTo(Edge that): 比较当前边和参数that边的权重，如果当前边权重大，返回1，如果一样大，返回0，如果当前权重小，返回-1。
  • 成员变量:
    1. private final int v: 顶点一
    2. private final int w: 顶点二
    3. private final double weight: 当前边的权重
• WeightedGraph
  • 类名: WeightedGraph
  • 构造方法: WeightedGraph(int V)
  • 成员方法:
    1. public int V(): 获取图中顶点的数量
    2. public int E(): 获取图中边的数量
    3. public void addEdge(Edge e): 向加权无向图中添加一条边e
    4. public Queue<Edge> adj(int v): 获取和顶点v关联的所有边
    5. public Queue<Edge> edges(): 获取加权无向图的所有边
  • 成员变量:
    1. private final int V: 记录顶点数量
    2. private int E: 记录边数量
    3. private Queue<Edge>[] adj: 邻接表

最小生成树

定义: 图的生成树是它的一棵含有其所有顶点的无环连通子图，一副加权无向图的最小生成树是它的一棵权值(树中所有边的权值之和)最小的生成树。

约定:

1. 只考虑连通图
2. 所有边的权重各不相同

最小生成树定理

树的性质:

1. 用一条边连接树中的任意两个顶点都会产生一个新的环
2. 从树中删除任意一条边，将会得到两棵独立的树

切分定理: 在一副加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图中的最小生成树，但也不一定是所有横切边中唯一属于最小生成树的边。

1. 切分: 将图的所有顶点按照某些规则分为两个非空且没有交集的集合。
2. 横切边: 连接两个术语不同集合的顶点的边称之为横切边。

贪心算法求解

计算图的最小生成树的算法有很多种，但这些算法都可以看做是贪心算法的一种特殊情况，这些算法的不同之处在于保存切分和判定权重最小的横切边的方式。

Prim算法

原理: 把最小生成树中的顶点看做是一个集合，把不在最小生成树中的顶点看做是另外一个集合。它的每一步都会为一棵生成中的树添加一条边。一开始这惈树只有一个顶点，然 后会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的项点且权重最小的边加入到树中。

课程api设计:

• 类名: PrimMST
• 构造方法: PrimMST(WeightedGraph G)
• 成员方法:
  1. private void visit(WeightedGraph G, int v): 将顶点v添加到最小生成树中，并且更新数据
  2. public Queue<Edge> edges(): 获取最小生成树的所有边
• 成员变量
  1. private Edge[] edgeTo: 索引代表顶点，值表示当前顶点和最小生成树之间的最短边
  2. private double[] distTo: 索引代表顶点，值表示当前顶点和最小生成树之问的最短边的权重
  3. private boolean[] marked: 索引代表顶点，如果当前顶点已经在树中，则位为true，否则为false
  4. private IndexMinPriorityQueue<Double> pg: 存放树中顶点与非树中顶点之间的有效横切边的权重

优化后的api设计:

• 类名: PrimMST
• 构造方法: PrimMST(WeightedGraph G)
• 成员方法:
  1. private void visit(WeightedGraph G, int v): 将顶点v添加到最小生成树中，并且更新数据
  2. public Queue<Edge> edges(): 获取最小生成树的所有边
• 成员变量
  1. private Queue<Edge> edges: 最小生成树中的边
  2. private boolean[] marked: 索引代表顶点，如果当前顶点已经在树中，则位为true，否则为false
  3. private IndexMinPriorityQueue<Edge> pg: 存放树中顶点与非树中顶点之间的有效横切边

Kruskal算法

原理: 将图中的每个顶点视为一个独立的单点树，将问题转化为合并树【通过并查集实现】

api设计:

• 类名: KruskalMST
• 构造方法: KruskalMST(WeightedGraph G)
• 成员方法
  1. public Queue<Edge> edges(): 获取最小生成树的所有边
• 成员变量
  1. private Queue<Edge> mst: 保存最小生成树的所有边
  2. private UnionFind uf: 索引代表顶点，使用uf.connect(v, w)可以判断顶点v和顶点w是否在同一颗树中，使用uf.union(v,w)可以把顶点v所在的树和顶点w所在的树合并
  3. private MinPriorityQueue<Edge> pq: 存储图中所有的边，使用最小优先队列，对边按照权重进行排序

加权有向图

api设计:

• DirectedEdge
  • 类名: DirectedEdge
  • 构造方法: DirectedEdge(int v, int w, double weight)
  • 成员方法
    1. public double weight(): 获取边的权重值
    2. public int from(): 获取有向边的起点
    3. public int to(): 获取有向边的终点
  • 成员变量
    1. private final int v: 起点
    2. private final int w: 终点
    3. private final double weight: 当前边的权重
• WeightedDigraph
  • 类名: WeightedDigraph
  • 构造方法: WeightedDigraph(int V)
  • 成员方法:
    1. public int V(): 获取图中顶点的数量
    2. public int E(): 获取图中边的数量
    3. public void addEdge(DirectedEdge e): 向加权有向图中添加一条边e
    4. public Queue<DirectedEdge> adj(int v): 获取由顶点v指出的所有的边
    5. public Queue <DirectedEdge> edges(): 获取加权有向图的所有边
  • 成员变量
    1. private final int V: 记录顶点数量
    2. private int E: 记录边数量
    3. private Queue<DirectedEdge>[] adj: 邻接表

最短路径问题

定义: 在一副加权有向图中，从顶点s到顶点t的最短路径是所有从顶点s到顶点t的路径中总权重最小的那条路径。

最短路径与最小生成树的区别:

• 目标:
  • 最短路径: 寻找两个节点之间的最短路径，即路径上边的权重之和最小。
  • 最小生成树: 寻找一个无环连通子图(生成树)，使得这个子图的边权重之和最小。
• 应用:
  • 最短路径: 常用于导航、网络路由等问题，其中需要找到从一个地点到另一个地点的最优路径。
  • 最小生成树: 常用于网络设计、电路布线等问题，其中需要在连接所有节点的同时保持整体连接成本最小。
• 举例: 一个无向图，里面有三个节点A、B、C；AB权重为2、AC权重为3、BC权重为2；求最小生成树和从A开始的最短路径
  • 最小生成树: AC, BC
  • 最短路径: AC, AB

性质:

1. 路径具有方向性
2. 权重不一定等价于距离。权重可以是距离、时间、花费等内容，权重最小指的是成本最低
3. 只考虑连通图。一副图中并不是所有的顶点都是可达的，如果s和t不可达，那么它们之间也就不存在最短路径，为了简化问题，这里只考虑连通图
4. 最短路径不一定是唯一的。从一个顶点到达另外一个顶点的权重最小的路径可能会有很多条，这里只需要找出一条即可
5. 给定一副加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一副子图，它包含顶点s以及从s可达的所有顶点。这棵有向树的根结点为s，树的每条路径都是有向图中的一条最短路径

常见算法及使用场景:

1. Dijkstra: 从某一点到其他所有点的最短路径【速度快(\(O(E+VlogV)\))，不能处理负权边】
2. Bellman-Ford: 从某一点到其他所有点的最短路径【速度慢(\(O(VE)\))，可以处理负权边】
3. Floyd-Warshall: 任意两点间的最短路径【复杂度为\(O(V^3)\)】

Dijkstra算法

参考视频: 【算法】最短路径查找—Dijkstra算法

松弛技术:

1. 边的松弛
2. 顶点的松弛: 松弛顶点指向的所有边

api设计:

• 类名: DijkstraSP
• 构造方法: public DijkstraSP(WeightedDigraph G, int s)
• 成员方法:
  1. private void relax(WeightedDigraph G, int v): 松弛图G中的顶点v
  2. public double distTo(int v): 获取从顶点s到顶点v的最短路径的总权重
  3. public boolean hasPathTo(int v): 判断从顶点s到顶点v是否可达
  4. public Queue<DirectedEdge> pathTo(int v): 查询从起点s到顶点v的最短路径中所有的边
• 成员变量
  1. private DirectedEdge[] edgeTo: 索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边
  2. private double[] distTo: 索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
  3. private IndexMinPriorityQueue<Double> pq: 存放树中顶点与非树中顶点之间的有效横切边

Bellman-Fords算法

前提: 不存在负权环，但可以检测负权环

思想: 如果一个图没有负权环，从一点到另外一点的最短路径，最多经过所有的V个顶 线，有V-1条边；否则，存在顶点经过了两次，既存在负权环。因此，只需要对图做V-1次松弛，再进行下一次松弛时，如果值不变，说明收敛；如果值继续减少，说明存在负权环。【参考Bellman-Ford Algorithm Explained EASY】

动态规划(Dynamic Programming)

把一个复杂的问题变成相对简单的一些子问题，再利用保存解决 这些子问题得到的结果来减少运算复杂度

基本要件:

1. 最优子问题(正确性): 分而治之(Divide & Conquer)、递归(Recursion)
2. 重叠子问题(有效性)

难点: 从朴素算法(Naive Algorithm)提取子问题

表现形式:

1. 自上而下(备忘录法): 递归 + 记忆中间结果
2. 自下而上(回溯法): 从最后一步的递归开始，反推结果