05.3.2 二叉树的优点

当你要描述多层次数据的时候，树是最好的选择。因此，树被广泛应用于编程语言的编译器解析计算机程序的过程。

此外，树本身就具有有序性，所以你不必另外对其进行排序。只要插入到了正确的位置，那么树就能保持有序。然而，由于树的构造方式，删除元素的操作有时至关重要。

如果一个二叉树是平衡的，它的查找、插入、删除操作需要 log(n) 步，这里的 n 是树上元素的总数量。此外，平衡二叉树的高度约为 log2(n)，这意味着一个拥有 10,000 个元素的平衡树的高度大约是 14。类似的，拥有 100,000 个元素的平衡树的高度大约是 17，拥有 1,000,000 个元素的平衡树的高度大约是 20。也就是说，向一个平衡二叉树中插入大量的元素后，对树进行操作的速度并不会大幅变化。换个说法，你只需要不到 20 步就能到达一个拥有 1,000,000 个节点的树上的任意一个节点！

二叉树最大的一个缺点是树的形状很依赖元素插入的顺序。如果树上元素的键又长又复杂，那么插入和查找元素的过程需要进行大量的匹配，从而变得很慢。最后，如果一个树不是平衡的，那么就很难对其性能进行预测。

尽管你能更快地创建链表或数组，但是二叉树在查找操作中的灵活性值得付出额外的开销并进行维护。在二叉树上查找一个元素时，你会比较要搜索的元素则值与当前节点值的大小，然后决定在哪个子树上继续搜索，这样做可以节约大量的时间。