data-structures - 一棵树的左子，右兄弟是什么？你为什么要使用它？

Question

许多数据结构使用称为 "left-child, right-sibling" 表示的表示形式将多路树存储为二进制树。这是什么意思？你为什么要使用它？

Answer 1

左 child ，右同胞表示(LCRS)是一种使用 multi-way tree binary tree (每个节点可以在其中最多有两个 child )。

动机

为了激发这种表示的工作方式，让我们首先考虑一个简单的多向树，如下所示:

                   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个子节点(零索引)。这样做的过程如下:

下降到当前节点的左子节点。 (这是其子级列表中的第一个节点)。

跟随 child 的右兄弟指针k次。 (这将您带到节点的第k个子节点)。

返回该节点。

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

以这种方式表示树的主要原因是，即使任何节点可以具有任意数量的子代，该表示每个节点最多也需要两个指针:一个节点用于存储最左边的子节点，而一个指针用于存储右边的子节点。结果，我们可以使用更简单的节点结构存储多路树:

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

该节点结构具有与二叉树中的节点完全相同的形状(数据加两个指针)。结果，LCRS表示使得有可能使用每个节点仅两个指针来表示任意多路树。

分析

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

让我们从查看初始“ child 动态数组”表示形式所需的总空间使用开始。一个n节点树将有多少总内存使用量？好吧，我们知道以下几点:

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

在树中所有动态数组中，将有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表示在数据结构存储空间和访问时间之间提供了time-space tradeoff。与原始多路树相比，LCRS表示具有更少的内存开销，而多路树则为其每个子级树提供恒定时间的查找。

用例

由于LCRS表示涉及时空折衷，因此通常不使用LCRS表示，除非满足以下两个条件之一:

内存非常稀缺，或者

不需要随机访问节点的子代。

如果您需要在主内存中存储一​​个惊人的巨大多路树，可能会出现情况(1)。例如，如果您需要存储一个phylogenetic tree，其中包含许多频繁更新的不同物种，则LCRS表示可能是合适的。

情况(2)出现在特殊的数据结构中，其中以非常特定的方式使用树结构。例如，可以使用LCRS表示对使用多路树的许多类型的heap data structures进行空间优化。这样做的主要原因是，在堆数据结构中，最常见的操作往往是

删除树的根并处理其每个子级，或

将一棵树作为另一棵树的子节点，将两棵树连接在一起。

在LCRS表示中，操作(1)可以非常有效地完成。在LCRS表示中，树的根永远不会有一个正确的子节点(因为它没有 sibling )，因此删除根只是意味着剥离根节点并下降到其左子树中。从那里开始，可以通过简单地沿着其余树的右脊走并依次处理每个节点来完成对每个 child 的处理。

操作(2)也可以非常有效地完成。从上面回顾，在LCRS表示中，树的根永远不会有合适的子代。因此，很容易将LCRS表示中的两棵树连接在一起，如下所示。从这样的两棵树开始:

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

我们可以通过以下方式将树木融合在一起:

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

这可以在O(1)时间内完成，并且非常简单。 LCRS表示具有此属性的事实意味着许多类型的堆优先级队列(例如binomial heap或rank-pairing heap)通常表示为LCRS树。

希望这可以帮助!