Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
12 lines (6 sloc) 1.64 KB

二叉树的优点

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

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

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

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

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

You can’t perform that action at this time.