gig*_*tes 17 c++ heap tree data-structures
堆是一个经典的数据结构,它将完整的二进制(或通用版本的d-ary)树放入一个连续的数组中,以广度优先的遍历顺序存储元素.以这种方式,来自树的相同级别的所有元素一个接一个地连续存储.
我正在实现一个数据结构,在引擎盖下,它是一个完全平衡的固定度d树,我想以连续的形式存储树以释放节点指针的空间.所以我想把节点放在堆中使用的广度优先顺序中,但后来我担心从根到叶子的典型搜索的缓存性能,因为在每个级别l,我跳过了很多元素.
有没有办法获得基于深度优先顺序的d-ary完整树的紧凑连续表示？
这样,在搜索叶子期间触摸的节点似乎更容易被发现彼此更接近.那么问题是如何检索节点的父节点和子节点的索引,但我也想知道在这个设置中树上的哪些操作通常是有效的.
我正在用C++实现这个东西,万一它很重要.
为简单起见,我将限制我的讨论到二叉树,但我所说的也适用于n-ary树.
堆(和一般的树)存储在数组广度优先的原因是因为以这种方式添加和删除项目要容易得多:增长和缩小树.如果您要存储深度优先,则必须以最大预期大小分配树,或者在添加级别时必须执行大量移动项.
但是如果你知道你将拥有一个完整,平衡的n-ary树,那么BFS或DFS表示的选择在很大程度上取决于风格.就内存性能而言,一方面没有任何特别的好处.在一个表示(DFS)中,您可以预先获取缓存未命中,而在另一种情况下(BFS),您可以在最后获取缓存未命中.
考虑具有20个级别(即2 ^ 20-1个项目)的二叉树,其包含从0到(2 ^ 20-1)的数字.每个节点占用四个字节(整数的大小).
使用BFS,当您获得树的第一个块时,会导致缓存未命中.但是,您在缓存中拥有树的前四个级别.因此,您的下三个查询将保证在缓存中.之后,当节点索引大于15时,保证会有缓存未命中,因为左子节点x*2 + 1距离父节点至少16个位置(64字节).
使用DFS,当您读取树的第一个块时,会导致缓存未命中.只要您搜索的数字位于当前节点的左子树中,就可以保证前15个级别不会出现缓存未命中(即您不断向左移动).但是任何正确的分支都会导致缓存未命中,直到你达到叶子上方的三个级别.此时,整个子树将适合缓存,您剩余的查询不会出现缓存未命中.
对于BFS,缓存未命中数与您必须搜索的级别数成正比.对于DFS,缓存未命中数与通过树的路径和您必须搜索的级别数成比例.但平均而言,搜索项目时发生的缓存未命中数对于DFS和BFS都是相同的.
计算节点位置的数学对于BFS来说比对DFS更容易,尤其是当您想要找到特定节点的父节点时.
| 归档时间： |
|
| 查看次数： |
626 次 |
| 最近记录： |