gpt4 book ai didi

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

转载 作者:搜寻专家 更新时间:2023-10-31 01:14:55 25 4
gpt4 key购买 nike

我正在编写一个简单的编解码器。树将被预先计算,一旦构建就不会发生任何变化。它只会被搜索。

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

如果我有大量叶节点,使用 STL vector 的列表实现是否可扩展?目前我不知道 large 有多大。

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

然后 child

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

所以我可以使用 vector 中的位置简单地跳转到 child 。

最佳答案

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

您可以使用vectordeque,两者都适用。如果系统找不到足够大的内存块来容纳所有元素,您可能会遇到 vector 的可伸缩性问题,尽管从一开始它应该更简单。如果您遇到了这个障碍,请切换到 deque,虽然您可能会失去一些速度,但由于其碎片化的性质,它应该可以让您进一步发展。

关于c++ - 二叉树的列表实现是否可扩展?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10715389/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com