data-structures - 模拟 parking 场可用空间的数据结构

Question

考虑一个 parking 场，它可以分为以下层次。

                                Structure

            Level1               Level2                 Level3

       Row1   Row2   Row3    Row1  Row2   Row3      Row1   Row2   Row3

       1...N   1...N  1...N  1...N N....N  1....N  1.....N 1....N 1.....N

这里最底层是连续 1 到 N 个可用点。它非常类似于树数据结构，如果其中一个子树有可用空间，则每个节点都可以保存一个值 true ，如果所有子树都被占用，则可以保存 false 。然后下一行或在一个级别的情况下，检查下一个级别。现在我有以下问题:

1. 是否存在一种树状数据结构，它可以在不同级别具有不同数量的子节点，例如，级别 2 为 3，级别 3 为 N。
2. 如果这样的树是可能的，它的时间复杂度是多少？
3. 如果这样的树是不可能的，那么可以使用什么数据结构来表示这个层次结构。

Answer 1

从本质上讲，您的问题需要一棵树，该树在每一层都有任意数量的节点。这样的树可以使用左子右兄弟表示法来表示。在这种表示中，您拥有以下指针，而不是二叉树通常的左右子指针。

1. Left-child:这个指针指向一个节点的最左边的 child 。如果没有 child ，则为空。
2. 右兄弟节点:该指针指向紧靠给定节点右侧(在同一级别)的节点。如果给定节点是最右边的节点本身，则为空。

以上表示允许使用 n 个节点的 O(n) 空间来表示任意树。有关详细信息，请参阅 here .

否则，您也可以使用简单的 (C++) 向量或链表在每个节点存储任意数量的子指针。当然，这比左子右兄弟表示需要更多的内存，但同时，就访问特定节点时处理的节点而言，这更快。