data-structures - 如何将不平衡树存储在矩阵中

Question

我正在使用一个词汇树，一个k-ary具有深度的树数据结构L，它是迭代运行层次k-means聚类的结果。这是一个不平衡的结构，因为当分配给集群的数据点的数量小于集群的数量时，集群过程可能会停止。

我的问题是我需要以矩阵格式存储这棵树。

我考虑过简单地以广度优先顺序存储它，但是如果实际节点数之间的差异（比方说n）与平衡树中的理论节点数增加，即：

n << (1-k^L)/(1-k)

有没有什么方法可以有效地以矩阵形式存储不平衡树而不浪费内存或浪费更少的可能？

Answer 1

似乎很难不浪费任何空间。但是，下面概述了一个相当简单的方法，并且只需要 O(N log_k N) 空间或 O(k N log_k N) 如果总是分配叶子的空间（在某些情况下有用），其中 N 是树中的元素。代价是访问一个元素需要 O(log_k N)。

确切的实现是相当可变的，因为它取决于许多因素。这个想法是将平衡二叉树的表示简单地概括为一个数组，作为一个不平衡的 n 叉树作为一个矩阵工作。这是通过让矩阵单元充当节点来完成的。节点中包含的信息可以位于具有数据结构的单个单元格中，也可以分布在接下来的几个单元格中。主要的是每个节点必须包含该特定节点的信息以及它所拥有的任何子节点的位置信息。然后使用增量指针来跟踪下一个儿童空闲点的位置。

总的来说，它只是一个小于或等于 r*c 元素的数组，它被分解为一个由 r 行和 c 列组成的矩阵。列表列表可能更有用，因为行 L 将包含深度 L 处的节点。否则，那里没有多大用处。