c++ - 在不浪费空间的情况下将二叉搜索树存储在数组中的看似可行的算法

Question

在尝试理解二叉(搜索)树时，我偶然发现了 BST 是否可以有效地存储在平面数组中(即不浪费空间)的问题。在 google 和论坛(包括 SO)中搜索之后，我没有找到令我满意的东西。大多数人想要存储 BT(l=2*i+1，r=2*i+2)或接受这样一个事实，即节点的空子节点表示为nil 值(并像那样存储，不必要地占用空间)。

因此我编写了自己的算法，利用 BST 中的子节点具有特定排序属性的事实(小于根:left，大于根:right) .

为了存储 BST，我只是将它线性写入数组，深度优先。这发生在 O(n) 中，递归到树的子节点中。该数组正好是 n 个条目，n 是 BST 中的节点数。

为了从数组中重构 BST，我在遇到数组中的新条目时遵循两个规则:

• 下一个左节点(如果存在)是下一个比当前节点小的节点。

• 下一个正确的节点(如果存在)是下一个...

  • ...比现在的大
  • ... 上次分支 left 时不大于最小父键
  • ... 如果在父级的 left 分支中则小于父级

这也发生在 O(n) 中。

这对于非常非常大的随机结构树(只要它们是 BST)非常有效。实证测试从未显示出任何问题。我用 C++ 创建了一个工作代码示例 here , 两个转换函数为 toArray和 fromArray .

现在回答我的问题: 这是否概括？我害怕监督与此有关的关键问题。事实上，我在网上没有找到任何其他内容，这让我想知道是否

a) 我太笨了，找不到它，

b) 这是常识，没有人谈论它或

c) 这是完全错误的。

如果任何精通该主题的人能就此启发我，我将不胜感激。

非常感谢。

编辑:

在谷歌搜索更多并完全忽略数组细节后，我找到了几个有效的解决方案。最突出的一个(如 here 和 here 所解释的)是使用预序遍历存储 BST。

Answer 1

最终，我自己找到了解决方案。用于从 BST 深度优先创建的数组重建 BST 的技术基于预序遍历。

我找到了解决方案 here并在我自己的 BST 类中实现它 here .主要部分如下:

bool BinarySearchTree::fromArrayPreorderTraversal(std::vector<unsigned int> vecArray, unsigned int& unCurrentIndex, unsigned int unMin, unsigned int unMax) {
  bool bResult = false;

  if(unCurrentIndex < vecArray.size()) {
    unsigned int unVal = vecArray[unCurrentIndex];

    if(unVal > unMin && unVal < unMax) {
      bResult = true;
      this->setKey(unVal);
      unCurrentIndex++;

      if(unCurrentIndex < vecArray.size()) {
        if(!this->left(true)->fromArrayPreorderTraversal(vecArray, unCurrentIndex, unMin, unVal)) {
          this->setLeft(NULL);
        }

        if(!this->right(true)->fromArrayPreorderTraversal(vecArray, unCurrentIndex, unVal, unMax)) {
          this->setRight(NULL);
        }
      }
    }
  }

  return bResult;
}

这里，一个 BST 的形式:

      10
     /  \
    5    20
   / \     \
  2   7     30
 /
1

作为预序遍历数组可用:

10 5 2 1 7 20 30

父节点先出现，然后是左 child ，然后是右 child (递归)。这是 BST 的深度优先表示。

该算法获取键的有效范围以接受left或right侧的新节点作为参数(此处为unMin和unMax) 并基于此决定是否应创建节点。以这种方式重构了包括其原始结构在内的完整 BST。

这个(根据上面的引用)的时间复杂度是O(n)。由于没有空间被浪费，空间复杂度也是O(n)。

这个算法比我在问题中提出的算法要优雅得多。这似乎也是进行这种重建的一般方法。