Нахождение размера идеального четырехугольного дерева

Question

Мне нужно найти размер идеального четырехугольного дерева. Это означает, что у меня есть 1 корневой узел, который разбивается на 4 узла, которые делятся на 4 узла и т. Д.

так что четырехугольное дерево высотой 1 будет размером 1 высота 2 = размер 5 (1 + 4) высота 3 = размер 21 (1 + 4 + 16) высота 4 = размер 85 (1 + 4 + 16 + 64)

и т.д ..

Я знаю, что размер идеального двоичного дерева можно найти с помощью: size = 2 ^ (height + 1) -1 Поэтому я считаю, что аналогичное уравнение существует для четырехугольного дерева.

Так что же это?

Answer 1

Для четырехугольного дерева алгоритм имеет вид

((4^depth)-1)/3

Например, для глубины 3 вы получите

(64-1)/3 = 21

, а если посчитать три слоя, вы получите

1 + 4 + 16 = 21

В моей реализации я даже разделил его на два массива, в которых размер всех узлов, которые не покидают узлы, равен

((4^(depth-1))-1)/3

, а оставленных узлов -

4^(depth-1)

.во время компиляции с метапрограммированием для pow и аргументом шаблона для глубины.Поэтому я просто размещаю свои узлы в двух массивах.

Answer 2

Это геометрическая серия .Таким образом, соответствующая формула имеет вид:

S = a * (1 - r^n) / (1 - r)

, где a - первое значение, r - общее отношение, n - число слагаемых, а ^ обозначает "к-тому".-мощность-из».

Answer 3

На всякий случай кому-нибудь понадобится пример кода (в swift3)

public func tileCount(forLevelRange levelRange: Range<UInt>) -> UInt64 {

   var tileCount: UInt64 = 0
   for level in levelRange.lowerBound ..< levelRange.upperBound {
       tileCount += UInt64(pow(Double(1 << level), 2) )
   }

   return tileCount
}