数据结构与算法复习(持续更新)

数据结构复习备忘!随着复习的进行而持续更新,配套代码仓库:AlgoStudy

Index

Changelog

一、排序

1.1 排序工具

后续具体排序算法实现类的父类,主要目的是引入排序检测函数:构造一个随机大数组,以粗略验证所写排序算法是否正确:

abstract public class SortAlgoBase {
    public SortAlgoBase() {
        check(); // 实例化后即检测输出
    }
    // ... 部分代码略
    abstract protected <E extends Comparable<E>> void sort(E[] arr);

    protected void check() {
        Integer[] test = randomArray(1000, 300);
        sort(test);
        if (isSorted(test) && new HashSet<Integer>(Arrays.asList(test)).equals(new HashSet<Integer>(Arrays.asList(test)))) {
            System.out.print(getName() + " 测试通过,用时:");
            // 测试用时
            Integer[] arr = randomArray(20000, 10000);
            long startTime = System.nanoTime();
            sort(arr);
            long endTime = System.nanoTime();
            double time = (endTime - startTime) / 1000000000.0;
            System.out.println(time + "s");
        } else {
            System.out.println(getName() + " 测试失败");
        }
    }
    // 常用的交换函数
    protected <E> void swap(E[] arr, int i, int j) {
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

1.2 选择排序

思路:遍历数组,从当前位置向后选择最小的元素交换到当前元素位置。

public class SelectionSort extends SortAlgoBase {
    @Override
    protected String getName() {
        return "选择排序";
    }

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; ++i) {
            int minIdx = i;

            for (int j = i + 1; j < arr.length; ++j) {
                if (arr[j].compareTo(arr[minIdx]) < 0)
                    minIdx = j;
            }

            swap(arr, i, minIdx);
        }
    }

    public static void main(String[] args) {
        new SelectionSort().check();
        new SelectionSort().checkOrdered();
    }
}

1.3 插入排序

特点:对于有序数组,复杂度 O(N),而选择排序复杂度稳定为 O(N^2)。

1.3.1 第一版代码

思路: 遍历数组,将前位置元素依次交换移动到合适位置,插入元素。

public class InsertionSort extends SortAlgoBase {
    @Override
    protected String getName() {
        return "选择排序 ver1";
    }

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; ++i) {
            // 把 arr[i] 插入到合适的位置
            for (int j = i; j - 1 >= 0; j--) {
                if (arr[j - 1].compareTo(arr[j]) > 0) {
                    swap(arr, j - 1, j);
                } else {
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        new InsertionSort();
    }
}

1.3.2 优化代码

上一版代码存在的问题:有一定的内存优化的可能,即可以去掉 swap

思路: 遍历数组,挪动腾出当前元素合适的位置,放入。

public class InsertionSort2 extends SortAlgoBase {
    @Override
    protected String getName() {
        return "选择排序 ver2";
    }

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; ++i) {
            // 把 arr[i] 放入到合适的位置
            E p = arr[i];
            int j = i;
            for (; j - 1 >= 0; j--) {
                if (p.compareTo(arr[j-1]) < 0) {
                    arr[j] = arr[j - 1];
                } else {
                    break;
                }
            }
            arr[j] = p;
        }
    }

    public static void main(String[] args) {
        new InsertionSort2();
    }
}

1.4 归并排序

1.4.1 递归实现

思路: 用分治法的思想,类似于二叉树后序遍历的顺序,依次排序左右半区间,然后O(N)时间 merge。

public class MergeSort extends SortAlgoBase {
    @Override
    protected String getName() {
        return "归并排序 递归版本";
    }

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {
        E[] aux = Arrays.copyOfRange(arr, l, r + 1);
        int i = 0;
        int j = mid - l + 1;
        int k = l;
        while (i < mid - l + 1 && j < r + 1 - l) {
            if (aux[i].compareTo(aux[j]) < 0) {
                arr[k++] = aux[i++];
            } else {
                arr[k++] = aux[j++];
            }
        }
        while (i < mid - l + 1) {
            arr[k++] = aux[i++];
        }
        while (j < r + 1 - l) {
            arr[k++] = aux[j++];
        }
    }

    public static void main(String[] args) {
        new MergeSort();
    }
}

1.4.2 算法优化

