Tree with exponential split factor

Question

What do you call a search tree with a split factor of 2^k, где k is the dimensionality of the data points stored within the tree? (The data points are vectors x_1, ... x_k)

За k=1 we would get a normal binary search tree. За k=2 we would split into 4 quadrants in every node in the tree, etc.

What would be the proper name for such a tree for arbitrary k?

Answer 1

Подобных структур данных много, и я не знаю, есть ли для них конкретное имя. Например, структуры quadtree и octree имеют эти коэффициенты ветвления для k = 2 и k = 3, и структура данных R-дерева делает это в пространствах более высокой размерности (но также имеет некоторую дополнительную структуру, расположенную сверху).

Как правило, у многомерных структур данных нет таких огромных факторов ветвления, как этот. Структуры данных, такие как дерево kd (или, в более общем случае, деревья BSP), хранят многомерные данные, но имеют фиксированный коэффициент ветвления, равный двум, чтобы избежать экспоненциального увеличения использования пространства для больших измерений. Деревья сегментов в больших измерениях часто используют дробное каскадирование, что позволяет им использовать низкий коэффициент ветвления без ущерба для производительности.

Надеюсь это поможет!