看似可行的算法，用于在数组中存储二叉搜索树而不浪费 space

Question

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

所以我编写了自己的算法，利用 BST 中的子节点具有特定顺序的事实属性（小于根：left，大于根：right） .

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

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

下一个左节点（如果存在）是下一个比当前节点小的节点。
下一个正确的节点（如果存在）是下一个...
- ...比现在的大
- ...最后一次分支时不大于最小父键left
- ...如果在父项的 left 分支

这也发生在 O(n)。

这对于非常非常大的随机结构树（只要它们是 BST）非常有效。实证测试从未显示出任何问题。我用 C++ here, the two conversion functions being toArray and fromArray.

制作了一个工作代码示例

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

a)我太笨没找到,

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

c) 完全错了

非常感谢任何精通该主题的人在这方面启发我。

已经非常感谢了。

编辑：

在 google 更多并完全忽略数组细节之后，我找到了几个有效的解决方案。最突出的一个（如 here and here 所解释的）是使用预序遍历存储 BST。

Answer 1

最终，我自己找到了解决方案。用于从 BST depth-first 创建的数组重建 BST 的技术基于 pre-order 遍历。

我找到了解决方案 here and implemented it in my own BST class 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

可用作pre-order遍历数组：

10 5 2 1 7 20 30

parent节点在前，然后是左child，然后是右child（递归）。这是 BST 的 depth-first 表示。

该算法获取 left 或 right 端的新节点接受的密钥的有效范围作为参数（此处为 unMin 和 unMax）和基于此，决定是否应该创建节点。完整的 BST 包括它的原始结构就是这样重建的。

这个（根据上面的参考）的时间复杂度是O(n)。由于没有 space 被浪费，space 的复杂度也是 O(n)。

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

看似可行的算法，用于在数组中存储二叉搜索树而不浪费 space

Seemingly working algorithm for storing a binary search tree in an array without wasting space

c++

arrays

algorithm

serialization

binary-search-tree