Найти корень, который всегда будет составлять полное дерево бинарного поиска

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

Двоичное дерево с уровнями N может содержать от 2 ^ (N-1) до 2 ^ N - 1 элемент.
Последний (самый низкий) уровень дерева, который вы описываете, может содержать от 1 до 2 ^ (N-1) элементов в строгом порядке.
Дерево с * 1013Элементы * K и уровни N содержат элементы K - 2 ^ (N-1) + 1 на последнем уровне.Левое поддерево этого дерева содержит C = min (K - 2 ^ (N-1) + 1, 2 ^ (N-2)) элементов.Таким образом, корень дерева будет 2 ^ (N-2) + C -й элемент

Answer 2

Это решение:

Из того, что я могу сказать, вычисление смещения осуществляется путем увеличения смещения для каждого дополнительного элемента в длине, пока вы не достигнете 1/2 ширины уровня.Итак, BST с высотой 4 имеет 8 элементов на самом низком уровне.Списки размером 8, 9, 10,… 15 создают BST с высотой 4. Для этих списков корневой индекс в списке равен 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);
   }
}

Найдено как часть этого кода:

https://stackoverflow.com/a/52749727/9899617

Answer 3

Корень вашего бинарного дерева не должен быть постоянным.Там существуют самобалансирующиеся деревья.Проверьте это: введите описание ссылки здесь