c++ - 二叉树的列表实现是否可扩展？

Question

我正在编写一个简单的编解码器。树将被预先计算，一旦构建就不会有任何更改。它只会被搜索。

平衡二叉树的所有叶节点都是信号值，内部节点是近似压缩表示。

如果我有大量叶节点，使用 stl 向量的列表实现是否可扩展？目前我不知道有多大。

如果我有 4 个叶节点，则列出实现，例如 1,2,3,4,5,6,7

然后的孩子

root(1)-> 2,3
2->4,5
3->6,7

所以我可以简单地使用他们在向量中的位置跳转到孩子们。

Answer 1

在这种情况下，使用“列表”或“数组”不应该造成任何问题（因为树是不可变的）。O(log n) 搜索的唯一要求是快速随机访问（即对给定索引的 O(1) 访问）。

您可以使用 avector或 a deque，两者都合适。vector如果系统找不到足够大的内存块来容纳所有元素，您可能会遇到可伸缩性问题，尽管从一开始它应该证明更简单。如果您遇到此障碍，请切换到deque，尽管您可能会失去一些速度，但由于其分散的性质，它应该可以让您进一步成长。

Answer 2

我更喜欢使用 MAX_ELEMENTS 预先分配的树节点数组（主要在初始化时分配）而不是 stl 向量，原因很简单，因为所有树节点都连续位于堆上以便在运行时更快地访问。

我说更快的访问主要是因为指针跳转可能与分布式 stl 向量元素不一致，因为列表中的元素数量非常庞大（比如溢出 32 位数字）

您可以从处理器的 L1 高速缓存访​​问角度从高速缓存行未命中来查看它。