优化点:

  1. 使用插入排序优化归并排序(n=5,000,000差不多能提升0.3秒)。

  2. merge ,如果 arr[mid]<arr[mid+1]则不需要归并。这样对于有序数组,复杂度降为 O(n)。

  3. 内存上的优化:可以(只开创一次空间temp),然后merge开始时arraycopy一下:

    System.arraycopy(arr, l, temp, l, r-l+1);
    
public class MergeSort2 extends SortAlgoBase {
    @Override
    protected String getName() {
        return "归并排序 递归版本2";
    }

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) return;
        // 优化点1:
//        if (r - l <= 15) {
//            // 使用插入排序
//            return; // 别忘了 return
//        }
        int mid = l + (r - l) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {
        // mid最大也是 (N + N-1) / 2 = N,故 mid + 1 不会越界
        if (arr[mid].compareTo(arr[mid + 1]) <= 0) return; // 优化点2:
        E[] aux = Arrays.copyOfRange(arr, l, r + 1); // [l, r+1)
        int i = 0;
        int j = mid - l + 1;
        int k = l;
        while (i < mid - l + 1 && j < r + 1 - l) {
            if (aux[i].compareTo(aux[j]) < 0) {
                arr[k++] = aux[i++];
            } else {
                arr[k++] = aux[j++];
            }
        }
        while (i < mid - l + 1) {
            arr[k++] = aux[i++];
        }
        while (j < r + 1 - l) {
            arr[k++] = aux[j++];
        }
    }

    public static void main(String[] args) {
        new MergeSort2();
    }
}

1.4.3 迭代实现

即:自底向上归并

public class MergeSort3 extends SortAlgoBase {
    @Override
    protected String getName() {
        return "归并排序 迭代版本";
    }

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        E[] aux = Arrays.copyOf(arr, arr.length);
        final int n = arr.length;

        for (int sz = 1; sz < n; sz += sz) { // sz 每次翻倍
            for (int i = 0; i + sz < n; i += sz + sz) { // i + sz - 1 是中点(左)
                // arr[i, i+sz-1], arr[i+sz, i+2sz-1]
                if (arr[i + sz - 1].compareTo(arr[i + sz]) > 0) { // 之前的优化点
                    merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1), aux);
                }
            }
        }
    }


    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] aux) {
        for (int i = l; i <= r; ++i) {
            aux[i] = arr[i];
        }
        int i = l;
        int j = mid + 1;
        int k = l;
        while (i < mid + 1 && j < r + 1) {
            if (aux[i].compareTo(aux[j]) < 0) {
                arr[k++] = aux[i++];
            } else {
                arr[k++] = aux[j++];
            }
        }
        while (i < mid + 1) {
            arr[k++] = aux[i++];
        }
        while (j < r + 1) {
            arr[k++] = aux[j++];
        }
    }

    public static void main(String[] args) {
        new MergeSort3();
    }
}

1.5 快速排序

思路:用分治法的思想,类似于二叉树前序遍历的顺序,先O(N)时间的partition确定一个pivot的位置,然后排序 pivot 左右区间。

快速排序 partition 的灵魂在于把握循环不变量

1.5.1 第一版:单路非随机算法

public class QickSort extends SortAlgoBase {
    @Override
    protected String getName() {
        return "快速排序 版本一";
    }

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) return;
        int p = partition(arr, l, r);
        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    private <E extends Comparable<E>> int partition(E[] arr, int l, int r) {
        final E v = arr[l];
        // 循环不变量 arr[l+1, j] < v, [j+1, i) >= v
        int j = l;
        for (int i = l + 1; i <= r; ++i) {
            if (arr[i].compareTo(v) < 0) { // i 指向的 < v
                j++; // j 跨越分界点,
                swap(arr, i, j); // 与 i 交换
            }
            // else: >= v, i++ 即可,略
        }
        // 循环结束:arr[l+1, j] < v, [j+1, r] >= v,交换 l 和 j 即可。
        swap(arr, l, j);
        return j;
    }
    public static void main(String[] args) {
        new QickSort();
    }
}

1.5.2 第二版:引入随机化,随机算法

上一版本存在的问题:完全有序的数组排序时间复杂度是 O(n^2)

解决:引入随机化,即每次随机选取一个位置的值为 pivot,避免分治“链表化”。

