知识树
graph LR A[算法与数据结构] A --> B[数据结构] B --> B1[线性结构] B1 --> B1a[数组 Array] B1 --> B1b[链表 Linked List] B1 --> B1c[栈 Stack] B1 --> B1d[队列 Queue] B --> B2[树结构] B2 --> B2a[二叉树 Binary Tree] B2 --> B2b[二叉搜索树 BST] B2 --> B2c[AVL 树] B2 --> B2d[红黑树 Red-Black Tree] B2 --> B2e[B 树 B-Tree] B2 --> B2f[堆 Heap] B2 --> B2g[Trie 前缀树] B --> B3[图结构] B3 --> B3a[有向图 Directed Graph] B3 --> B3b[无向图 Undirected Graph] B3 --> B3c[加权图 Weighted Graph] B --> B4[集合结构] B4 --> B4a[哈希表 Hash Table] B4 --> B4b[集合 Set] B4 --> B4c[位图 Bitmap] B --> B5[其他结构] B5 --> B5a[跳表 Skip List] B5 --> B5b[并查集 Union-Find] B5 --> B5c[线段树 Segment Tree] B5 --> B5d[树状数组 Fenwick Tree] A --> C[算法] C --> C1[排序算法] C1 --> C1a[冒泡排序 Bubble Sort] C1 --> C1b[选择排序 Selection Sort] C1 --> C1c[插入排序 Insertion Sort] C1 --> C1d[快速排序 Quick Sort] C1 --> C1e[归并排序 Merge Sort] C1 --> C1f[堆排序 Heap Sort] C1 --> C1g[计数排序 Counting Sort] C --> C2[搜索算法] C2 --> C2a[线性搜索 Linear Search] C2 --> C2b[二分搜索 Binary Search] C2 --> C2c[深度优先搜索 DFS] C2 --> C2d[广度优先搜索 BFS] C --> C3[图算法] C3 --> C3a[最短路径 Dijkstra/Bellman-Ford] C3 --> C3b[最小生成树 Prim/Kruskal] C3 --> C3c[拓扑排序 Topological Sort] C --> C4[动态规划 DP] C4 --> C4a[背包问题 Knapsack] C4 --> C4b[最长公共子序列 LCS] C4 --> C4c[最长递增子序列 LIS] C --> C5[贪心算法] C5 --> C5a[活动选择 Activity Selection] C5 --> C5b[哈夫曼编码 Huffman Coding] C --> C6[分治算法] C6 --> C6a[归并排序 Merge Sort] C6 --> C6b[快速排序 Quick Sort] C --> C7[数学与计算几何] C7 --> C7a[最大公约数 GCD] C7 --> C7b[快速幂 Fast Power] C7 --> C7c[凸包 Convex Hull] C --> C8[字符串算法] C8 --> C8a[KMP 算法] C8 --> C8b[Rabin-Karp] C8 --> C8c[Manacher] C --> C9[其他算法] C9 --> C9a[随机化算法 Randomized] C9 --> C9b[回溯算法 Backtracking]
数据结构
基础数据结构
数据结构 | 特点 | 操作 | 场景 |
---|---|---|---|
数组 (Array) | 连续内存存储,固定大小,元素类型相同 | 随机访问:O(1) 插入/删除:O(n) |
快速查找 静态数据存储 |
链表 (Linked List) | 非连续内存,动态大小,节点包含数据和指针 类型:单向链表、双向链表、循环链表 |
插入/删除:O(1) 查找:O(n) |
频繁增删的场景(如LRU缓存) |
栈 (Stack) | 后进先出(LIFO),仅允许一端操作 | 入栈(push):O(1) 出栈(pop):O(1) |
函数调用栈 括号匹配 表达式求值 |
队列 (Queue) | 先进先出(FIFO),允许两端操作 变种:双端队列(Deque)、优先队列(Priority Queue) |
入队/出队:O(1)(普通队列) | 任务调度 广度优先搜索(BFS) |
数组
1. 线性查找 (Linear Search)
- 功能描述:在数组中逐个检查元素,找到目标值并返回其索引,若不存在返回 -1。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public int linearSearch(int[] arr, int target) { |
2. 二分查找 (Binary Search)
- 功能描述:在有序数组中通过不断折半查找目标值,返回其索引,若不存在返回 -1。
- 时间复杂度:O(log n)
- Java 代码实现:
1 | public int binarySearch(int[] arr, int target) { |
3. 冒泡排序 (Bubble Sort)
- 功能描述:通过相邻元素两两比较并交换,将较大元素逐步“冒泡”到数组末尾,实现排序。
- 时间复杂度:O(n²)
- Java 代码实现:
1 | public void bubbleSort(int[] arr) { |
4. 快速排序 (Quick Sort)
- 功能描述:选择一个基准值(pivot),将数组分区并递归排序,适用于大多数情况的高效排序算法。
- 时间复杂度:O(n log n) 平均,O(n²) 最坏
- Java 代码实现:
1 | public void quickSort(int[] arr, int low, int high) { |
5. 数组反转 (Reverse Array)
- 功能描述:使用双指针从两端向中间交换元素,将数组顺序反转。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public void reverseArray(int[] arr) { |
6. 查找最大值 (Find Maximum)
- 功能描述:遍历数组,比较每个元素,找出最大值。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public int findMax(int[] arr) { |
7. 删除重复元素 (Remove Duplicates from Sorted Array)
- 功能描述:在有序数组中删除重复元素,返回新长度,原地修改数组。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public int removeDuplicates(int[] arr) { |
8. 旋转数组 (Rotate Array)
- 功能描述:将数组向右旋转 k 个位置,使用三次反转法实现。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public void rotate(int[] arr, int k) { |
9. 两数之和 (Two Sum)
- 功能描述:找到数组中两个元素的索引,其和等于目标值,使用哈希表优化。
- 时间复杂度:O(n)
- Java 代码实现:
1 | import java.util.HashMap; |
10. 归并排序 (Merge Sort)
- 功能描述:使用分治法将数组分成小块,分别排序后合并,稳定且适用于大数据。
- 时间复杂度:O(n log n)
- Java 代码实现:
1 | public void mergeSort(int[] arr, int left, int right) { |
11. 前缀和 (Prefix Sum)
- 功能描述:计算数组的前缀和,用于快速求解子数组和的问题。
- 时间复杂度:O(n) 预处理,O(1) 查询
- Java 代码实现:
1 | public int[] prefixSum(int[] arr) { |
12. 滑动窗口最大值 (Sliding Window Maximum)
- 功能描述:使用双端队列在固定窗口大小 k 内找到每个窗口的最大值。
- 时间复杂度:O(n)
- Java 代码实现:
1 | import java.util.ArrayDeque; |
13. 合并两个有序数组 (Merge Two Sorted Arrays)
- 功能描述:将两个有序数组合并为一个有序数组,原地修改第一个数组。
- 时间复杂度:O(m + n),其中 m 和 n 是两个数组的长度
- Java 代码实现:
1 | public void mergeSortedArrays(int[] nums1, int m, int[] nums2, int n) { |
14. 数组中第 k 大元素 (Kth Largest Element)
- 功能描述:使用快速选择算法(QuickSelect)找到数组中第 k 大的元素。
- 时间复杂度:O(n) 平均,O(n²) 最坏
- Java 代码实现:
1 | public int findKthLargest(int[] arr, int k) { |
15. 数组元素移动零 (Move Zeroes)
- 功能描述:将数组中的所有零移动到末尾,保持非零元素相对顺序。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public void moveZeroes(int[] arr) { |
链表
单链表
定义单链表
1 | class ListNode { |
遍历链表
原理
- 从头节点开始,沿
next
指针依次访问每个节点,直到遇到null
。 - 用于统计长度、查找节点或打印链表。
代码
1 | public class Main { |
复杂度
- 时间复杂度: O(n),n 是链表长度。
- 空间复杂度: O(1),只用一个指针。
反转链表
原理
- 使用三个指针(
prev
、curr
、next
)迭代反转每个节点的next
指针。 - 核心思想:逐步调整指针方向,原地完成反转。
代码
1 | public class Main { |
复杂度
- 时间复杂度: O(n),一次遍历。
- 空间复杂度: O(1),原地操作。
合并两个有序链表
原理
- 类似归并排序的合并过程,比较两个链表的节点值,逐步构建新链表。
- 使用哑节点(dummy node)简化边界处理。
代码
1 | public class Main { |
复杂度
- 时间复杂度: O(n + m),n 和 m 是两个链表长度。
- 空间复杂度: O(1),仅用哑节点,不计输出空间。
检测链表中的环
原理
- 使用快慢指针法(Floyd 判圈算法):
- 慢指针每次走 1 步,快指针每次走 2 步。
- 若有环,快慢指针会在环内相遇;若无环,快指针先到
null
。
代码
1 | public class Main { |
复杂度
- 时间复杂度: O(n),快指针最多跑完环的长度。
- 空间复杂度: O(1),只用两个指针。
删除链表中的节点
原理
- 普通删除: 找到目标节点的前驱,调整指针跳过目标。
- 特殊情况: 如果只给定要删除的节点(无前驱引用),将其值替换为下个节点的值,再删除下个节点。
代码
####### 删除指定值的节点
1 | public class Main { |
####### 只给定节点删除(无前驱)
1 | public class Main { |
复杂度
- 普通删除: O(n) 时间,O(1) 空间。
- 给定节点删除: O(1) 时间,O(1) 空间。
查找中间节点
原理
- 使用快慢指针:快指针走 2 步,慢指针走 1 步,快指针到尾时,慢指针在中间。
代码
1 | public class Main { |
复杂度
- 时间复杂度: O(n)。
- 空间复杂度: O(1)。
双链表
双链表节点定义
1 | class DoublyListNode { |
双链表基本类
1 | class DoublyLinkedList { |
在头部添加节点
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
在尾部添加节点
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
删除指定值的第一个节点
1 | // 时间复杂度: O(n), 空间复杂度: O(1) |
打印链表
1 | // 时间复杂度: O(n), 空间复杂度: O(1) |
反转双链表
1 | // 时间复杂度: O(n), 空间复杂度: O(1) |
查找中间节点
1 | // 时间复杂度: O(n), 空间复杂度: O(1) |
检测循环
1 | // 时间复杂度: O(n), 空间复杂度: O(1) |
合并两个有序双链表
1 | // 时间复杂度: O(n + m), 空间复杂度: O(n + m) |
使用示例
1 | public static void main(String[] args) { |
单向循环链表
- 循环链表的特点是尾节点的 next 指向头节点,形成闭环。
- 这些算法适用于单向循环链表,操作时需要特别注意循环的维护。
- 分割算法假设链表长度为偶数时分成相等两半,奇数时第一部分少一个节点。
1. 循环链表节点定义
1 | class CircularListNode { |
2. 循环链表基本类
1 | class CircularLinkedList { |
3. 在尾部添加节点
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
4. 在头部添加节点
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
5. 删除指定值的第一个节点
1 | // 时间复杂度: O(n), 空间复杂度: O(1) |
6. 打印循环链表
1 | // 时间复杂度: O(n), 空间复杂度: O(1) |
7. 检测循环(验证是否正确形成循环链表)
1 | // 时间复杂度: O(n), 空间复杂度: O(1) |
8. 查找链表长度
1 | // 时间复杂度: O(n), 空间复杂度: O(1) |
9. 分割循环链表为两个循环链表
1 | // 时间复杂度: O(n), 空间复杂度: O(1) |
使用示例
1 | public static void main(String[] args) { |
栈
栈是一种后进先出(LIFO)的数据结构
- 数组实现:适合固定大小的场景,空间利用率高但不灵活。
- 链表实现:动态大小,无需预定义容量,适合不确定大小的场景。
1. 基于数组的栈实现
栈的基本类(数组实现)
1 | class ArrayStack { |
1.1 入栈(push)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
1.2 出栈(pop)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
1.3 查看栈顶元素(peek)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
1.4 判断栈是否为空
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
1.5 判断栈是否已满
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
2. 基于链表的栈实现
栈节点定义
1 | class StackNode { |
栈的基本类(链表实现)
1 | class LinkedStack { |
2.1 入栈(push)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
2.2 出栈(pop)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
2.3 查看栈顶元素(peek)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
2.4 判断栈是否为空
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
3. 栈的常用算法
3.1 反转栈
1 | // 时间复杂度: O(n), 空间复杂度: O(n) |
3.2 检查括号匹配
1 | // 时间复杂度: O(n), 空间复杂度: O(n) |
3.3 计算后缀表达式(逆波兰表达式)
1 | // 时间复杂度: O(n), 空间复杂度: O(n) |
3.4 最小栈(获取栈中最小元素)
1 | // 支持在 O(1) 时间获取最小元素的栈 |
使用示例
1 | public static void main(String[] args) { |
队列
队列是一种先进先出(FIFO)的数据结构
- 数组队列:简单实现,但空间利用率低,出队后空间不可复用。
- 链表队列:动态大小,适合不确定长度的场景。
- 循环队列:优化数组队列,复用空间,适合固定大小场景。
- 双端队列:支持两端操作,灵活性更高。
- 优先队列:基于最小堆实现,保证每次出队的是最小元素。
1. 基于数组的队列实现
队列的基本类(数组实现)
1 | class ArrayQueue { |
1.1 入队(enqueue)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
1.2 出队(dequeue)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
1.3 查看队首元素(peek)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
1.4 判断队列是否为空
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
1.5 判断队列是否已满
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
2. 基于链表的队列实现
队列节点定义
1 | class QueueNode { |
队列的基本类(链表实现)
1 | class LinkedQueue { |
2.1 入队(enqueue)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
2.2 出队(dequeue)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
2.3 查看队首元素(peek)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
2.4 判断队列是否为空
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
3. 队列的常用算法
3.1 循环队列(基于数组优化)
1 | class CircularQueue { |
3.2 双端队列(Deque)
1 | class Deque { |
3.3 优先队列(最小堆实现)
1 | class PriorityQueue { |
使用示例
1 | public static void main(String[] args) { |
树形结构
数据结构 | 特点 | 变种/类型 | 操作 | 场景 |
---|---|---|---|---|
二叉树 (Binary Tree) | 每个节点最多两个子节点 | - 二叉搜索树 (BST):左子树值 < 根 < 右子树值 - 平衡二叉树 (AVL树/红黑树):自动平衡高度 |
查找/插入(BST平均O(log n),平衡树O(log n)) | 快速查找 排序 |
堆 (Heap) | 完全二叉树,父节点与子节点有大小关系 | - 最大堆:父节点≥子节点 - 最小堆:父节点≤子节点 |
插入:O(log n) 取最值:O(1) |
优先队列 堆排序 |
多叉树 | 支持多个子节点的树结构 | - B树/B+树:多路平衡树,减少磁盘I/O - 字典树 (Trie):前缀树,存储字符串集合 |
依赖具体类型(如B树查找O(log n),Trie前缀查询O(m),m为字符串长度) | B树/B+树:数据库索引 Trie:自动补全 |
二叉树
普通二叉树
二叉树节点定义
所有算法基于以下二叉树节点类:
1 | class TreeNode { |
1. 前序遍历 (Preorder Traversal)
- 功能描述:按照“根-左-右”的顺序递归遍历二叉树。
- 时间复杂度:O(n),其中 n 是节点数
- Java 代码实现:
1 | public void preorderTraversal(TreeNode root) { |
2. 中序遍历 (Inorder Traversal)
- 功能描述:按照“左-根-右”的顺序递归遍历二叉树,对于二叉搜索树(BST)会输出有序序列。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public void inorderTraversal(TreeNode root) { |
3. 后序遍历 (Postorder Traversal)
- 功能描述:按照“左-右-根”的顺序递归遍历二叉树,常用于释放节点内存。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public void postorderTraversal(TreeNode root) { |
4. 层序遍历 (Level Order Traversal)
- 功能描述:使用队列按层从上到下、从左到右遍历二叉树。
- 时间复杂度:O(n)
- Java 代码实现:
1 | import java.util.LinkedList; |
5. 计算二叉树深度 (Maximum Depth)
- 功能描述:递归计算二叉树的最大深度(根到最远叶节点的路径长度)。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public int maxDepth(TreeNode root) { |
6. 判断是否平衡二叉树 (Check Balanced Binary Tree)
- 功能描述:检查二叉树是否平衡,即任意节点的左右子树高度差不超过 1。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public boolean isBalanced(TreeNode root) { |
7. 二叉树路径总和 (Path Sum)
- 功能描述:判断是否存在从根到叶节点的路径,其节点值之和等于目标值。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public boolean hasPathSum(TreeNode root, int targetSum) { |
8. 反转二叉树 (Invert Binary Tree)
- 功能描述:将二叉树的左右子树交换,递归反转整棵树。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public TreeNode invertTree(TreeNode root) { |
9. 二叉搜索树验证 (Validate Binary Search Tree)
- 功能描述:验证二叉树是否为二叉搜索树(BST),即左子树值 < 根 < 右子树值。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public boolean isValidBST(TreeNode root) { |
10. 最低公共祖先 (Lowest Common Ancestor)
- 功能描述:在二叉树中找到两个节点的最低公共祖先(LCA)。
- 时间复杂度:O(n)
- Java 代码实现:
1 | public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { |
11. 前序遍历(非递归)(Preorder Traversal - Iterative)
- 功能描述:使用栈模拟递归,按照“根-左-右”的顺序遍历二叉树。
- 时间复杂度:O(n),空间复杂度 O(h),h 为树高
- Java 代码实现:
1 | import java.util.Stack; |
12. 中序遍历(非递归)(Inorder Traversal - Iterative)
- 功能描述:使用栈模拟递归,按照“左-根-右”的顺序遍历二叉树,先将左子树压栈到底。
- 时间复杂度:O(n),空间复杂度 O(h)
- Java 代码实现:
1 | import java.util.Stack; |
13. 后序遍历(非递归)(Postorder Traversal - Iterative)
- 功能描述:使用栈模拟递归,按照“左-右-根”的顺序遍历二叉树,需记录上一次访问的节点以区分回溯路径。
- 时间复杂度:O(n),空间复杂度 O(h)
- Java 代码实现:
1 | import java.util.Stack; |
14. 层序遍历(非递归)(Level Order Traversal - Iterative)
- 功能描述:使用队列按层从上到下、从左到右遍历二叉树(已在之前提供,这里重复列出以保持完整性)。
- 时间复杂度:O(n),空间复杂度 O(w),w 为树的最大宽度
- Java 代码实现:
1 | import java.util.LinkedList; |
二叉搜索树 (Binary Search Tree, BST)
- 定义: 左子树所有节点值 < 根节点值 < 右子树所有节点值。
- 特性: 支持高效的查找、插入和删除,但可能退化为链表。
- 应用场景:
- 数据库索引
- 动态集合管理
- 符号表
结构图
graph TD A[10] --> B[5] A --> C[15] B --> D[3] B --> E[7] C --> F[13]
1. 二叉搜索树节点定义
1 | class BSTNode { |
2. 二叉搜索树基本类
1 | class BinarySearchTree { |
3. 二叉搜索树常用算法
3.1 插入节点
1 | // 时间复杂度: O(h) 其中 h 是树高,平均 O(log n),最坏 O(n) |
3.2 删除节点
1 | // 时间复杂度: O(h) 其中 h 是树高,平均 O(log n),最坏 O(n) |
3.3 查找节点
1 | // 时间复杂度: O(h) 其中 h 是树高,平均 O(log n),最坏 O(n) |
3.4 前序遍历(Preorder Traversal)
1 | // 时间复杂度: O(n) 其中 n 是节点数 |
3.5 中序遍历(Inorder Traversal)
1 | // 时间复杂度: O(n) 其中 n 是节点数 |
3.6 后序遍历(Postorder Traversal)
1 | // 时间复杂度: O(n) 其中 n 是节点数 |
3.7 查找最小值
1 | // 时间复杂度: O(h) 其中 h 是树高,平均 O(log n),最坏 O(n) |
3.8 查找最大值
1 | // 时间复杂度: O(h) 其中 h 是树高,平均 O(log n),最坏 O(n) |
3.9 计算树的高度
1 | // 时间复杂度: O(n) 其中 n 是节点数 |
3.10 验证是否是有效的BST
1 | // 时间复杂度: O(n) 其中 n 是节点数 |
使用示例
1 | public static void main(String[] args) { |
说明
- 时间复杂度:大多数操作依赖树高 h,在平衡 BST 中 h ≈ log n,在退化为链表时 h = n。
- 插入、删除、查找:核心操作,利用 BST 的性质快速定位。
- 遍历:前序、中序、后序是基本的树遍历方式,中序遍历 BST 会得到有序序列。
- 最小值和最大值:利用 BST 左子树最小、右子树最大的特性。
- 高度和验证:辅助功能,用于分析树结构和正确性。
平衡二叉树
AVL树 (自平衡二叉搜索树)
AVL 树通过在插入和删除时保持平衡因子(左右子树高度差不超过 1)来确保树的高度始终接近 log n,从而保证操作的高效性。
- 定义: BST的改进,任何节点的左右子树高度差不超过1。
- 特性: 通过旋转保持平衡,保证O(log n)操作。
- 应用场景:
- 需要频繁查找的实时系统
- 内存管理中的动态分配
AVL 树节点定义
1 | class AVLNode { |
AVL 树基本类
1 | class AVLTree { |
获取节点高度
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
获取平衡因子
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
更新节点高度
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
右旋转(Right Rotation)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
左旋转(Left Rotation)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
插入节点
1 | // 时间复杂度: O(log n), 空间复杂度: O(log n) 递归调用栈 |
删除节点
1 | // 时间复杂度: O(log n), 空间复杂度: O(log n) 递归调用栈 |
查找节点
1 | // 时间复杂度: O(log n), 空间复杂度: O(log n) 递归调用栈 |
中序遍历(Inorder Traversal)
1 | // 时间复杂度: O(n), 空间复杂度: O(log n) 递归调用栈 |
验证 AVL 树性质
1 | // 时间复杂度: O(n), 空间复杂度: O(log n) 递归调用栈 |
使用示例
1 | public static void main(String[] args) { |
说明
- 平衡因子:AVL 树通过平衡因子(左子树高度 - 右子树高度)保持平衡,范围在 [-1, 1]。
- 旋转操作:
- 右旋转:处理左子树过高的情况(左左或左右)。
- 左旋转:处理右子树过高的情况(右右或右左)。
- 时间复杂度:
- 插入、删除、查找为 O(log n),因为 AVL 树始终保持平衡。
- 遍历和验证为 O(n),需要访问所有节点。
- 空间复杂度:
- 递归操作依赖树高 h,由于 AVL 树平衡,h ≈ log n。
- 特点:
- 相比普通 BST,AVL 树通过旋转操作保证了高效性,但增加了维护成本。
红黑树 (Red-Black Tree)
红黑树是一种自平衡二叉搜索树,通过颜色(红/黑)和五条性质保持平衡,确保操作时间复杂度为 O(log n)。
- 定义: 自平衡BST,具有颜色属性(红/黑),遵循特定规则:
- 节点是红色或黑色
- 根节点是黑色
- 红色节点的子节点必须是黑色
- 从根到叶的每条路径黑色节点数相同
- 红黑树性质:
- 每个节点是红色或黑色。
- 根节点是黑色。
- 所有叶子(NIL)是黑色。
- 红色节点的子节点必须是黑色(不能有连续红色节点)。
- 从根到任一叶子的路径上黑色节点数量相同。
- 特性: 保证O(log n)操作,广泛用于系统实现。
- 应用场景:
- Java的TreeMap/TreeSet
- Linux内核调度
- 数据库B+树基础
红黑树节点定义
1 | class RBNode { |
红黑树基本类
1 | class RedBlackTree { |
左旋转(Left Rotation)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
右旋转(Right Rotation)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
插入节点
1 | // 时间复杂度: O(log n), 空间复杂度: O(1) |
删除节点
1 | // 时间复杂度: O(log n), 空间复杂度: O(1) |
查找节点
1 | // 时间复杂度: O(log n), 空间复杂度: O(1) |
中序遍历(Inorder Traversal)
1 | // 时间复杂度: O(n), 空间复杂度: O(log n) 递归调用栈 |
查找最小值
1 | // 时间复杂度: O(log n), 空间复杂度: O(1) |
使用示例
1 | public static void main(String[] args) { |
说明
- 旋转操作:
- 左旋转和右旋转用于调整树结构,保持平衡。
- 插入和删除:
- 插入后通过调整颜色和旋转修复红黑性质。
- 删除后通过四种情况修复,确保黑色高度一致。
- 时间复杂度:
- 插入、删除、查找为 O(log n),因为红黑树高度始终保持在 2log(n+1) 以内。
- 遍历为 O(n)。
- 空间复杂度:
- 大多数操作只需常数额外空间,递归调用栈为 O(log n)。
完全二叉树
完全二叉树是一种特殊的二叉树,所有层(除可能的最底层)都被填满,最底层的节点尽量靠左排列。完全二叉树常用于实现堆。
1. 完全二叉树节点定义
1 | class CBTNode { |
2. 完全二叉树基本类(基于数组实现)
由于完全二叉树可以用数组高效存储(无需显式指针),以下实现主要基于数组形式,适用于堆等场景。如果需要基于链表的实现,可以另行说明。
1 | class CompleteBinaryTree { |
3. 完全二叉树常用算法
3.1 插入节点(尾部插入)
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
3.2 删除最后一个节点
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
3.3 获取父节点索引
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
3.4 获取左子节点索引
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
3.5 获取右子节点索引
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
3.6 检查是否为完全二叉树(基于链表实现)
1 | // 时间复杂度: O(n), 空间复杂度: O(w), w 是树的最大宽度(队列空间) |
3.7 计算树的高度
1 | // 时间复杂度: O(1), 空间复杂度: O(1) |
3.8 层序遍历(Level Order Traversal)
1 | // 时间复杂度: O(n), 空间复杂度: O(w), w 是树的最大宽度 |
3.9 堆化(Heapify)- 最小堆调整
1 | // 时间复杂度: O(log n), 空间复杂度: O(1) |
3.10 构建最小堆
1 | // 时间复杂度: O(n), 空间复杂度: O(1) |
3.11 最大堆化(Max Heapify)
1 | // 时间复杂度: O(log n), 空间复杂度: O(1) |
3.12 构建最大堆
1 | // 时间复杂度: O(n), 空间复杂度: O(1) |
3.13 插入并调整为最大堆
1 | // 时间复杂度: O(log n), 空间复杂度: O(1) |
3.14 删除最大值(根节点)
1 | // 时间复杂度: O(log n), 空间复杂度: O(1) |
使用示例
1 | import java.util.*; |
说明
- 实现方式:
- 主要基于数组实现,因为完全二叉树可以用数组连续存储,适合堆等应用。
- 提供了基于链表的
isCompleteBinaryTree
检查算法,展示树结构的验证。
- 时间复杂度:
- 插入和删除最后一个节点为 O(1),因为只操作数组末尾。
- 堆化操作(如
minHeapify
)为 O(log n),构建堆为 O(n)。 - 遍历和检查为 O(n)。
- 空间复杂度:
- 数组实现大多为 O(1) 额外空间。
- 层序遍历和检查使用队列,空间为 O(w),w 是树的最大宽度。
- 与堆的关系:
- 完全二叉树常用于实现堆(如最小堆、最大堆),因此包含了堆化相关算法。
- 如果不考虑堆序性,完全二叉树仅关注结构完整性。
- 扩展:
- 如果需要最大堆调整、前序/中序遍历等其他算法,可以告诉我,我会补充。
完全二叉树的算法相对简单,主要优势在于其结构特性便于数组存储和高效操作,尤其在堆的实现中应用广泛。
多叉树
多路平衡树
B树
B 树是一种自平衡的多路搜索树,广泛用于数据库和文件系统,能够高效处理大量数据。B 树的每个节点可以有多个键和子节点,保持树的平衡以确保操作时间为 O(log n)。
B 树性质:
- 每个节点最多有 2t-1 个键,最多 2t 个子节点。
- 每个非根节点至少有 t-1 个键,至少 t 个子节点。
- 根节点至少有 1 个键(除非树为空)。
- 所有叶子节点在同一层。
B 树节点定义
1 | class BTreeNode { |
B 树基本类
1 | class BTree { |
搜索键
1 | // 时间复杂度: O(t log_t n), 其中 t 是度数,n 是键总数 |
插入键
1 | // 时间复杂度: O(t log_t n), 空间复杂度: O(t) 递归栈 |
删除键
1 | // 时间复杂度: O(t log_t n), 空间复杂度: O(t) 递归栈 |
遍历(中序遍历)
1 | // 时间复杂度: O(n), 空间复杂度: O(t) 递归栈 |
使用示例
1 | public class Main { |
说明
- 时间复杂度:
- 搜索、插入、删除为 O(t log_t n),其中 t 是度数,n 是键总数。
- 遍历为 O(n)。
- 空间复杂度:
- 每个节点占用 O(t) 空间,递归栈为 O(t)。
- 算法特点:
- 插入:通过分裂满节点保持平衡。
- 删除:通过借用或合并子节点保持最小键数。
- 搜索:利用有序键快速定位。
- 应用:
- B 树适用于磁盘存储系统,因其多路结构减少了 I/O 操作。
- 扩展:
- 如果需要范围查询、最小/最大值等其他算法,可以告诉我,我会补充。
这个实现假设键为整数,t 为固定值。如果需要动态调整 t 或支持其他数据类型,可以进一步修改。有什么具体需求,请告诉我!
B+ 树
B+ 树是 B 树的变种,广泛用于数据库和文件系统,特点是所有键值存储在叶子节点,非叶子节点仅用于索引,且叶子节点通过链表连接,便于范围查询。
B+ 树性质:
- 所有键值存储在叶子节点,非叶子节点仅存储索引。
- 每个节点最多有 2t-1 个键,最多 2t 个子节点。
- 每个非根节点至少有 t-1 个键,至少 t 个子节点。
- 叶子节点通过链表连接。
B+ 树节点定义
1 | class BPlusNode { |
B+ 树基本类
1 | class BPlusTree { |
搜索键
1 | // 时间复杂度: O(t log_t n), 其中 t 是度数,n 是键总数 |
插入键
1 | // 时间复杂度: O(t log_t n), 空间复杂度: O(t) 递归栈 |
删除键
1 | // 时间复杂度: O(t log_t n), 空间复杂度: O(t) 递归栈 |
范围查询
1 | // 时间复杂度: O(t log_t n + k), 其中 k 是范围内的键数 |
遍历(叶子节点顺序遍历)
1 | // 时间复杂度: O(n), 空间复杂度: O(1) |
使用示例
1 | import java.util.*; |
说明
- 时间复杂度:
- 搜索、插入、删除为 O(t log_t n),t 是度数,n 是键总数。
- 范围查询为 O(t log_t n + k),k 是范围内的键数。
- 遍历为 O(n)。
- 空间复杂度:
- 每个节点占用 O(t) 空间,递归栈为 O(t)。
- 范围查询结果占用 O(k) 空间。
- 算法特点:
- 插入:分裂时将中间键提升到父节点,叶子节点保持链表。
- 删除:仅从叶子节点删除,通过借用或合并保持平衡。
- 范围查询:利用叶子节点链表高效实现。
- 与 B 树的区别:
- B+ 树叶子节点存储所有数据,非叶子节点仅用于导航。
- 叶子节点链表支持顺序访问和范围查询。
- 应用:
- 数据库索引(如 MySQL InnoDB),因其支持高效范围查询和顺序访问。
这个实现假设键为整数,t 为固定值。如果需要支持其他数据类型或动态 t,可以进一步修改。有什么具体需求,请告诉我!
Trie (前缀树)
Trie 是一种树形数据结构,特别适合处理字符串的前缀查询和搜索问题。
- 定义: 多叉树,用于存储字符串集合,每个节点代表一个字符。
- 特性: 高效前缀查询,空间换时间。
- 应用场景:
- 自动补全(如搜索引擎)
- 拼写检查
- IP路由表
1. Trie 节点定义
1 | class TrieNode { |
2. Trie 基本类
1 | class Trie { |
3. Trie 常用算法
3.1 插入字符串
1 | // 时间复杂度: O(m), 其中 m 是字符串长度 |
3.2 搜索完整单词
1 | // 时间复杂度: O(m), 其中 m 是单词长度 |
3.3 检查前缀
1 | // 时间复杂度: O(m), 其中 m 是前缀长度 |
3.4 删除字符串
1 | // 时间复杂度: O(m), 其中 m 是字符串长度 |
3.5 查找所有以某前缀开头的单词
1 | // 时间复杂度: O(p + n), 其中 p 是前缀长度,n 是以该前缀开头的单词总数 |
3.6 计算 Trie 中单词总数
1 | // 时间复杂度: O(n), 其中 n 是 Trie 中所有节点数 |
使用示例
1 | import java.util.*; |
说明
- Trie 特点:
- 每个节点表示一个字符,路径表示字符串。
- 适合前缀查询、自动补全等场景。
- 时间复杂度:
- 插入、搜索、检查前缀为 O(m),m 是字符串长度。
- 删除为 O(m),但涉及递归清理。
- 查找前缀单词为 O(p + n),p 是前缀长度,n 是匹配单词数。
- 统计单词为 O(n),n 是所有节点数。
- 空间复杂度:
- 插入可能需要 O(m) 空间来存储新节点。
- 其他操作通常为 O(1) 或 O(h),h 是 Trie 高度。
- 假设:
- 这里假设只处理小写字母(26 个字符)。如果需要支持更多字符(如 ASCII 或 Unicode),可以调整
children
数组大小。
- 这里假设只处理小写字母(26 个字符)。如果需要支持更多字符(如 ASCII 或 Unicode),可以调整
- 扩展:
- 如果需要支持大小写、数字等,可以将
children
改为Map<Character, TrieNode>
。 - 如果需要其他算法(如最长公共前缀、模糊匹配等),可以告诉我,我会补充。
- 如果需要支持大小写、数字等,可以将
哈希结构
数据结构 | 特点 | 冲突解决方法 | 操作 | 场景 |
---|---|---|---|---|
哈希表 (Hash Table) | 键值对存储,通过哈希函数快速定位 | - 链地址法:链表存储冲突元素 - 开放寻址法:探测下一个空位 包括线性探测、二次探测和双重哈希 |
插入:O(1) 删除:O(1) 查找:O(1)(理想情况下) |
缓存(如Redis) 快速去重 |
哈希表是一种基于键值对(Key-Value Pair)的高效数据结构,通过哈希函数将键映射到存储位置,支持快速的插入、查找和删除操作。实现一个简单的哈希表,处理冲突使用链地址法(Separate Chaining)。
哈希表节点定义(链地址法)
1 | class HashNode { |
哈希表基本类
1 | class HashTable { |
插入键值对
1 | // 时间复杂度: 平均 O(1), 最坏 O(n)(冲突严重时) |
查找键值对
1 | // 时间复杂度: 平均 O(1), 最坏 O(n)(冲突严重时) |
删除键值对
1 | // 时间复杂度: 平均 O(1), 最坏 O(n)(冲突严重时) |
检查键是否存在
1 | // 时间复杂度: 平均 O(1), 最坏 O(n)(冲突严重时) |
获取所有键
1 | // 时间复杂度: O(n + m), 其中 n 是键值对数,m 是数组容量 |
调整容量(动态扩容)
1 | // 时间复杂度: O(n), 空间复杂度: O(n) |
使用示例
1 | import java.util.*; |
说明
- 链地址法特点:
- 使用链表处理冲突,适合动态负载。
- 平均时间复杂度为 O(1),但冲突严重时退化为 O(n)。
- 时间复杂度:
- 插入、查找、删除:平均 O(1),最坏 O(n)。
- 获取所有键和扩容:O(n)。
- 空间复杂度:
- 基本操作 O(1),存储所有键值对为 O(n)。
- 扩容时临时需要 O(n) 额外空间。
- 哈希函数:
- 这里使用简单的模运算,可根据需求优化(如乘法散列)。
- 负载因子:
- 当 size/capacity 超过某个阈值(如 0.7),应调用
resize
扩容以保持性能。
- 当 size/capacity 超过某个阈值(如 0.7),应调用
- 应用:
- 哈希表用于键值存储(如 HashMap)、缓存、数据库索引等。
开放寻址法处理冲突
哈希表基本类(开放寻址法通用)
1 | class OpenAddressingHashTable { |
线性探测(Linear Probing)实现
发生冲突时,线性向后查找下一个空位。时间复杂度:平均 O(1),但随着负载因子增加,可能退化为 O(n)。
1 | // 线性探测函数 |
二次探测(Quadratic Probing)实现
冲突时按二次函数(i²)偏移查找。
1 | // 二次探测函数 |
双重哈希(Double Hashing)实现
使用第二个哈希函数确定探测步长。
1 | // 双重哈希探测函数 |
使用示例
1 | public class Main { |
说明
- 负载因子控制:
- 设置
LOAD_FACTOR_THRESHOLD = 0.75
,当 size/capacity ≥ 0.75 时,自动扩容为两倍容量。 - 扩容通过
resize
方法实现,时间复杂度 O(n)。
- 设置
- 冲突处理方法:
- 线性探测:简单,但容易主聚集。
- 二次探测:减少主聚集,但可能次聚集,需确保容量为素数以覆盖所有位置。
- 双重哈希:最优,避免聚集,但需设计合适的第二个哈希函数。
- 时间复杂度:
- 平均 O(1)(负载因子低时),最坏 O(n)(表满或聚集严重)。
- 空间复杂度:
- O(1) 额外空间(不计数组本身),扩容时临时需要 O(n)。
- 优化点:
- 这里使用懒删除(标记删除),避免破坏探测序列。
- 哈希函数简单,可根据实际需求优化(如乘法散列)。
- 二次探测和双重哈希未强制容量为素数,实际应用中建议调整。
图结构
类别 | 内容 | 描述 | 适用场景 |
---|---|---|---|
表示方式 | 邻接矩阵 | 二维数组表示顶点关系,matrix[i][j] 表示边权重或是否存在边 |
适合稠密图(边较多) |
邻接表 | 链表数组表示顶点关系,每个顶点关联一个邻接顶点链表 | 适合稀疏图(边较少) | |
算法场景 | 最短路径 (Dijkstra算法) | 从单一源点计算到所有顶点的最短路径,基于贪心策略 | 网络路由、路径规划 |
最小生成树 (Prim/Kruskal算法) | - Prim:从某顶点扩展生成树 - Kruskal:按边权重排序合并 |
网络设计(如电缆布线) | |
拓扑排序 | 对有向无环图(DAG)排序,输出顶点线性序列 | 任务调度、依赖解析(如编译顺序) |
高级数据结构
数据结构 | 特点 | 操作 | 场景 |
---|---|---|---|
并查集 (Union-Find) | 管理元素分组,支持合并集合和查询所属集合 | 合并(Union):近似O(1) 查找(Find):近似O(1)(路径压缩优化后) |
连通性问题(如社交网络好友关系) |
跳表 (Skip List) | 多层链表结构,利用概率平衡,提升查询效率 | 插入:O(log n) 删除:O(log n) 查找:O(log n) |
Redis有序集合实现 |
布隆过滤器 (Bloom Filter) | 概率型数据结构,判断元素“可能存在”或“一定不存在” | 添加:O(1) 查询:O(1) |
缓存穿透防护 垃圾邮件过滤 |