为什么 'complete binary tree' 或 'binary heap' 的最后一层可能是部分空的？有充分的理由吗？
Why may the last level of 'complete binary tree' or a 'binary heap' be partially empty ? Is there a good reason for it?
完全二叉树的定义是"A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible."我想知道为什么最后一层允许部分填充。这在某些情况/情况下有帮助吗？
我试图在很多地方搜索这个问题的答案，但是我没能找到满意的答案。有人可以帮我回答这个问题吗？非常感谢...
这就是完全二叉树的定义。它不一定有帮助或阻碍任何事情，它就是这样。
如果您对此主题感兴趣，请查找平衡二叉树。在那里，只让最低层不被完全填充是有意义的，以确保树是平衡的，并且您没有 10 节点深的左侧和 1 节点深的右侧。
完全填充树的所有级别有助于确保快速搜索时间。如果所有级别都被完全填满，您就会知道树的深度在所有可能的路径上都是相等的，因此可以确保您在搜索速度上有一个很好的上限。在这种情况下，您可以通过 D = floor(lg(N)) 计算所有可能的叶节点路径的深度，其中 N 是节点数。
现在，想象一下如果您根本不需要填充关卡。您可能会遇到类似这种怪异的情况，其中某些元素的获取速度会比其他元素快得多。
对这个问题的看法与其他答案不同：如果所有级别都需要完全填满，那么某些 n 的树只能包含 (2^n)-1 个元素。 IE。 1, 3, 7, 15, ... 元素。通过允许最后一层被部分填充，您可以拥有包含任意数量元素的二叉树。
完全二叉树的定义是"A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible."我想知道为什么最后一层允许部分填充。这在某些情况/情况下有帮助吗？
我试图在很多地方搜索这个问题的答案，但是我没能找到满意的答案。有人可以帮我回答这个问题吗？非常感谢...
这就是完全二叉树的定义。它不一定有帮助或阻碍任何事情，它就是这样。
如果您对此主题感兴趣，请查找平衡二叉树。在那里，只让最低层不被完全填充是有意义的，以确保树是平衡的，并且您没有 10 节点深的左侧和 1 节点深的右侧。
完全填充树的所有级别有助于确保快速搜索时间。如果所有级别都被完全填满，您就会知道树的深度在所有可能的路径上都是相等的，因此可以确保您在搜索速度上有一个很好的上限。在这种情况下，您可以通过 D = floor(lg(N)) 计算所有可能的叶节点路径的深度，其中 N 是节点数。
现在，想象一下如果您根本不需要填充关卡。您可能会遇到类似这种怪异的情况，其中某些元素的获取速度会比其他元素快得多。
对这个问题的看法与其他答案不同：如果所有级别都需要完全填满，那么某些 n 的树只能包含 (2^n)-1 个元素。 IE。 1, 3, 7, 15, ... 元素。通过允许最后一层被部分填充，您可以拥有包含任意数量元素的二叉树。