简单引入随机即可。

private static Random rnd = new Random();

private <E extends Comparable<E>> int partition(E[] arr, int l, int r) {
    int rand = rnd.nextInt(r - l + 1) + l;
    swap(arr, l, rand);
    // ...

1.5.3 第三版:双路快速排序

上一版本存在的问题:全等的数组排序时间复杂度是 O(n^2)

解决:双路快速排序,使得全等的情况,pivot集中在中间

使用双指针,更改循环不变量即可:

private <E extends Comparable<E>> int partition(E[] arr, int l, int r) {
    int rand = rnd.nextInt(r - l + 1) + l;
    swap(arr, l, rand);
    final E v = arr[l];
    // 循环不变量:arr[l+1, i) <= 0, arr(j, r] >= 0
    int i = l + 1, j = r;
    for (; ; ) {
        while (i <= j && arr[i].compareTo(v) < 0) i++;
        while (i <= j && arr[j].compareTo(v) > 0) j--;
        if (i >= j) break; // i = j,说明 arr[i] = v;
        swap(arr, i, j);
        i++;
        j--;
    }
    // 如果i,j不等,一定是 i 超过了 j,且 [j]<v, [i] >= v 所以要和 j 交换。
    swap(arr, l, j);
    return j;
}

1.5.4 第四版:三路快速排序

上一版本存在的问题:全等的数组时,相等的区间可以不用处理。即相等的区间可以在下次分区的时候排除。

解决:三路快速排序,区间划分成三部分。

使用三指针,更改循环不变量即可:

private <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
    if (l >= r) return;
    int p = rnd.nextInt(r - l + 1) + l;
    swap(arr, l, p);

    // 循环不变量 arr[l+1, lt] < v, arr[lt+1, i) = v, arr[gt, r] > v
    final E v = arr[l];
    int lt = l, i = l + 1, gt = r + 1;
    while (i < gt) {
        E cur = arr[i];
        if (cur.compareTo(v) < 0) {
            lt++;
            swap(arr, i, lt);
            i++;
        } else if (cur.compareTo(v) > 0) {
            gt--;
            swap(arr, i, gt);
            // i 此时指向未处理元素,不用++
        } else {
            i++;
        }
    }
    swap(arr, l, lt);
    // 此时: arr[l+1, lt-1] < v, arr[lt, gt-1] = v, arr[gt, r] > v
    sort(arr, l, lt - 1);
    sort(arr, gt, r);
}

1.6 堆排序

思路:就地建立最大二叉堆,然后从尾部依次添加最大值,每次拿到最大值后调整维持堆结构。

@Override
public <E extends Comparable<E>> void sort(E[] arr) {
    final int n = arr.length;

    // 就地建立二叉堆:升序排序->最大堆,降序排序->最小堆
    // k 初始为最后一个叶子节点的父节点
    for (int k = (n - 1 - 1) / 2; k >= 0; k--) {
        sink(arr, k, n);
    }


    // 排序
    int k = n - 1;
    while (k > 0) {
        swap(arr, 0, k--);
        sink(arr, 0, k);
    }
}

private void sink(Comparable[] pq, int k, int n) {
    while (2 * k + 1 < n) { // 左节点未越界
        int j = 2 * k + 1;
        if (j + 1 < n && pq[j].compareTo(pq[j + 1]) < 0) j++;
        if (pq[j].compareTo(pq[k]) <= 0) break;
        swap(pq, k, j);
        k = j;
    }
}

1.7 冒泡排序

1.7.1 第一版代码

思路:不断遍历数组,每次确定一个当前未确定的最大值的位置。

@Override
public <E extends Comparable<E>> void sort(E[] arr) {
    final int N = arr.length;
    for (int i = 0; i < N; ++i) {
        boolean isSwapped = false; // 小优化
        // 循环不变量:arr[n-i, n) 已经排序,在 n-i-1 上摆放合适的元素
        for (int j = 1; j < N - i; ++j) {
            if (arr[j-1].compareTo(arr[j]) > 0) {
                isSwapped = true;
                swap(arr, j - 1, j);
            }
        }
        if (!isSwapped) return;
    }
}

1.7.2 优化

优化思路:记录最后一次交换的位置last, 则下一次循环时,[last, N)实际上已经有序了,i 可以跳跃而不用只加一。

