对于程序员来说，内存泄漏是一个非常严重的问题。当程序需要长时间运行时，例如现在的大多数服务器程序，内存泄漏将会最终导致程序耗尽物理内存然后崩溃掉，这就会产生非常严重的后果。
一个程序员可能会写一个程序来监视内存分配和回收，并且报告程序的使用情况，以便于监视内存泄漏。这个内存分析程序可以仅仅是简单地重写一个新的malloc和free函数来记录每一次分配和释放内存的信息。我们希望记录每一次内存分配操作，并且当内存释放时，我们必须及时更新信息。
在前面的描述中，我们不可能知道我们将要存储多少个元素。一个基于散列的查找也许可以正常工作。但是我们也许会选择一个错误的散列表规模，以至于影响高效的资源使用。一个替代的查找策略是采用查找树。当我们准备在内存中维护我们的查找数据时，我们使用二叉查找树能够很好地做到这个。二叉查找树在动态数据，尤其是插入和删除操作非常频繁时，性能表现非常好。
一棵二叉查找树，T是一个节点的有限集合，并且节点之间能够通过有序的特征，如键值，来进行区分。节点的集合可以是空，或者只是包含了一个根节点nr。每一个节点n都指向了两棵子二叉查找树，Tl和Tr，并且满足这样的性质：如果k是节点n的键值，那么所有在Tl的元素的键值都小于等于k，所有在Tr的元素的键值都大于k。这个性质叫做二叉查找树性质（Cormen等，2001）。图5-8给出了一棵二叉树的例子。每一个节点都有一个整数键值，唯一的区分节点。你可以看到在图5-8的树中寻找一个键值只需要从根节点开始，最多探测3个节点。这棵树是完全平衡的。也就是说，每一个节点恰好有两个子节点。一棵完全平衡二叉树有2n-1个节点。
图 5-8 一棵简单的二叉查找树树也可能不会总是平衡的。在最坏情况下，一棵树可能退化到链表的性能。考虑使用和图5-8相同的节点，但是如果按照图5-9的方式来排列的话。节点被按照升序添加，虽然这个结构的确满足了二叉树的严格定义，每一个节点的左子树都是空的。这棵树简直就是一个链表。
图 5-9 一棵退化的二叉查找树