算法与数据结构核心知识点学习笔记

一、二维数组最短路径和（动态规划）

1.1 问题描述

给定一个包含非负整数的二维数组，要求从左上角 (0,0) 走到右下角 (m-1, n-1)，每次只能向下或向右移动一步。目标是找到一条路径，使得路径上的数字总和最小。

示例矩阵：

最优路径： 1 → 3 → 1 → 1 → 1，总和为 7。

1.2 核心思路分析

这是一个经典的**动态规划（Dynamic Programming）**问题。

• 状态定义：dp[i][j] 表示从起点 (0,0) 走到 (i,j) 的最小路径和。

• 状态转移方程：

  由于只能向下或向右走，到达 (i,j) 的前一步只能是 (i-1,j) 或 (i,j-1)。因此：

  dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + arr[i][j]

• 边界条件：

  • 起点：dp[0][0] = arr[0][0]
  • 第一行：只能从左向右走，dp[0][j] = dp[0][j-1] + arr[0][j]
  • 第一列：只能从上向下走，dp[i][0] = dp[i-1][0] + arr[i][0]

1.3 完整代码实现

package cn.wolfcode.test;

public class MinPathNum {
    public static void main(String[] args) {
        int[][] arr = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        System.out.println("最小路径和: " + minPath(arr));
    }

    /**
     * 计算二维数组左上角到右下角的最小路径和
     * @param arr 输入的二维数组
     * @return 最小路径和
     */
    public static int minPath(int[][] arr) {
        if (arr == null || arr.length == 0 || arr[0].length == 0) {
            return 0;
        }

        int m = arr.length;    // 行数
        int n = arr[0].length; // 列数
        
        // 1. 创建 dp 数组
        int[][] dp = new int[m][n];
        
        // 2. 初始化起点
        dp[0][0] = arr[0][0];
        
        // 3. 初始化第一行（只能从左边来）
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + arr[0][j];
        }
        
        // 4. 初始化第一列（只能从上面来）
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + arr[i][0];
        }
        
        // 5. 填充其余位置（取上方或左方的最小值 + 当前值）
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
            }
        }
        
        // 6. 返回右下角的值
        return dp[m - 1][n - 1];
    }
}

1.4 复杂度分析

优化提示：空间可优化至 O(n)，因为当前行只依赖上一行和当前行的左侧值，只需保留一维数组即可。

二、二叉树基础概念

2.1 满二叉树 (Full Binary Tree)

• 定义：如果一棵二叉树的高度为 h，则除第 h 层外，其余各层（1 到 h-1 层）的节点数都达到最大个数，且所有非叶子节点的度均为 2。
• 特征：节点总数 N = 2^h - 1。
• 性质：
  • 第 i 层最多有 2^(i-1) 个节点
  • 树高为 h 时总节点数最多为 2^h - 1

2.2 完全二叉树 (Complete Binary Tree)

• 定义：设二叉树高度为 h，则：
  1. 第 0 层到第 h-1 层必须是满二叉树。
  2. 第 h 层的节点必须从左向右连续排列，中间不能有空缺。
• 应用：堆（Heap）结构通常基于完全二叉树实现，适合用数组存储。
• 节点编号规律：对于编号为 i 的节点，其左孩子为 2i，右孩子为 2i+1，父节点为 ⌊i/2⌋。

2.3 二叉搜索树 (BST)

• 定义：一种特殊的二叉树，满足以下性质：
  1. 若左子树不为空，则左子树上所有节点的值 < 根节点的值。
  2. 若右子树不为空，则右子树上所有节点的值 > 根节点的值。
  3. 左右子树也分别为二叉搜索树。
• 中序遍历：结果是一个升序序列。例如：1 2 3 4 5 6。
• 缺点：在极端情况下（如插入有序数据），会退化为链表，查询复杂度退化为 O(N)。

三、AVL 树（自平衡二叉搜索树）

3.1 核心特性

AVL 树是为了解决 BST 退化问题而提出的严格平衡二叉搜索树。

• 平衡条件：任意节点的左右子树高度差的绝对值不超过 1。
• 优势：查询效率极高，时间复杂度稳定在 O(log N)。
• 劣势：为了维持严格平衡，插入和删除操作需要频繁旋转，增删效率相对较低。
• 中序遍历：结果仍为升序序列，例如：1 2 3 4 5 6。

3.2 删除操作详解

AVL 树删除节点后，需从删除点向上回溯检查平衡因子，必要时进行旋转调整。

四、红黑树 (Red-Black Tree)

4.1 AVL 树 vs 红黑树

4.2 红黑树五大性质

1. 颜色限制：每个节点非红即黑。
2. 根节点：必须是黑色。
3. 叶子节点：NIL 叶子节点必须是黑色。
4. 红红不相邻：任意两个红色节点不能直接相连（父子不能同红）。
5. 黑高一致：从任一节点到其所有叶子节点的路径上，黑色节点数量相同。

补充规则：新插入的节点默认染为红色，以减少对黑高性质的破坏。

4.3 红黑树删除操作规则

删除操作比插入复杂，核心在于处理黑色节点删除导致的黑高不平衡。

1. 物理删除策略

2. 黑色节点修复逻辑

设被删节点为 N，兄弟节点为 S：

情况 A：兄弟节点 S 为红色

• 操作：父节点与 S 变色，对父节点进行旋转（LL/RR），转化为 S 为黑色的情况。

情况 B：兄弟节点 S 为黑色

笔记案例：

• 节点 C 变 A，A 变黑，执行 LL 右旋
• 16黑 15红 9黑，执行左旋
• 旋转类型包括：LL、RR、RL、LR

五、核心知识点总结对照表

六、学习要点归纳

1. 动态规划：二维数组最短路径问题的关键在于正确初始化第一行和第一列，状态转移方程取上方和左方的最小值加当前值。

2. 二叉树三种类型：满二叉树（所有非叶子节点度为2）、完全二叉树（靠左连续）、二叉搜索树（左小右大）。

3. AVL树：严格平衡保证了 O(log N) 的查询效率，但删除操作需要回溯调整，增删效率较低。删除分三种情况：无孩子直接删、单子节点代替、双子节点用前驱/后继代替。

4. 红黑树：弱平衡设计在查询效率和增删效率之间取得平衡，是 Java TreeMap、HashMap 等集合框架的核心数据结构。删除黑色节点时需要复杂的修复逻辑，包括变色和旋转（LL/RR/RL/LR 四种情况）。