为什么不用二分搜索树呢

Question

二分搜索树，取最大值不是很简单么。用最大二叉堆还要进行sift操作，不是很麻烦么？这里是为了用数组来构造树，才采用这样有规律的方式么？最大二叉堆优点应该效率更高吧？

Answer 1

liuyubobobo 2020-06-15 10:12:46

首先，如果真的是纯粹的二分搜索树的话，取出最大值确实更简单。但是二分搜索树是可能退化的（成为链表），而堆是绝对平衡的。

如果防止二分搜索树的退化，就需要把二分搜索树改造成为平衡树，那么为了维持平衡，删除一个元素后，还是需要一系列操作。（课程后续会介绍 AVL 树和红黑树）

确实，平衡二分搜索树可以代替堆。但是，如果你的需求堆能够满足的话，堆的性能更好（常数级别差距）。

另外，堆也更省空间一些，因为二分搜索树是链式结构，每一个 Node 中都要存储左右子树的引用，而堆只存储数据就够了。链式结构在极端情况下，也存在因为反复处理 Node 相关的内存管理而带来的性能问题。印象里这个问题你问过？如果我记错了，可以参考我的这篇公众号文章：https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247485646&idx=1&sn=044c6359c49f65935333e6e6c6366f91&chksm=fd8ca788cafb2e9e2fd35d6afc16103dfa9598b255cdd716f1f5b9ea3b210daad591a1abde42&token=1542849361&lang=zh_CN#rd

后续说到了链表的性能问题。二分搜索树同理。

继续加油！：）