Аналитическое решение для прогнозирования размера массива двоичного дерева
Вот использование киллера для конструктора на месте C ++: выравнивание с линией кэша, а также другие полномочия из двух границ. Вот мой сверхбыстрый алгоритм выравнивания указателя на любую мощность 2-х границ с 5-ти или менее однотактными инструкциями :
/* Quickly aligns the given pointer to a power of two boundary IN BYTES.
@return An aligned pointer of typename T.
@brief Algorithm is a 2's compliment trick that works by masking off
the desired number in 2's compliment and adding them to the
pointer.
@param pointer The pointer to align.
@param boundary_byte_count The boundary byte count that must be an even
power of 2.
@warning Function does not check if the boundary is a power of 2! */
template
inline T* AlignUp(void* pointer, uintptr_t boundary_byte_count) {
uintptr_t value = reinterpret_cast(pointer);
value += (((~value) + 1) & (boundary_byte_count - 1));
return reinterpret_cast(value);
}
struct Foo { Foo () {} };
char buffer[sizeof (Foo) + 64];
Foo* foo = new (AlignUp (buffer, 64)) Foo ();
Теперь не это просто положил улыбку на твоем лице (:-). I ♥♥♥ C ++ 1x
4 ответа
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);
Я близок к формализации решения. Интуицией сначала найдите максимальную мощность 2 < N, затем проверьте, является ли N - 2 ^ m четным или нечетным, решите, какую часть уровня отпуска нужно увеличить.
У тебя действительно не должно быть дыр. Они создаются вашим алгоритмом разделения, но этот алгоритм неверен.
Для 1-5 элементов ваши деревья должны выглядеть следующим образом:
1 2 2 3 4
/ \ / \ / \ / \
1 1 3 2 4 2 5
/ / \
1 1 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)