什么是左儿子右兄弟表示法？为什么要使用它？

Question

什么是左儿子右兄弟表示法？为什么要使用它？

data-structurestreebinary-treemultiway-tree

24

许多数据结构使用一种叫做"左孩子，右兄弟"的表示法将多叉树存储为二叉树。这意味着什么？为什么要使用它？

- templatetypedef

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

左儿子右兄弟表示法（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个子节点（从0开始）。执行此操作的过程如下：

进入当前节点的左子节点。（这是其子节点列表中的第一个节点）。
跟随该子节点的右兄弟指针k次。（这将带您到节点的第k个子节点）。
返回该节点。

例如，要查找根节点A的第三个（从0开始计数的子节点），我们将下降到最左侧的子节点（B），然后跟随三个右链接（访问B、C、D，最后是E）。然后我们到达E节点，它保存节点A的第三个子节点。

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

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

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

分析

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

首先，让我们看一下“动态子节点数组”表示法所需的总空间使用情况。对于一个n个节点的树，总内存使用量是多少？我们知道以下内容：

每个节点，无论其子节点数量如何，都会为存储的原始数据（sizeof(data)）和动态数组的空间开销（space overhead）贡献空间。动态数组（通常）存储一个指针（指向分配的数组），一个机器字（表示动态数组中元素的总数），以及（可选的）一个机器字（表示数组的分配容量）。这意味着每个节点占用 sizeof(Data) + sizeof(Node *) + 2 * sizeof(machine word) 的空间。
在树的所有动态数组中，将有 n-1 个指向子节点的指针，因为在树的 n 个节点中，n-1 个节点有父节点。这增加了额外的 (n-1) * sizeof(Node *) 因素。

因此，总空间使用量为

n · (sizeof(Data) + sizeof(Node*) + 2 * sizeof(machine word)) + (n - 1) * sizeof(Node *)

= n * sizeof(Data) + (2n - 1) * sizeof(Node*) + 2n * sizeof(machine word)

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

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

这就是我们看到的胜利：请注意，我们没有存储2n * sizeof（机器字）额外的内存来跟踪分配的数组大小。这意味着LCRS表示法使用的内存比常规多路树少得多。

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

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

用例

由于LCRS表示法涉及时间-空间权衡，通常情况下不使用LCRS表示法，除非满足以下两个条件之一：

内存极度稀缺，或者
不需要随机访问节点的子节点。

如果您需要在主内存中存储一个巨大的多路树，可能会出现情况（1）。例如，如果您需要存储一个包含许多不同物种的系统发育树，并经常更新，则LCRS表示法可能是适当的。

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

删除树的根并处理其每个子节点，或者
通过使一棵树成为另一棵树的子节点来合并两棵树。

在LCRS表示中，操作（1）可以非常高效地完成。在LCRS表示中，树的根节点永远没有右子节点（因为它没有兄弟姐妹），因此删除根节点只意味着剥离根节点并进入其左子树。从那里，通过简单地沿着剩余树的右脊走下去并依次处理每个节点即可处理每个子节点。

操作（2）也可以非常高效地完成。回想一下上面提到的，在LCRS表示中，树的根节点从不具有右子节点。因此，可以按照以下方式轻松地将两棵LCRS表示的树连接在一起。从这样的两棵树开始：

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

我们可以这样将树融合在一起：

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

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

希望这可以帮助！