干杯,假设我们有一个不允许重复元素的 MAX 堆。这个堆有可能是 BST 吗?选择下面的正确答案:
哪一个是合适的答案?我会选择(3)和(4),以及我对所有答案的解释。谢谢!
开始:
(最大)堆是一个完全二叉树,其中每个节点的值都大于或等于其子节点的值。
A BST 是一棵二叉树,其中每个节点最多有 2 个子节点,并且每个节点的值都大于其左子树的所有值,并小于其右子树的所有值。
我想到的堆只有一个值,例如8. 由于它没有子节点,因此这棵树仅由其根组成。这棵树是完整的,根的值大于其子树的值,因此它是一个堆。这棵树也是一个没有孩子的 BST。所以有一个堆也是一个 BST。
这当然是错误的。设最大堆为:
当然,这是一个最大堆,但不是 BST,因为 6 放置在 8 的右侧。
我认为这是正确的,正如我在(1)中也解释过的那样
最多两个节点意味着我们可以有 0、1 或 2 个节点。
如果我们有 0 个节点,则它成立。
如果我们有 1 个节点,它也成立,我们证明了这一点。
如果我们有 2 个节点,它也成立。让最大堆有 2 个节点。要使其成为最大堆,它必须是完整的树,因此根据定义,第二个节点应放置在第一个节点(根)的左侧。根据最大堆的定义,第二个节点还包含小于第一个节点(根)的值。这也是具有 2 个节点的 BST 树。所以这是正确的。
(如有错误请指出,谢谢!)
这很棘手!让我们一一深入研究所有选项。
从您问题的选项来看:
错了。 因为具有一两个元素的堆也可以是有效的 BST。 (参见第三个选项的示例)
错了。从你的例子中可以清楚地看出,堆有时无法保存 BST 的属性,特别是 Max-Heap。
错了。因为一棵有两个孩子的树也可以拥有 BST 的财产。
示例-
3
\
5
上面的节点结构是BST,也是一个Min-Heap。
你猜怎么着!也错了!因为单个节点可以是有效的 BST 以及最大/最小堆。
我认为这个问题最合适的答案是选项(3)。
堆树要成为二叉搜索树(BST),主要必须满足两个条件,它们是:
Condition 1
:每个节点最多有两个子节点(每个节点的最大度数等于 2)。Condition 2
:左子树为空或具有较小的值。同样,右子树要么为空,要么具有更大的值。
让我们看看为什么其他选项不正确以及为什么选项(3)是最合适的。
Option (1): A heap can never be a BST
:Option (2): A heap is always a BST
:Option (4): A heap can be BST if and only if it has up to 2 nodes
:condition 2
。
Option (3): A heap can be a BST if there is only one node inside it (root)
:condition 1
和 condition 2
,因为没有子节点。