基于深度优先顺序而不是宽度优先，我可以为完整树构建类似堆的连续布局吗？

4 回答

• 1

  为简单起见，我将限制我的讨论到二叉树，但我所说的也适用于n-ary树 .

  堆（和一般的树）存储在数组广度优先的原因是因为以这种方式添加和删除项目要容易得多：增长和缩小树 . 如果您要存储深度优先，则必须以最大预期大小分配树，或者在添加级别时必须执行大量移动项目 .

  但是如果你知道你将拥有一个完整， balancer 的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更容易，尤其是当您想要找到特定节点的父节点时 .

  回复于 2024-05-03T12:09:47+08:00
• 1

  看来需要一个 is_leaf 指标 . 因为大多数事物都与级别相关，所以我们需要快速找到它，这似乎取决于知道节点是否是叶子 .

  下面的片段也假设节点相对于父节点的位置是已知的...它不漂亮而且几乎无用，因为整点是节省空间 .

  int parent_index(int index, int pos){
    if (pos == LEFT){
      return i-1;
    } else {
      return i - pow(2,num_levels - level(i));
    }
  }
  
  int left_child_index(int index){
    return i+1;
  }
  int right_child_index(int index){
    return i+pow(2,num_levels - level(index))
  }
  

  要获得节点的级别，您可以走左边的孩子，直到你到达一片叶子 .

  树形凹凸之间的差异似乎类似于Pascal的三角形 - 所以这也可能有用 .

  回复于 2024-05-03T12:09:47+08:00
• 1

  我只是想了一下 .

  中缀订单怎么样？这样一切都更容易计算：

  bool is_leaf(unsigned int i){
    return !(i%2);
  }
  
  unsigned int left_child(unsigned int i){
    return i - pow(2,num_levels - level(i));
  }
  unsigned int left_child(unsigned int i){
    return i + pow(2,num_levels - level(i));
  }
  
  int level(unsigned int i){
    unsigned int offset = 1;
    unsigned int level_bits = 1;
    int level = 0;
    while ((i - offset)&level_bits == 0){
      level++;
      offset += pow(2,level);
      level_bits = (level_bits << 1) + 1; /* should be a string of trailing 1s */
    }
    return level;
  }
  

  这样你只能在最顶层的节点上获得大跳跃 . 之后，跳跃呈指数级变小 . 这样做的好处在于，由于较低级别的节点较少，因此可以缓存这些节点 . 在树更密集的地方（即更多的同伴），跳跃要小得多 .

  退回是插入缓慢：

  void insert_node(node[] node_array, node new_node){
    for (unsigned int i = num_nodes-1; i >= 0; i--){
      node_array[i*2 + 1] = node_array[i];
      node_array[i] = NULL_NODE_VALUE; /* complete (but not full) trees are discontiguous */
    }
    node_arry[0] = new_node;
  }
  

  这个中缀顺序无疑比前缀（深度优先搜索）顺序要好得多，因为树在逻辑上和物理上都是“ balancer 的” . 在前缀顺序中，左侧更受青睐 - 所以它会有所表现无论如何，像一棵不 balancer 的树 . 至少使用中缀，您可以在密集节点之间进行 balancer 和快速搜索 .

  回复于 2024-05-03T12:09:47+08:00
• 8

  二进制搜索树用于存储以后可以有效查询和排序的信息 . 任何特定节点的左节点包含的值小于该节点的值，右节点包含更大的值 .

  Heap is efficient implementation of almost complete binary search trees?

  除了由特定节点表示的数据值之外，二进制搜索树还需要至少两个其他指针（因为它们也可以是父指针） . 基于堆的结构通过利用几乎完整的BST的属性将这些指针操作转换为数组索引操作 . 我们也知道如果特定的BST不接近几乎完整的BST，我们在该二叉树的数组表示中创建漏洞，以便维持父节点和子节点之间的关系 . 这意味着这可以抵消在这种情况下使用指针的成本 .

  Implement heap like structure based on depth first order of tree traversal?

  通过尝试为树的深度一阶遍历实现堆状结构，我们不再能够证明在第一时间使用堆的原因 . 因为，与树的宽度（可以在给定树几乎完全BST的特定级别计算）相比，深度不是固定的，我们必须操纵元素之间的复杂关系 . 每当在树中添加/删除新元素时，我们还必须重新排列元素，以便它们仍然满足堆的属性 . 因此，如果以这种方式实现，我认为我们不能证明使用堆超过BST是合理的 .

  回复于 2024-05-03T12:09:47+08:00