Аналитическое решение для прогнозирования размера массива двоичного дерева

Question

Я строю двоичное дерево для последовательности данных, и дерево хранится в массиве на основе 1. Так что, если индекс родительского узла равен idx, левый ребенок - 2 * idx, а правый - 2 * idx + 1.

На каждой итерации я сортирую текущую последовательность на основе определенных критериев, выбираю медианный элемент в качестве родителя, дерево [индекс] = последовательность [медиана], затем выполняю ту же операцию слева (подпоследовательность перед медианой) и справа (подпоследовательность) после медианы) рекурсивно.

Например, если всего 3 элемента, дерево будет:

  1
 / \
2   3   

размер массива для хранения дерева также равен 3

4 элемента:

    1 
   / \
  2   3  
 /
4       

размер массива для хранения дерева также 4

5 элементов:

      1 
   /     \
  2       3  
 / \     /
4 null  5    

размер массива для хранения дерева должен быть 6, так как между 4 и 5 есть дыра.

Таким образом, размер массива определяется только количеством элементов, я считаю, что для него есть аналитическое решение, просто не могу доказать это.

Любое предложение будет оценено. Спасибо.

Answer 1

    int32_t rup2 = roundUpPower2(nPoints);
    if (rup2 == nPoints || rup2 == nPoints + 1)
    {
        return nPoints;
    }
    int32_t leaveLevelCapacity = rup2 / 2;
    int32_t allAbove = leaveLevelCapacity - 1;
    int32_t pointsOnLeave = nPoints - allAbove;

    int32_t iteration = roundDownLog2(pointsOnLeave);
    int32_t leaveSize = 1;
    int32_t gap = leaveLevelCapacity;
    for (int32_t i = 1; i <= iteration; ++i)
    {
        leaveSize += gap / 2;
        gap /= 2;
    }
    return (allAbove + leaveSize);

Answer 2

Я близок к формализации решения. Интуицией сначала найдите максимальную мощность 2

Answer 3

Каждый уровень двоичного дерева содержит в два раза больше узлов, чем предыдущий уровень. Если у вас есть n узлы, то требуемое количество уровней (высота дерева) будет log2(n) + 1, округленное до целого числа. Таким образом, если у вас есть 5 узлов, ваше двоичное дерево будет иметь высоту 3.

Количество узлов в полном двоичном дереве высотой h равно (2^h) - 1. Итак, вы знаете, что максимальный размер массива, который вам нужен для 5 элементов, равен 7. Предполагается, что все уровни заполнены, за исключением, возможно, последнего.

Последняя строка вашего дерева будет содержать (2^h)-1 - n узлов. Последний уровень полного дерева содержит 2^(h-1) узлов. Предполагая, что вы хотите сбалансировать его, чтобы половина узлов находилась слева, а половина - справа, а правая сторона была заполнена слева, то есть вы хотите следующее:

             1
        2         3
     4    5    6     7
    8 9      10 11

Количество пространств массивов, требуемых для последнего уровня вашего дерева, равно 1, или это половина числа, требуемого для полного дерева, плюс половина узлов, требуемых вашим деревом.

Итак:

n = 5
height = roundUp(log2(n) + 1)
fullTreeNodes = (2^height) - 1
fullTreeLeafNodes = 2^(height-1)
nodesOnLeafLevel = fullTreeNodes - n

Теперь самое интересное. Если на уровне листа требуется более 1 узла, и вы хотите сбалансировать стороны, вам понадобится половина fullTreeLeafNodes плюс половина nodesOnLeafLevel. Например, в дереве выше уровень листьев имеет потенциал для 8 узлов. Но у вас есть только 4 листовых узла. Вы хотите, чтобы два из них с левой стороны и два справа. Таким образом, вам нужно выделить место для 4 узлов с левой стороны (2 для элементов левой стороны и 2 пустых пространства), плюс еще два для двух элементов правой стороны.

if (nodesOnLeafLevel == 1)
    arraySize = n
else
    arraySize = (fullTreeNodes - fullTreeLeafNodes/2) + (nodesOnLeafLevel / 2)

Answer 4

У вас действительно не должно быть никаких отверстий. Они создаются вашим алгоритмом разделения, но этот алгоритм неверен.

Для 1-5 предметов ваши деревья должны выглядеть так:

  1       2       2       3       4
         / \     / \     / \     / \
        1       1   3   2   4   2   5
                       /       / \
                      1       1   3

Самый простой способ заполнить дерево - это выполнить упорядоченный обход местоположений узлов, заполняя элементы из последовательности по порядку.