@Override
public <E extends Comparable<E>> void sort(E[] arr) {
    final int N = arr.length;
    for (int i = 0; i < N; ++i) {
        int last = 0;
        // arr[n-i, n) 已经排序,在 n-i-1 上摆放合适的元素
        for (int j = 1; j < N - i; ++j) {
            if (arr[j - 1].compareTo(arr[j]) > 0) {
                last = j; // [j, n) 为最终位置
                swap(arr, j - 1, j);
            }
        }
        // [j, n) 为最终位置 arr[n-i, n) 已经排序, i+1 = n-j, 不过还要考虑最后的 i++
        // 或者 i 等于多少元素已经排好序了,故下一个循环开始时,i = len([last, N)) = N - last;
        i = N - last - 1;
    }
}

1.8 希尔排序

1.8.1 希尔排序的思想

思想:让数组变得越来越有序,利用插入排序在近乎有序的数组下比较高效的特点。注意冒泡排序每次操作也可以让数组更加有序,但缺点是只处理相邻逆序对,若此时一个非常大的数在数组靠前的位置或者一个非常小的元素在数组靠后的位置,就只能一步步挪动。希尔排序给了这些家伙一定程度跃迁的机会。

  1. 对元素间距为 n/2 的所有数组做插入排序。
  2. 对元素间距为 n/4 的所有数组做插入排序。
  3. 对元素间距为 n/8 的所有数组做插入排序 ... ...

在数据规模中等的时候,希尔排序法有着优异的性能,远快于其他N^2的算法,甚至能快于NlogN。并且有些场合比如嵌入式,编程环境不支持递归或者递归实现复杂度高,这时就可以使用希尔排序。

