目 录CONTENT
以下是
yilee
的文章
-
-
-
-
-
-
-
-
-
-
3、数据结构 这篇文章系统介绍了**数据结构**的核心概念与经典实现，主要涵盖以下内容： **动态集合基础**：定义了动态集合的元素结构（关键字、卫星数据、指针属性）以及两大类操作——查询（SEARCH、MINIMUM、MAXIMUM、SUCCESSOR、PREDECESSOR）和修改（INSERT、DELETE）。 **基本数据结构（第10章）**：详细讲解了**栈**（LIFO，PUSH/POP）、**队列**（FIFO，ENQUEUE/DEQUEUE）和**链表**（搜索O(n)、插入O(1)、删除、哨兵简化边界处理）的原理与数组实现。 **散列表（第11章）**：对比直接寻址与散列方式，介绍了除法散列、乘法散列、全域散列三种散列函数，以及链接法和开放寻址法（线性/二次/双重探查）两种冲突解决策略，并简述了O(1)最坏情况查找的完全散列。 **二叉搜索树（第12章）**：阐述BST性质，给出查找、最大/最小值、前驱/后继、插入和删除的算法与Java实现，插入和删除均为O(h)时间复杂度。 **红黑树（第13章）**：定义红黑树的五条性质，通过旋转维护平���；详述插入修复（三种情况）和删除修复（四种情况）的完整流程，保证所有操作在O(lgn)时间内完成，并附Java完整实现。 **数据结构扩张（第14章）**：以红黑树为基础，通过四步法（选基础结构、定附加信息、验证维护、设计新操作）构建**顺序统计树**（支持按秩选取和求秩，O(lgn)）和**区间树**（支持区间重叠查询，O(lgn)）。 **总结**：文章从基础到进阶，层次清晰地覆盖了栈、队列、链表、散列、BST、红黑树及扩张结构，是一份全面的数据结构学习笔记。
