21

许多数据结构使用称为“左孩子，右兄弟”表示的表示将多路树存储为二叉树。这是什么意思？你为什么要使用它？

4

1 回答 1

77

左子右兄弟表示 (LCRS) 是一种使用二叉树（一种每个节点都可以最多有两个孩子）。

动机

为了激发这种表示的工作原理，让我们首先考虑一个简单的多路树，如下所示：

                   A
                 //|\ \
               / / | \  \
              B C  D  E  F
              |   /|\   / \
              G  H I J K   L

（为低质量的 ASCII 艺术品道歉！）

在这个树结构中，我们可以从树中的任何节点向下导航到它的任何子节点。例如，我们可以从 A 迁移到 B，A 迁移到 C，A 迁移到 D，等等。

如果我们想在这样的树中表示一个节点，我们通常会在这里使用某种节点结构/节点类（用 C++ 编写）：

struct Node {
    DataType value;
    std::vector<Node*> children;
};

在 LCRS 表示中，我们以每个节点最多需要两个指针的方式表示多路树。为此，我们将稍微重塑树。与其让树中的每个节点都存储指向其所有子节点的指针，不如让每个节点仅存储指向其子节点之一的指针（在 LCRS 中，最左边的子节点），以稍微不同的方式构造树。然后，我们将让每个节点存储一个指向其右兄弟节点的指针，即树中的下一个节点，它是同一父节点的子节点。在上述树的情况下，我们可以用以下方式表示树：

            A
           /
          /
         /
        B -> C -> D -> E -> F
       /         /         /
      G         H->I->J   K->L

请注意，在这个新结构中，仍然可以从父节点导航到其第 k 个子节点（零索引）。这样做的过程如下：

  • 下降到当前节点的左子节点。（这是其子节点列表中的第一个节点）。
  • 跟随那个孩子的右兄弟指针 k 次。（这会将您带到节点的第 k 个子节点）。
  • 返回那个节点。

例如，要找到根节点 A 的第三个（零索引子节点），我们将下降到最左边的子节点 (B)，然后跟随三个右链接（访问 B、C、D，最后是 E）。然后我们到达 E 的节点，它包含节点 A 的第三个子节点。

以这种方式表示树的主要原因是，即使任何节点可能有任意数量的子节点，该表示法最多需要每个节点两个指针：一个节点存储最左边的子节点，一个指针存储右边的兄弟节点。因此，我们可以使用更简单的节点结构来存储多路树：

struct Node {
    DataType data;
    Node* leftChild;
    Node* rightSibling;
};

该节点结构与二叉树中的节点形状完全相同（数据加上两个指针）。因此，LCRS 表示可以使用每个节点仅使用两个指针来表示任意多路树。

分析

现在让我们看看多路树的两种不同表示的时间和空间复杂度以及一些基本操作。

让我们首先查看初始“动态子数组”表示所需的总空间使用量。n 节点树的总内存使用量是多少？好吧，我们知道以下内容：

  1. 每个节点，无论其子节点的数量如何，都会为存储的原始数据 (sizeof(data)) 和动态数组的空间开销贡献空间。动态数组（通常）存储一个指针（指向分配的数组），一个机器字用于动态数组中的元素总数，以及（可选）一个机器字用于数组的分配容量。这意味着每个节点占用 sizeof(Data) + sizeof(Node *) + 2 * sizeof(machine word) 空间。

  2. 在树中的所有动态数组中，将有 n - 1 个指向子节点的指针，因为在树中的 n 个节点中，n - 1 个节点有父节点。这增加了一个额外的 (n - 1) * sizeof(Node *) 因子。

因此，总空间使用量为

n · (sizeof(Data) + sizeof(Node*) + 2 * sizeof(机器字)) + (n - 1) * sizeof(Node *)

= n * sizeof(Data) + (2n - 1) * sizeof(Node*) + 2n * sizeof(机器字)

现在，让我们将其与 LCRS 树进行对比。LCRS树中的每个节点存储两个指针（2 * sizeof(Node*)）和一个数据元素（sizeof(Data)），所以它的总空间是

n * sizeof(Data) + 2n * sizeof(Node *)

在这里我们看到了胜利：请注意，我们没有存储 2n * sizeof(machine word) 额外内存来跟踪分配的数组大小。这意味着 LCRS 表示比常规多路树使用的内存要少得多。

然而，对 LCRS 树结构的基本操作往往比它们在普通多路树上的相应操作花费更长的时间。具体来说，在以标准形式表示的多路树中（每个节点存储一个子指针数组），从一个节点导航到其第 k 个子节点所需的时间由跟随单个指针所需的时间给出。另一方面，在 LCRS 表示中，执行此操作所需的时间由跟随 k + 1 个指针（一个左子指针，然后是 k 个右子指针）所需的时间给出。因此，如果树具有较大的分支因子，则在 LCRS 树结构中进行查找比在相应的多路树结构中进行查找要慢得多。

因此，我们可以将 LCRS 表示视为在数据结构存储空间和访问时间之间提供时空权衡。LCRS 表示比原始多路树具有更少的内存开销，而多路树提供了每个子节点的恒定时间查找。

用例

由于 LCRS 表示中涉及时空权衡，除非两个标准之一成立，否则通常不使用 LCRS 表示：

  1. 内存极其稀缺，或
  2. 不需要随机访问节点的子节点。

如果您需要在主存储器中存储一个惊人的多路树，则可能会出现情况 (1)。例如，如果您需要存储一个系统发育树，其中包含许多需要频繁更新的不同物种，那么 LCRS 表示可能是合适的。

情况（2）出现在专门的数据结构中，其中树结构以非常特定的方式使用。例如，许多使用多路树的堆数据结构可以通过使用 LCRS 表示进行空间优化。主要原因是在堆数据结构中，最常见的操作往往是

  1. 移除树的根并处理它的每个子节点，或者
  2. 通过使一棵树成为另一棵树的孩子，将两棵树连接在一起。

操作 (1) 可以在 LCRS 表示中非常有效地完成。在 LCRS 表示中，树的根永远不会有右孩子（因为它没有兄弟姐妹），因此移除根仅意味着剥离根节点并下降到其左子树。从那里，可以通过简单地沿着剩余树的右脊柱并依次处理每个节点来处理每个子节点。

操作（2）也可以非常有效地完成。回想一下，在 LCRS 表示中，树的根永远不会有右孩子。因此，在 LCRS 表示中很容易将两棵树连接在一起，如下所示。从这样的两棵树开始：

    R1             R2
   /               /
 (children 1)    (children 2)

我们可以通过这种方式将树融合在一起：

             R1
            /
           R2
          /  \
(children 2) (children 1)

这可以在 O(1) 时间内完成，而且非常简单。LCRS 表示具有此属性的事实意味着许多类型的堆优先级队列，例如二项式堆或等级配对堆通常表示为 LCRS 树。

希望这可以帮助！

于 2012-12-23T23:30:46.947 回答