时间复杂度,小学数学能求出一个比较松的上界: O(N^2 - N^2/(2^logn) = O(N^2)

1.8.2 四重循环实现

@Override
public <E extends Comparable<E>> void sort(E[] arr) {
   int h = arr.length / 2;
   while (h >= 1) {
       // start: 每一个数组起始时的位置索引
       for (int start = 0; start < h; start++) {
           // 对 data[start, start+h, start+2h, ...] 进行插入排序
           for (int i = start + h; i < arr.length; i += h) {
               E t = arr[i];
               int j;
               for (j = i; j - h >= 0 && arr[j - h].compareTo(t) > 0; j -= h) {
                   arr[j] = arr[j - h];
               }
               arr[j] = t;
           }
       }
       h /= 2;
   }
}

1.8.3 三重循环实现

实际上,遍历初始位置索引的循环实际上并不需要。

实现非常简单,直接去掉那个循环就好了,其他逻辑不变。

@Override
public <E extends Comparable<E>> void sort(E[] arr) {
    int h = arr.length / 2;
    while (h >= 1) {
        for (int i = h; i < arr.length; i += h) {
            E t = arr[i];
            int j;
            for (j = i; j - h >= 0 && arr[j - h].compareTo(t) > 0; j -= h) {
                arr[j] = arr[j - h];
            }
            arr[j] = t;
        }
        h /= 2;
    }
}

1.8.4 步长序列

希尔排序的步长序列的选取时该算法的一个超参数,不同的选取会导致不同的复杂度(紧上界)。

如 h=3*h+1:

@Override
public <E extends Comparable<E>> void sort(E[] arr) {
    int h = 1;
    while (h < arr.length) h = h * 3 + 1;
    while (h >= 1) {
        for (int i = h; i < arr.length; i += h) {
            E t = arr[i];
            int j;
            for (j = i; j - h >= 0 && arr[j - h].compareTo(t) > 0; j -= h) {
                arr[j] = arr[j - h];
            }
            arr[j] = t;
        }
        h /= 3;
    }
}

更多步长的选择和动机可以参考这篇博客(英文)

1.9 排序算法总结

1.9.1 复杂度分析

image-20220321094450515

1.9.2 稳定性分析

排序的稳定性:排序前相等的两个元素,排序后相对位置不变。

稳定的:

不稳定的:

二、二分查找

2.1 常规

递归写法:

public static <E extends Comparable<E>> int search(E[] data, E target) {
    return search(data, target, 0, data.length - 1);
}

// [l, r]
public static <E extends Comparable<E>> int search(E[] data, E target, int l, int r) {
    if (l > r) return -1;
    int mid = l + (r - l) / 2;
    if (data[mid].compareTo(target) == 0)
        return mid;
    if (data[mid].compareTo(target) < 0)
        return search(data, target, mid + 1, r);
    return search(data, target, l, mid - 1);
}

迭代写法:

public static <E extends Comparable<E>> int search(E[] data, E target) {

    int l = 0, r = data.length - 1; 

    while (l <= r) { // 搜索范围:[l, r]
        int mid = l + (r - l) / 2;
        if(data[mid].compareTo(target) == 0)
            return mid;
        if(data[mid].compareTo(target) < 0)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return -1;
}

public static <E extends Comparable<E>> int search(E[] data, E target) {

    int lo = 0, hi = data.length; // 搜索空间

    while (lo <= hi) { // 搜索范围:[l, r]
        int mid = lo + (hi - lo) / 2;
        if(data[mid].compareTo(target) == 0)
            return mid;
        if(data[mid].compareTo(target) < 0)
            lo = mid + 1;
        else
            hi = mid;
    }
    return -1;
}

2.2 Ceil 上界

2.2.1 ceil

即:大于 target 的最小值,如大于60分的最小值。

public static <E extends Comparable<E>> int upper(E[] data, E target) {

    int l = 0, r = data.length; // 搜索空间:[0, n],需要+1

    // data[l, r]
    while (l < r) { // 小于号原因:一定有解,且 l=r 时得到解
        int mid = l + (r - l) / 2;
        if(data[mid].compareTo(target) <= 0) // [l, mid] 一定不满足,可以排除
            l = mid + 1;
        else
            r = mid; // 不能排除 mid,因为 mid 可能是解,进一步求最小
    }
    return l;
}

2.2.2 upper_ceil

Ceil: 天花板,向上取整

即:

  1. 如果数组中存在元素,返回最大索引;
  2. 数组中不存在元素,返回 ceil。
public static <E extends Comparable<E>> int upperCeil(E[] data, E target) {
    int upper = upper(data, target);
    if (upper-1 >= 0 && data[upper - 1].compareTo(target) == 0) {
        return upper - 1;
    }
    return upper;
}

2.2.3 lower_ceil

即:

  1. 如果数组中存在元素,返回最小索引;
  2. 数组中不存在元素,返回 ceil。

>= target 的最小索引

修改 upper 函数,改变(1)处的符号即可:

public static <E extends Comparable<E>> int lowerCeil(E[] data, E target) {

    int l = 0, r = data.length; // 搜索空间:[0, n],需要+1

    // data[l, r]
    while (l < r) { // 小于号原因:一定有解,且 l=r 时得到解
        int mid = l + (r - l) / 2;
        if(data[mid].compareTo(target) < 0) // (1) [l, mid] 一定不满足,可以排除
            l = mid + 1;
        else
            r = mid; // 不能排除 mid,因为 mid 可能是解,进一步求最小
    }
    return l;
}

2.3 Floor 下界

2.3.1 floor

即:小于 target 的最大值,如没及格的最高分。

public static <E extends Comparable<E>> int floor(E[] data, E target) {

    int l = -1, r = data.length - 1; // 搜索空间:[-1, n-1]

    // data[l, r]
    while (l < r) { // 一定有解,且 l=r 时得到解
        int mid = l + (r - l + 1) / 2; // 注意:+0.5 避免**相邻**的时候出现死循环
        if (data[mid].compareTo(target) < 0)
            l = mid; // 不能排除 mid,因为 mid 可能是解
        else
            r = mid - 1;
    }
    return l;
}

2.3.2 lower_floor

即:

  1. 如果数组中存在元素,返回最小索引;
  2. 数组中不存在元素,返回 floor。
public static <E extends Comparable<E>> int lowerFloor(E[] data, E target) {
    int floor = floor(data, target);
    if (floor+1 < data.length && data[floor+1].compareTo(target) == 0) {
        return floor+1;
    }
    return floor;
}

2.3.3 upper_floor

即:小于等于 target 的最大值

public static <E extends Comparable<E>> int upperFloor(E[] data, E target) {

    int l = -1, r = data.length - 1; // 搜索空间:[-1, n-1]

    // data[l, r]
    while (l < r) { // 一定有解,且 l=r 时得到解
        int mid = l + (r - l + 1) / 2; // 注意:+0.5 避免**相邻**的时候出现死循环
        if (data[mid].compareTo(target) <= 0)
            l = mid; // 不能排除 mid,因为 mid 可能是解
        else
            r = mid - 1;
    }
    return l;
}

三、树

3.1 二叉树

二叉树节点类型如下:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

构造二叉树的工具类(即ACM模式构造树,-1代表空)

public class TreeUtils {
    private TreeUtils() {
        throw new AssertionError("No instances");
    }
    public static TreeNode constuctTree(int... arr) {
        TreeNode[] nodes = new TreeNode[arr.length];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                nodes[i] = null;
            } else {
                nodes[i] = new TreeNode(arr[i]);
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (nodes[i] == null) continue;
            if (2 * i + 1 < arr.length) {
                nodes[i].left = nodes[2 * i + 1];
            }
            if (2 * i + 2 < arr.length) {
                nodes[i].right = nodes[2 * i + 2];
            }
        }
        return nodes[0];
    }
}

3.1.1 二叉树遍历,递归

递归思路比较自然,直接给出代码。

前序:

public static List<Integer> preOrder(TreeNode node) {
    List<Integer> res = new ArrayList<>();
    preOrder(node, res);
    return res;
}

public static void preOrder(TreeNode node, List<Integer> res) {
    if (node == null) return;
    res.add(node.val);
    preOrder(node.left, res);
    preOrder(node.right, res);
}

中序:

public static List<Integer> inOrder(TreeNode node) {
    List<Integer> res = new ArrayList<>();
    inOrder(node, res);
    return res;
}

public static void inOrder(TreeNode node, List<Integer> res) {
    if (node == null) return;
    inOrder(node.left, res);
    res.add(node.val);
    inOrder(node.right, res);
}

后序:

public static List<Integer> postOrder(TreeNode node) {
    List<Integer> res = new ArrayList<>();
    postOrder(node, res);
    return res;
}

public static void postOrder(TreeNode node, List<Integer> res) {
    if (node == null) return;
    postOrder(node.left, res);
    postOrder(node.right, res);
    res.add(node.val);
}

前序模拟后续

public static List<Integer> postOrder2(TreeNode node) {
    List<Integer> res = new ArrayList<>();
    postOrder2(node, res);
    Collections.reverse(res);
    return res;
}

public static void postOrder2(TreeNode node, List<Integer> res) {
    if (node == null) return;
    res.add(node.val);
    postOrder2(node.right, res);
    postOrder2(node.left, res);
}

3.1.2 二叉树遍历,迭代

前序:

public static List<Integer> preOrder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (!stack.isEmpty() || node != null) {
        while (node != null) {
            res.add(node.val);
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        node = node.right;
    }
    return res;
}

中序:

public static List<Integer> inOrder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (!stack.isEmpty() || node != null) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        res.add(node.val);
        node = node.right;
    }
    return res;
}

