找到总能构成完整二叉搜索树的根

Question

我需要做一个Complete Binary Search Tree。如果我有一个看起来像这样的方法：

public void createCompleteTree(Node n, int i)

例如，我使用数字 9 作为 i 值，我该怎么做才能找到一个可以构成完整树的根？

如果我使用 9 作为值，数字将是 1,2,3,4,5,6,7,8,9。对于完整的二叉搜索树，根必须是 6，如下所示：

我怎样才能创建一个知道这个的方法？它应该适用于任何类型的数字，所以如果我想使用数字 14，它应该可以。

到目前为止，我唯一的代码是一个插入方法，它只检查要插入的数字是大于（向右）还是小于（向左）我们当前所在的节点。 x 是要插入的数字，t 是我们在树中的当前节点：

 private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
{
    if( t == null )
        return new BinaryNode<>( x, null, null );

    int compareResult = x.compareTo( t.element );

    if( compareResult < 0 )
        t.left = insert( x, t.left );
    else if( compareResult > 0 )
        t.right = insert( x, t.right );
    else
        ;  // Duplicate; do nothing
    return t;
}

Answer 1

二叉树的根不必是常量。存在自平衡树。看看这个：enter link description here

Answer 2

具有 N 层的二叉树可能包含从 2^(N-1) 到 2^N - 1 个元素。
您描述的最后（最低）级别的树可能包含从 1 到 2^(N-1) 严格顺序的元素。
具有 K 个元素和 N 个级别的树包含 K - 2^(N-1) + 1 个元素在它的最后一层。这棵树的左子树包含 C = min(K - 2^(N-1) + 1, 2^(N-2)) 个元素。所以树的根将是 2^(N-2) + C -th element

Answer 3

这是解决方案：

据我所知，通过增加长度上每个附加元素的偏移量来计算偏移量，直到达到水平宽度的 1/2。因此，高度为 4 的 BST 在最低层有 8 个元素。大小为 8、9、10、... 15 的列表创建高度为 4 的 BST。对于这些列表，列表中的根索引为 4、5、6、7、7、7、7、7。

似乎有效

private int calcMid(int length) {
    if ( length <= 4 )
        return length / 2;
    int levelSize = 1;
    int total = 1;
    while ( total < length ) {
        levelSize *= 2;
        total += levelSize;
    }
    int excess = length - (total - levelSize);
    int minMid = (total - levelSize + 1) / 2;
    if ( excess <= levelSize / 2 ) {
        return minMid + (excess - 1); 
    } else {
        int midExcess = levelSize/2; 
        return minMid + (midExcess - 1);
   }
}

作为此代码的一部分找到：

找到总能构成完整二叉搜索树的根

Find root that will always make a complete Binary Search Tree

java

binary-tree

binary-search-tree