二进制搜索字符串的树（平衡之前） [英] Binary Search Tree of Strings (before balancing)

问题描述

我读了二叉搜索树，我有一个问题要回答类似有序弦乐的二叉树

I'm reading up on Binary Search Trees and I have a question to answer similar to Ordered Binary Tree of Strings

是我画下面正确的前后平衡后的树？所输入的数据是字符串，以中，水星，金星，地球，火星，木星，土星，天王星

Are the trees I've drawn below correct for before and after balancing? The data being entered are the strings, in order of, Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus

平衡之前：

      Mercury
     /       \
   Earth     Venus
     \        /
    Mars   Saturn
    /         \
Jupiter      Uranus

均衡后：

          Mercury
         /       \
   Jupiter        Uranus
   /     \        /     \
Earth   Mars   Saturn  Venus

时也正确，所述第一树的深度是3和第二树的深度为2，并且最大尺寸是7（基于 N = 2 ^（D + 1 ）-1 ，其中 D =深度？

推荐答案

是的，平衡看起来是正确的二叉搜索树排序是正确的（对于任何给定的节点，左子树的所有节点都较小，在所有节点右子树都较大），它是完美的平衡。

Yes, the balancing looks correct as the binary search tree ordering is correct (for any given node, all nodes in the left subtree are smaller and all nodes in the right subtree are larger) and it's perfectly balanced.

虽然我不知道有一个通用的平衡树算法（至少不是一个我听说过）。然而有自我平衡的BST的像红黑树和AVL树。

Although I'm not sure there's a generic "balance the tree" algorithm (at least not one I've heard of). There are however self-balancing BST's like red-black trees and AVL trees.

是的，深度是正确的，因为每维基百科：

Yes, the depths are correct, as per Wikipedia:

树的深度（或高度）是路径的从根到树中的最深节点的长度。 A（根）树只有一个节点（根）具有的深度为零。

The depth (or height) of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a depth of zero.

是的，最大尺寸计算也是正确的。你可以认为这是如下：
最大尺寸为 1 + 2 + 4 + 8 + ... + 2 深度 （每学期相当于每级节点的最大数量）。照片 这就是 1111111 ... 111 （深度 1的）二进制。
当然，上面加一 100000 ...... 000 （深度 0），这是 2 深度+ 1 。
再减去一，我们得到 2 （深度+ 1） - 1

Yes, the maximum size calculation is also correct. You can think of this as follows:
The maximum size is 1 + 2 + 4 + 8 + ... + 2depth (each term corresponds to the maximum number of nodes per level).
That is 1111111...111 (depth 1's) in binary.
And, of course, the above plus one is 100000...000 (depth 0's), which is 2depth + 1.
Subtracting the one again, we get 2(depth + 1) - 1.

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