后序:

public static List<Integer> postOrder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root, prev = null;
    while (!stack.isEmpty() || node != null) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        if (node.right == null || node.right == prev) {
            res.add(node.val);
            prev = node;
            node = null;
        } else {
            stack.push(node);
            node = node.right;
        }

    }
    return res;
}

可以修改前序代码实现后续:

public static List<Integer> postOrder2(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (!stack.isEmpty() || node != null) {
        while (node != null) {
            res.add(node.val);
            stack.push(node);
            node = node.right;
        }
        node = stack.pop();
        node = node.left;
    }
    Collections.reverse(res);
    return res;
}

3.1.2 二叉树遍历,迭代器

利用迭代法,可以方便的实现二叉树的迭代器。

观察到迭代法的形式形如:

<初始化>;
while (hasNext()) {
    getNext();
}

所以只需要对应的做好拆分就行了,以一道leetcode为例,要求写一个中序遍历迭代器。173. 二叉搜索树迭代器

class BSTIterator {

    private TreeNode cur;
    private Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        cur = root;
        stack = new ArrayDeque<>();
    }
    
    public int next() {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        int res = cur.val;
        cur = cur.right;
        return res;
    }
    
    public boolean hasNext() {
        return !(stack.isEmpty() && cur == null);
    }
}

3.2 二叉搜索树

