| 操作 | 平均 | 最坏情况 |
|---|
* 均摊:在一长串操作上取平均
数据结构可视化
数据结构是一种存放数据的方式,让最常问的问题能够被快速回答。从栈到红黑树,在十一种经典结构中选一种,输入一个值,然后按下一个操作。每一步都会在屏幕上演示:比较的是哪个节点,哪个链接发生了变化,树为什么旋转,值为什么上浮,并用一句话说明发生了什么。卡片统计每个操作的工作量,表格给出它的运行时间。 选择一种结构,输入一个值,然后按下一个操作。每个操作都会逐步播放:高亮的节点表示正在比较、移动或改变的内容,图片下方的一行说明发生了什么以及为什么。用“上一步”“单步”“播放”和“结束”可以重新查看这些步骤。“随机填充”和“清空”会重新开始,“撤销”可以撤回一个操作。卡片显示大小、树的高度、上一个操作的工作量(比较次数、探测次数或沿父链接走过的次数),以及一个对该结构重要的数值;表格列出每个操作的运行时间。
它是如何运作的
- 选择一种结构,例如二叉搜索树、哈希表或字典树。它一开始带有随机内容;“随机填充”和“清空”会重新开始。
- 输入一个值并按下一个操作:入栈、入队、插入、删除、查找、遍历、合并或查找根。步骤会自动播放;“上一步”“单步”“播放”和“结束”可以再看一遍。
- 在图片下方的一行阅读每一步做了什么,在卡片中观察大小、高度和上一个操作的工作量,并在表格中比较运行时间。
链表、栈和队列
最简单的结构把元素排成一行。栈只在一端操作,所以最后放入的元素最先取出,就像一摞盘子;队列在队尾加入、从队首取出,就像窗口前排的队。这里的队列存放在环形缓冲区中:队首和队尾在一个固定数组里循环移动,越过末尾后回到开头;缓冲区满了,元素就会被复制到大一倍的新缓冲区。链表用指针连接节点,所以在头部插入几乎不花代价,但要找到尾部或某个索引,就得一个一个地沿链接走。
树、堆、哈希表和集合
二叉搜索树把较小的值放在左边,较大的值放在右边,所以只要树保持枝繁叶茂,每一步查找都能把候选减半。AVL 树和红黑树通过旋转来保证这一点,你可以看到这些旋转,它们以各自的情形命名。堆只把最小或最大的值放在顶端,而这正是优先队列所需要的全部。哈希表直接跳到由键算出的桶,并且必须处理冲突;字典树共享单词的前缀;并查集能在几乎常数的时间内回答两个元素是否属于同一个集合。
常见问题
我应该使用哪种数据结构?
这取决于你最常问的问题。元素按到达顺序或相反顺序处理时,用栈或队列;查找一个键,用哈希表;还需要按顺序取键或找最接近的键时,用 AVL 树或红黑树这样的平衡搜索树;永远只需要最小或最大元素时,用堆;处理单词和前缀,用字典树;跟踪不断合并的分组,用并查集。
AVL 树和红黑树有什么区别?
两者都让二叉搜索树保持较浅,所以每次查找、插入和删除所需的时间都与 log n 成正比。AVL 树平衡得更严格,每个节点两侧的高度之差不超过 1,所以查找略快。红黑树允许更多余地,修改时需要的旋转更少,这就是许多标准库用它来实现有序映射和集合的原因。
为什么哈希表在最坏情况下会变慢?
如果许多键落入同一个桶,查找就必须逐个检查它们,就像在链表中一样。好的哈希函数会把键均匀分散,表也会在过满之前扩容,所以查找平均只需常数时间。试试表长为 10、数字都以同一个数位结尾,或者用彼此是字母异位词的单词,看看冲突如何堆积。
AVL 节点旁边的数字是什么意思?
它们是平衡因子:一个节点左子树的高度减去右子树的高度。在 AVL 树中,每个平衡因子都必须是 −1、0 或 +1。当一次插入或删除使某个平衡因子变成 +2 或 −2 时,树就在那个节点旋转;情形(LL、RR、LR 或 RL)说明多出的高度偏向哪一边,并决定需要一次还是两次旋转。
会把任何内容发送到服务器吗?
不会。每个操作都在你的浏览器中运行,每种结构的内容都保存在这个浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器