什么是树的左子,右兄弟代表？你为什么要用它？

Question

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

Answer 1

左子,右兄弟表示(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(数据))和动态数组的空间开销提供空间.动态数组(通常)存储一个指针(指向分配的数组),一个机器字表示动态数组中元素的总数,(可选)一个机器字表示分配的数组容量.这意味着每个节点占用sizeof(Data)+ sizeof(Node*)+ 2*sizeof(机器字)空间.

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

因此,总空间使用量是

n·(sizeof(数据)+ sizeof(节点*)+ 2*sizeof(机器字))+(n - 1)*sizeof(节点*)

= n*sizeof(数据)+(2n - 1)*sizeof(节点*)+ 2n*sizeof(机器字)

现在,让我们将其与LCRS树进行对比.LCRS树中的每个节点都存储两个指针(2*sizeof(Node*))和一个数据元素(sizeof(Data)),因此它的总空间是

n*sizeof(数据)+ 2n*sizeof(节点*)

在这里我们看到胜利:注意我们没有存储2n*sizeof(机器字)额外内存来跟踪分配的数组大小.这意味着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树.

希望这可以帮助!