3.3 红黑树

本小节主要整理红黑树性质相关的问题。红黑树手撕代码不符合人体工程学,略。

3.3.1 红黑树的基本概念

2-3 树:

  1. 节点分为 2 节点和 3 节点。

  2. 是绝对平衡的。

  3. 添加节点不会添加到空节点,而是总和已有节点合并。

  4. 由合并产生的 4 节点需要分解。

  5. 2-3 树与左倾红黑树一一对应 :

    image-20220318100447715

红黑树的性质:

  1. 节点或者是红色的,或者是黑色的。
  2. 根节点和空节点是黑色的。
  3. 不存在连续的红节点。
  4. 从任意节点到达叶子节点,经过的黑色节点是一样的。

红黑树的特点:

  1. 红黑树是保持“黑平衡”的二叉树。
  2. 严格意义上,不是平衡二叉树。
  3. 最大高度 2logn = O(logn)。

红黑树的性能总结:

  1. 对于完全随机的数据,普通二分搜索足够好用。
  2. 但对于极端情况下,普通二分搜索树回退化为链表。
  3. 对于查询较多的情况,AVL比较好。
  4. 红黑树牺牲了平衡性(2logn的高度),但统计性能更优(综合CURD的所有操作)。

3.3.2 红黑树的添加元素

添加元素

image-20220318102541529

  1. 维护的时机:和AVL树一样
  2. 添加节点后回溯向上维护

递归写法:

public void add (K key, V value) {
    root = add(root, key, value);
    root.color = BLACK; // 保持根节点为黑
}

private void add(Node node, K key, V value) {
    if (node == null) {
        size++;
        return new Node(key, value); // 默认插入红色节点
    }
    if (key.compareTo(node.key) < 0) node.left = add(node.left, key, value);
    else if (key.compareTo(node.key) > 0) node.right = add(node.right, key, value);
    else node.value = value;
    
    // 性质的维护
    if (isRed(node.right) && !isRed(node.left)) node = leftRotate(node);
    if (isRed(node.left) && isRed(node.left.left)) node = rightRotate(node);
    if (isRed(node.left) && isRed(node.right)) flipColors(node);
}
保持根节点为黑
public void add (K key, V value) {
    root = add(root, key, value);
    root.color = BLACK; // 保持根节点为黑
}
左旋转

新添加42,需要变换为左倾

image-20220318103847911

image-20220318103859809

private Node leftRotate(Node node) {
    Node x = node.right;
    
    node.right = x.left;
    x.left = node;
    
    x.color = node.color;
    node.color = RED;
    return x;
}
颜色翻转

新添加 66:

image-20220318104115611

对应于如下2-3树变换:

image-20220318104237674

故三个节点都应该是黑色,但注意此时还要继续向上回溯调整树,因此42需要染成红色(染成红色意味着与根结点合并!)

整体来看就是翻转了一下三个节点的颜色:

private void flipColors(Node node) {
    node.color = RED;
    node.left.color = BLACK;
    node.right.color = BLACK;
}
右旋转

插入12:

image-20220318104550284

注意42要变成红色对应于2-3树的4节点情况:

对应于右旋转x:

image-20220318104744328

添加逻辑里后续可以接着进行颜色翻转:

image-20220318104757369

private Node rightRotate(Node node) {
    Node x = node.left;
    node.left = x.right;
    x.right = node;
    x.color = node.color;
    node.color = RED;
    return x;
}

3.3.3 红黑树的删除元素

TODO..

3.4 线段树

类定义:

public class SegmentTree<E> {
    private E[] tree;
    private E[] data;
    private Merger<E> merger;

    public SegmentTree(E[] arr, Merger<E> merger) {
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; ++i) data[i] = arr[i];

