既然，我们已经证明，保持 AVL 树的平衡将会使性能得到很大的提升，那我们看看如何在程序中向树插入一个新的键值。因为所有的新键是作为叶节点插入树的，而新叶子的平衡因子为零，所以我们对新插入的节点不作调整。不过一旦有新叶子的插入我们必须更新其父节点的平衡因子。新叶子会如何影响父节点的平衡因子取决于叶节点...

在上一节中我们讨论了建立一个二叉搜索树。我们知道，当树变得不平衡时get和put操作会使二叉搜索树的性能降低到O(n)。在这一节中我们将看到一种特殊的二叉搜索树，它可以自动进行调整，以确保树随时都保持平衡。这种树被称为AVL树，命名源于其发明者：G.M. Adelson-Velskii 和 E.M. Landis。

最后，我们把注意力转向二叉搜索树中最具挑战性的方法，删除一个键值（参见Listing 7）。首要任务是要找到搜索树中要删除的节点。如果树有一个以上的节点，我们使用_get方法找到需要删除的节点。如果树只有一个节点，这意味着我们要删除树的根，但是我们仍然要检查根的键值是否与要删除的键值匹配。在以上两种情况下，如...

我们已经知道了在一个集合中获取键值对的两种不同的方法。回忆一下这些集合是如何实现ADT（抽象数据类型）MAP的。我们讨论两种ADT MAP的实现方式，基于列表的二分查找和哈希表。在这一节中，我们将要学习二叉搜索树，这是另一种键指向值的Map集合，在这种情况下我们不用考虑元素在树中的实际位置，但要知道使用二叉树来...

完成树的实现之后，现在我们来看一个例子，告诉你怎么样利用树去解决一些实际问题。在这个章节，我们来研究解析树。解析树常常用于真实世界的结构表示，例如句子或数学表达式。

在用嵌套列表表示树时，我们使用 Python 的列表来编写这些函数。虽然把界面写成列表的一系列方法与我们已实现其他的抽象数据类型有些不同，但这样做比较有意思，因为它为我们提供一个简单、可以直接查看的递归数据结构。在列表实现树时，我们将存储根节点作为列表的第一个元素的值。列表的第二个元素的本身是一个表示左...

我们已经学过了像栈和队列这样的线性数据结构，同时我们对递归也有了一定的了解，现在让我们来看看另一种常见的数据结构——树（Tree）。树在计算机科学里应用广泛，包括操作系统，图形学，数据库和计算机网络。树和真正的树有许多相似的地方，也包括根、树枝和叶子，它们的不同在于计算机中的树的根在顶层而它的叶子在底部。