本章来介绍一些基础的数据结构。 抽象数据类型与数据结构抽象数据类型 (Abstract Data Type, ADT) 与 数据结构 (Data Structure) 本质上是两码事。抽象数据类型的角度较为宏观，例如“存在一个栈，允许我往里压入元素，...

在上个章节我们了解到，在一个数组中作搜索通常效率感人。如果在一个未排序的数组里做搜索，则时间复杂度为$O(n)$。排序过的数组还好点，可以用二分搜索达成$O(\log(n))$的时间复杂度。 那么哈希与哈希表就是实现更高效增删改查操作的一次尝试。...

树(Tree)数据结构是我们继续学习进阶数据结构的基石。 树首先我们先介绍通用树 (General Trees)，这种树的每个节点可以拥有任意数量的子节点。这种结构常见于文件系统。 那么树这样的数据结构有什么要求吗？ 一个树里面包含这些内...

我们已经在第五章介绍了树。这一章我们将目光聚集到二叉搜索树上。 还记得二分搜索的缺点嘛？二分搜索需要在一个排好序的数组上才能使用，而且正如我们之前所说，二分搜索在这种情况下适用于静态数据的搜索，因为一旦我们需要在数组里添加或删除元素，你需要花费$...

还记得如果我们将数据按顺序插入BST会出现什么问题吗？我们的结果会变成一个链表，所有操作退化为 $O(n)$。 本章我们引入平衡树——这些树会在插入或删除过程中自动调整结构，强制保持平衡，从而保证操作复杂度始终是 $O(\log n)$。 AVL ...