用于模拟停车场空间可用性的数据结构

Question

考虑一个停车场，它可以分成以下层次结构。

                                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. 是否存在一种树形数据结构，不同层级可以有不同数量的子节点，例如第二层有3个，第三层有N个。
2. 如果这样的树形结构是可能的，它的时间复杂度是多少？
3. 如果这样的树形结构不可能，可以使用什么数据结构来表示这种层次结构。

- Meena Chaudhary

---

你可以通过一个简单的树来实现，就像你建议的那样，其中在最坏情况下找到车位和移除车辆将需要O(h)的时间，其中h是树中节点的最大深度。 - advocateofnone

@sasha 但是我该如何表示每一行的位置数量与每个级别的行数不同呢？ - Meena Chaudhary

你的层次结构只有深度为3吗（意思是每个层级有R行，每行有N个插槽，共L个层级）？ - Anudeep Gade

Answer 1

回答你的问题：

1. 是的，您可以根据您的要求实现基于树的结构。数据结构应该像这样：

   public abstract class ParkingLotTreeNode {
       private ParkingLotTreeNode [] childNodes;
   
   }
   

   这样，每个节点都包含其子节点的数组，这样您就可以为停车场拥有任意数量的级别和行。

2. 使用上述基本方法，找到停车位的最坏情况将是停车场中停车位的总数，这不是找到空闲插槽的好解决方案。

   可以进行改进，存储一个布尔标志，当特定的子项所有停车位都被占满时设置该标志。在每个节点上，我们将有一个表示其子节点是否有任何剩余空位的标志。

   public abstract class ParkingLotTreeNode {
       private ParkingLotTreeNode [] childNodes;
       private Boolean isFull = false;
   }
   

   这样，查找空闲插槽将在相对较短的时间内完成，因为我们事先知道哪些级别/行已经满了，不会被遍历。

希望这能帮到你！

- ssadaqat

Answer 2

实际上，您的问题需要一个每个级别具有任意数量节点的树。这样的树可以使用左孩子，右兄弟表示法来表示。与二叉树的通常左右孩子指针不同，在这种表示法中，您有以下指针。

1. 左孩子：此指针指向节点的最左侧子节点。如果没有子节点，则为空。
2. 右兄弟：此指针指向给定节点右侧的节点（在同一级别上）。如果给定节点本身是最右侧节点，则为空。

上述表示法允许使用O(n)空间来表示任意树形结构，其中n为节点数。详情请参见此处。

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

- gjain