数据结构详解

每个程序都要把数据存放在某处,而存放的方式决定了什么快、什么慢。一份一百万个名字的名单,可以一个一个地查,也可以整理成只需二十次比较就能找到任何名字的样子。数据结构就是这些整理方式:寥寥几个想法,大多比个人电脑还要古老,却存在于每一个数据库、操作系统、浏览器和游戏之中。

一棵红黑着色的二叉搜索树、一摞方块组成的栈、一排哈希桶及其中一串冲突的键,以及连接链表节点的箭头
一棵红黑着色的二叉搜索树、一摞方块组成的栈、一排哈希桶及其中一串冲突的键,以及连接链表节点的箭头

数据结构有什么用

选择数据结构,要看它需要回答哪些问题。手机的通话记录要先给出最近的一通电话,打印机的任务要先处理最早的那个,词典要在十万个词中找出一个词的意思,路线规划要找出最近的未访问路口。每种结构都通过放弃一些操作的速度来换取另一些操作的速度,而大 O 记号描述了这种取舍:O(1) 表示时间不随元素个数 n 增长,O(log n) 表示 n 翻倍只多一步,O(n) 表示时间与 n 成正比增长。

栈、队列和双端队列

栈在同一端添加和删除:后进先出。撤销历史、返回按钮以及正在运行的程序的函数调用都是栈。队列在队尾添加、在队首删除:先进先出,就像键盘输入或打印队列。双端队列允许在两端做这两件事。三者每个操作都只需常数时间。队列常常存放在环形缓冲区中,这是一个固定数组,队首和队尾越过最后一个位置后会绕回开头;满了以后,元素会被复制到大一倍的数组。复制要花 O(n),但发生得非常少,所以每个操作平均仍是 O(1),这叫作均摊界。

链表

链表把每个值存放在一个节点里,节点带有指向下一个节点的指针。插入或删除只需改动一两个指针,不用移动任何元素,但无法直接跳到第十个节点:只能从头开始沿链接走。只保存头节点的链表要 O(n) 步才能走到尾部;实际使用的链表通常还保存尾指针,双向链表还有指向前一个节点的指针,浏览器历史和 LRU 缓存就是这样构建的。

二叉搜索树

二叉搜索树在每个节点处,把较小的值放在左子树,较大的值放在右子树。查找时比较后向左或向右走,中序遍历则按顺序读出所有值。删除叶子就是直接移除它;只有一个子节点的节点由那个子节点替代;有两个子节点的节点由它的中序后继,即右子树中的最小值来替代。这一切所需的时间都与树的高度成正比:树枝繁叶茂时约为 log n,但如果值按顺序到来,树就会退化成链表,时间变成 n。

AVL 树和红黑树

自平衡树会在每次修改后修复自己的形状。AVL 树由阿德尔森-韦尔斯基和兰迪斯于 1962 年发明,它让每个节点两棵子树的高度之差不超过 1;当某个节点的平衡因子达到 ±2 时,一次旋转(LL 和 RR 情形)或两次旋转(LR 和 RL)就能恢复平衡。红黑树给节点着色,使根为黑色、红色节点没有红色子节点、每条向下的路径经过相同数量的黑色节点,这保证了最长路径不超过最短路径的两倍。它通过重新着色和最多几次旋转来修复自己,Java 的 TreeMap、C++ 的 std::map 和 Linux 调度器里用的就是它。

堆和优先队列

二叉堆是一棵存放在数组中、不需要任何指针的完全二叉树:位置 i 的子节点在 2i + 1 和 2i + 2。在最小堆中,每个父节点都不大于它的子节点,所以最小的值总在根上。新值放到末尾,越过较大的父节点向上浮;取出根时,最后一个值被移到顶端再向下沉。两者都是 O(log n),而把整个数组变成堆只需 O(n)。堆驱动着 Dijkstra 最短路径算法、事件模拟和操作系统调度器中的优先队列,也构成了堆排序。

哈希表

哈希表用哈希函数把键变成数组下标,然后直接到那里去。不同的键可能落到同一个下标:这就是冲突。链地址法在每个桶里保存一个小链表;开放寻址法(如线性探测)会依次尝试后面的槽位,直到找到空位,并且删除键时必须留下墓碑标记,好让之后的查找继续探测。有了好的哈希函数,再通过扩容让装载因子(每个桶的键数)保持较低,插入、查找和删除的平均代价都是 O(1)。差的函数,例如把单词的字符编码相加,会把字母异位词送进同一个桶。Python 的 dict、JavaScript 的对象和数据库索引背后都是哈希表。

字典树和并查集

字典树也叫前缀树,它每层存放一个字符,所以开头相同的单词共享一条路径,并由一个节点标记单词在哪里结束。查找长度为 L 的单词只需 L 步,与存了多少单词无关,而具有某个前缀的所有单词都在同一棵子树里:自动补全和拼写检查就是这样工作的。并查集把元素分成不相交的集合,每个集合是一棵树,树根代表这个集合。查找根时沿父链接一直走到根;合并时把一个根挂到另一个根下面。采用按秩合并和路径压缩后,一长串操作中每个操作的代价几乎是常数,即反阿克曼函数 α(n),对任何实际的 n 都不超过 4。Kruskal 最小生成树算法就依赖于它。

常见问题

数组和链表有什么区别?

数组把元素在内存中紧挨着存放,所以任何位置都能立即访问,但在中间插入就要把后面所有元素往后挪。链表可以通过修改指针在任意位置插入,但要到达某个位置就得从头走过去。数组还能更好地利用处理器缓存,所以在实践中通常更快。

均摊时间是什么意思?

在一长串操作中每个操作的平均代价,即使某一个操作有时很昂贵。一个满了就翻倍的环形缓冲区偶尔要复制全部 n 个元素,但由于缓冲区越大复制就越少见,n 次添加总共只需 O(n),也就是平均每次 O(1)。

堆和二叉搜索树是一回事吗?

不是。二叉搜索树把每个左子树放在节点之前、右子树放在节点之后,所以它能按顺序列出所有值,也能快速找到任意值。堆只保证每个父节点排在子节点之前,这足以立即找到最小值或最大值,却不足以查找任意一个值。

并查集怎么知道两个元素是否连通?

它从每个元素出发,沿父链接一直走到所在树的根。如果两者到达同一个根,它们就在同一个集合中。随后,路径压缩会让路径上的每个节点直接指向根,所以下一次关于它们的询问只需一步。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

打开数据结构可视化