预计阅读本页时间：-
如果需要，尽可能用实践检验
在继续深入之前，Gary希望能够较好地了解程序的运行状况。他和Graham坐下来一起写了一些小程序，通过调用这个库来检查这些程序是如何运行的。也许他们能够更好地明白是什么导致了这个诡异的问题。
注意：你会进行哪些实验呢？你的程序将会是什么样？
Gary和Graham的第一个测试程序（程序A）如例1-1所示。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
例1-1：程序A代码
他们运行了这个程序然后等待结果。这个程序运行了数分钟。即便在当时的计算机速度比较缓慢的情况下，这个运行时间也很明显不可接受。当程序运行结束的时候，记录显示有32MB的内存泄漏。那么如果程序中所有分配的内存都被释放了会出现什么情况呢？他们做了一点小修改，这就是程序B，如例1-2所示。
例1-2：程序B代码
编译并且运行程序B，程序B在几秒内就运行结束了。Graham确信这个问题和程序结束的时候没有释放的内存大小相关。但是他不知道问题出在哪。他搜寻了整个代码，花费了数个小时却也找不出问题在哪儿。Gary并不像Graham那样确信问题是与内存泄漏的数目相关。他建议做更多的实验，并且对程序做了另一次的修改，将所有的内存释放操作集中到程序的最后。如例1-3所示。
例1-3：程序C代码
这个程序就像第一个程序那样缓慢地运行着！这个例子证明了性能问题并不是由内存泄漏的数量导致的。不仅如此，这个程序让Gary明白了问题原因的真正所在。并不是程序结尾的内存分配次数导致性能问题，而是任意时刻没有被释放的内存的最大数量严重影响了整个程序的性能。如果程序本身的内存泄漏并不是影响问题的唯一因素，那么Graham维护内存分配以及释放的记录的方法就存在一些问题。在程序B的执行过程中，任何时刻都没有超过32字节的未释放内存。但是第一个和第三个程序运行的时候却有100万个内存分配操作没有相应的释放操作。分配和释放内存并不是关键，所以问题肯定和Graham记录内存分配和释放请求的代码有关。
Gary询问了Graham他是如何记录分配的内存的。Graham回答说他使用了一个二叉树来记录，每一个节点都记录了指向子节点的指针（若有的话）、指向分配内存的地址、分配的大小以及程序在哪儿进行的分配请求。Graham还补充道他是使用内存地址作为节点的键值，因此不能重复，这个方法使得插入和删除内存分配的记录更加容易。
使用二叉树通常比简单地使用有序链表更加高效。假设有一个包含了n个元素的有序链表，这个表中的每个元素被请求的概率是相等的。那么一个寻找表中一个元素平均将要花费n/2次比较。从表中插入或者删除元素平均也需要大约n/2次操作。计算机科学专业的教科书描述这些操作（查找、插入和删除）的性能为O(n)，实际上这些操作的数量的两倍就是和这个链表长度有关，进行这些操作花费的时间期望也是这么多[1]。
使用一棵二叉树能够将上述操作降到O(log n)的花费，虽然代码可能有一些难以编写和维护。跟链表的时间花费不一样，使用了二叉树，这些操作的花费仅仅是常数量的增长。当处理1 000 000个元素的时候，我们只需要平均检查20个元素，相比有序链表需要500 000次操作，效率之高可想而之。如果键值是平均分布在树中的，那么使用二叉树是一个很好的选择。如果键值不是平均分布的，那么树会变得扭曲，不平衡，在某种程度上这个数据结构就会认为不适合用来查找。
知道了一些关于二叉树以及如何工作的知识后，Gary询问Graham一个价值64 000美元（毕竟这个数字是对数）的问题：“你对这个二叉树进行了平衡处理吗？”Graham非常惊讶，因为他是一名优秀的软件工程师，不可能不知道这样简单的东西。“没有，为什么我需要做这个？这个操作使得代码更加复杂了。”不过事实的确是由于Graham没有做平衡处理，使得这棵树右倾到操作时间近似线性的程度，这种情况下更像是一个有序链表而不是一棵二叉树。想知道为什么吗，看看图1-2中的两棵二叉树。在a树中顺序插入数字1～15。它的根节点值为1，从根节点出发到达值为15的节点需要经过14个节点。b树插入了相同的数字，不过是按照这样的顺序：＜8，4，12，2，6，10，14，1，3，5，7，9，11，13，15＞。在这种情况下下，根节点的值是8，不过从根节点到其他节点的路径在3个节点或者更少。我们在第5章将会看到，查找时间直接和最长路径的长度相关。
