Differenza tra elenchi fratelli, albero binario fratello destro e figlio destro e albero doppiamente incatenato

Question

Differenza tra elenchi fratelli, albero binario fratello destro e figlio destro e albero doppiamente incatenato

#1 da (0 voti)

2

La pagina Wikipedia per gli alberi dei suffissi riporta gli elenchi dei fratelli come

Each node has a pointer to its first child, and to the next node in the child list it is a part of.

Wikipedia descrive alberi binari di sinistra fratello di destra nel modo seguente:

Then, starting with the root, each node's leftmost child in the original tree is made its left child in the binary tree, and its nearest sibling to the right in the original tree is made its right child in the binary tree.

Infine, secondo Wikipedia, gli alberi doppiamente incatenati hanno la seguente proprietà:

In a doubly-chained tree, each node has two pointers, one to the node's first child and one to its next sibling.

Per me, queste tre definizioni sono esattamente le stesse. C'è una differenza?

trees binary-tree suffix-trees

posta Markus Himmel 03.04.2015 - 18:13

fonte

1 risposta

Leggi altre domande sui tag trees binary-tree suffix-trees

Active Directory Federation per multi-tenant Che algoritmo è questo?

score 0 · Accepted Answer

Per quanto posso dire, l'implementazione di un "albero gemello" di un albero suffisso, un "albero binario di destra fratello sinistro" e un "albero doppiamente incatenato" sono tutti esattamente la stessa struttura dati .

Fonte 1: La voce del dizionario NIST degli algoritmi e delle strutture dati per " rappresentazione ad albero binario degli alberi "afferma che questo è

Also known as first child-next sibling binary tree, doubly-chained tree, filial-heir chain.

Fonte 2: esiste in realtà un libro di Wikipedia chiamato Strutture di dati che - almeno nell'anteprima di Google books - contiene la seguente frase:

This binary tree representation of a general order tree, is sometimes referred to as a First-Child/Next-Sibling binary tree, or a Double-chained tree, or a Filial-Heir chain.

Fonte 3: Queste diapositive di un corso CS universitario si riferiscono a questo come albero

1st Child / Next Sibling List Representation

Quindi penso che sia ragionevole concludere che si tratta semplicemente di una struttura dati con molti nomi diversi.

P.S. Non ho trovato alcuna fonte oltre a quella stub di Wikipedia che usa un nome con "right-sibling", quindi è possibile che i nomi "next-sibling" siano più comuni / standard (e mi sembrano più intuitivi).