平衡二进制搜索树中的数字 [英] Balanced Binary Search Tree for numbers

问题描述

我想为1到20之间的数字绘制平衡的二叉搜索树.

I wanted to draw a balanced binary search tree for numbers from 1 to 20.

             _______10_______
            /                \
        ___5___                15
       /       \             /    \
      3         8          13      18
     / \       / \        /  \     /  \
    2   4     7   9     12    14  17    19
   /          /          /        /     
   1         6          11       16

以上那棵树正确且平衡吗?

Is the above tree correct and balanced?

推荐答案

回答您的原始问题，即是否需要首先计算高度，不，不需要到.您只需要了解平衡树就是其中最高节点与最短节点之间的高度差为零或一的树，而实现这一点的最简单方法是确保在填充树时始终选择可能列表的中点.子树的顶部节点.

In answer to your original question as to whether or not you need to first calculate the height, no, you don't need to. You just have to understand that a balanced tree is one where the height difference between the tallest and shortest node is zero or one, and the simplest way to achieve this is to ensure that you always pick the midpoint of the possible list, when populating the top node in a sub-tree.

您的样本树是平衡的，因为所有叶节点位于底部或从下到下，因此任何两个叶节点之间的高度差最大为一个.

Your sample tree is balanced since all leaf nodes are either at the bottom or next-to-bottom level, hence the difference in heights between any two leaf nodes is at most one.

要从1到20(含1和20)之间创建一个平衡树，只需将根条目设置为10或11(中点的数字为10.5)，以便在任一子树中都有相同数量的数字.

To create a balanced tree from the numbers 1 through 20 inclusive, you can just make the root entry 10 or 11 (the midpoint being 10.5 for those numbers), so that there's an equal quantity of numbers in either sub-tree.

然后只需对每个子树进行递归操作.在10的下侧，5是中点:

Then just do that recursively for each sub-tree. On the lower side of 10, 5 is the midpoint:

           10
          /  \
         5    11-thru-19 sub-tree
        / \
1-thru-4   6-thru-9
sub-tree   sub-tree

只需对此进行扩展，您将得到类似以下的内容:

Just expand on that and you'll end up with something like:

         _______10_______
        /                \
    ___5___               15
   /       \             /  \
  2         7          13    17
 / \       / \        /     /  \
1   3     6   8     11    16    18    <- depth of highest leaf node
     \         \      \           \
      4         9      12          19 <- depth of lowest leaf node
                                                     ^
                                                     |
                                               Difference is 1

中点可以在该数字之上和之下的数量之差为一或零的数字处找到.对于包括1到20在内的整个数字列表，小于10的数字为9，大于10的数字为10(或者，如果您选择11作为中点，则数量为10和9).

The midpoint can be found at the number where the difference between quantities above and below that numbers is one or zero. For the whole list of numbers 1 through 20 inclusive, there are nine less than 10 and ten greater than 10 (or, if you chose 11 as the midpoint, the quantities are ten and nine).

您的样本和我的样本之间的差异可能与以下事实有关:我更喜欢通过舍入可以选择的位置来选择中点(这意味着我的右子树倾向于更重").由于左子树较重，因此您似乎已舍入.

The difference between your sample and mine is probably to do with the fact that I preferred to pick the midpoint by rounding down where there was a choice (meaning my right sub-trees tend to be "heavier"). Because your left sub-trees are heavier, you appear to have rounded up.

选择10作为初始中点后，左子树上没有任何余地，您必须选择5，因为它的上下有四个.任何其他中点将导致两个半部分之间至少相差两个(例如，选择4作为中点将具有大小为三和五的两个半部分).根据数据，这仍然可以给您一个平衡的子树，但是选择中点安全".

After choosing 10 as the initial midpoint, there's no leeway on the left sub-tree, you have to choose 5 since it has four above and below it. Any other midpoint would result in a difference of at least two between the two halves (for example, choosing 4 as the midpoint would have the two halves of size three and five). This can still give you a balanced sub-tree depending on the data but it's "safer" to choose the midpoint.

这篇关于平衡二进制搜索树中的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！