疯狂的青蛙

平衡二叉搜索树 我们知道，当二叉搜索树不平衡时，get 和 put 等操作的性能可能降到 $O(n)$。下面将介绍一种特殊的二叉搜索树，它能自动维持平衡。这种树叫作 AVL 树，以其发明者 G. M. Adelson-Velskii 和 E. M. Landis 的姓氏命名。 AVL 树实现映射抽象数据类型的方式与普通的二叉搜索树一样，唯一的差别就是性能。实现 AVL 树时，要记录每个节点的平衡因

- 阅读全文 -

二叉搜索树 我们需要学习如何利用二叉树结构提供高效的搜索。 搜索树的操作 搜索树的接口类似于 Python 字典。 Map() 新建一个空的映射。 put(key, val) 往映射中加入一个新的键–值对。如果键已经存在，就用新值替换旧值。 get(key) 返回 key 对应的值。如果 key 不存在，则返回 None。 del 通过 del map[key]这样的语句从映射中删除键–值对。

- 阅读全文 -

利用二叉堆实现优先级队列 队列有一个重要的变体，叫作优先级队列。和队列一样，优先级队列从头部移除元素，不过元素的逻辑顺序是由优先级决定的。优先级最高的元素在最前，优先级最低的元素在最后。因此，当一个元素入队时，它可能直接被移到优先级队列的头部。 我们可以使用排序函数和列表实现优先级队列。但是，就时间复杂度而言，列表的插入操作是 $O(n)$，排序操作是 $O(n\log n)$。 实现优先级队列的

- 阅读全文 -

树 快速总结： 映射的不同实现间的性能对比： 有序列表 散列表 二叉搜索树 AVL 树 put $O(n)$ $O(1)$ $O(n)$ $O(\log_2{n})$ get $O(\log_2{n})$ $O(1)$ $O(n)$ $O(\log_2{n})$ in $O(\log_2{n})$ $O(1)$ $O(n)$ $O(\log_2{n})$ del $O(

- 阅读全文 -

排序是指将集合中的元素按某种顺序排列的过程。 分析排序过程： 首先，排序算法要能比较大小。为了给一个集合排序，需要某种系统化的比较方法，以检查元素的排列是否违反了顺序。在衡量排序过程时，最常用的指标就是总的比较次数。 其次，当元素的排列顺序不正确时，需要交换它们的位置。交换是一个耗时的操作，总的交换次数对于衡量排序算法的总体效率来说也很重要。 快速总结： 冒泡排序、选择排序和插入排序都是 $

- 阅读全文 -