        tree = (E[]) new Object[4 * arr.length];
        this.merger = merger;
        buildTree(0, 0, data.length - 1);
    }

    public int size() {
        return data.length;
    }

    public E get(int index) {
        if (index < 0 || index > data.length) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        return data[index];
    }

    private int leftChild(int index) {
        return 2 * index + 1;
    }

    private int rightChild(int index) {
        return 2 * index + 2;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append('[');
        for (int i = 0; i < tree.length; i++) {
            if (tree[i] != null)
                res.append(tree[i]);
            else
                res.append("null");
            if (i != tree.length - 1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }
}

interface Merger<E> {
    E merge(E a, E b);
}

构建线段树:

递归的构建,然后将左右子树的值 merge 存入当前节点。

// buildTree(0, 0, data.length - 1);
// [l .. r]
private void buildTree(int treeIndex, int l, int r) {
    if (l == r) {
        tree[treeIndex] = data[l];
        return;
    }
    int leftTreeIndex = leftChild(treeIndex);
    int rightTreeIndex = rightChild(treeIndex);

    int mid = l + (r - l) / 2;
    buildTree(leftTreeIndex, l, mid);
    buildTree(rightTreeIndex, mid + 1, r);
    tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}

区间查询:

递归的查询。

// [queryL, queryR]
public E query(int queryL, int queryR) {
    if (queryL < 0 || queryL > data.length || queryR < 0 || queryR > data.length
        || queryL > queryR) {
        throw new IllegalArgumentException("Index is illegal.");
    }
    return query(0, 0, data.length - 1, queryL, queryR);
}
// int treeIndex, int l, int r 这三个信息其实是某个节点的信息,可以封装一下
public E query(int treeIndex, int l, int r, int queryL, int queryR) {
    if(l==queryL && r==queryR) return tree[treeIndex];
    int mid = l + (r - l) / 2;
    int leftTreeIndex = leftChild(treeIndex);
    int rightTreeIndex = rightChild(treeIndex);

    if (queryL >= mid + 1) return query(rightTreeIndex, mid + 1, r, queryL, queryR);
    else if (queryR <= mid) return query(leftTreeIndex, l, mid, queryL, queryR);
    return merger.merge(query(leftTreeIndex, l, mid, queryL, mid),
                        query(rightTreeIndex, mid + 1, r, mid+1, queryR));
}

更新操作:

public void set(int index, E e) {
    if (index < 0 || index > data.length) {
        throw new IllegalArgumentException("Index is illegal.");
    }
    data[index] = e;
    set(0, 0, data.length - 1, index, e);
}

public void set(int treeIndex, int l, int r, int index, E e) {

    if (l == r) {
        tree[treeIndex] = e;
        return;
    }
    int mid = l + (r - l) / 2;
    int leftTreeIndex = leftChild(treeIndex);
    int rightTreeIndex = rightChild(treeIndex);
    if (index >= mid + 1)
        set(rightTreeIndex, mid + 1, r, index, e);
    else
        set(leftTreeIndex, l, mid, index, e);
    tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}

测试一下:

public static void main(String[] args) {
    Integer[] nums = {-2, 0, 3, -5, 2, -1};
    SegmentTree<Integer> segmentTree = new SegmentTree<>(nums, Integer::sum);
    System.out.println(segmentTree);
    System.out.println(segmentTree.query(0, 2));
    System.out.println(segmentTree.query(2, 5));
    System.out.println(segmentTree.query(0, 5));

}

四、其他数据结构

4.1 二叉堆

用二叉堆可以方便的实现优先级队列。

public class MaxPQ<E extends Comparable<E>> {
    private E[] pq;
    private int N;
    public MaxPQ(int cap) {pq = (E[]) new Comparable[cap];}
    public int size() {return N;}
    public boolean isEmpty() {return N == 0;}
    private void swap(int i, int j) {E t = pq[i];pq[i] = pq[j];pq[j] = t;}

    public void insert(E e) {
        pq[N++] = e;
        swim(N-1);
    }

    public E delMax() {
        E res = pq[0];
        swap(0, N - 1);
        pq[N - 1] = null;
        N--;
        sink(0);
        return res;
    }

    private void swim(int k) {
        while (k > 0 && pq[k].compareTo(pq[(k - 1) / 2]) > 0) {
            int p = (k - 1) / 2;
            swap(k, p);
            k = p;
        }
    }

    private void sink(int k) {
        while (2 * k + 1 < N) {
            int j = 2 * k + 1;
            if (j + 1 < N && pq[j + 1].compareTo(pq[j]) > 0) {
                j++;
            }
            if (pq[k].compareTo(pq[j]) >= 0) break;
            swap(k, j);
            k = j;
        }
    }
}

附、Java 算法常用工具函数

A.1 数组类

A.2 集合类

A.3 其他