data-structures - 具有指数分裂因子的树

Question

您将什么称为拆分因子为 的搜索树，存储在树中的数据点的维度在2^k哪里？k（数据点是向量x_1, ... x_k）

因为k=1我们会得到一个正常的二叉搜索树。因为k=2我们会在树的每个节点中分成 4 个象限，等等。

这种树的正确名称是k什么？

Answer 1

有很多这样的数据结构，我不知道它是否有一个特定的名称。例如，四叉树和八叉树结构具有 k = 2 和 k = 3 的这些分支因子，而R-tree数据结构在更高维空间中执行此操作（但也有一些额外的分层结构）。

通常，高维数据结构没有像这样巨大的分支因子。像kd 树（或更一般地说，BSP 树）这样的数据结构存储高维数据，但具有固定的分支因子 2，以避免成倍增加高维的空间使用量。高维度的分段树通常使用分数级联，这使它们可以在不牺牲性能的情况下使用低分支因子。

希望这可以帮助！