Question

The Wikipedia page for suffix trees descibes sibling lists as

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

Wikipedia describes left-child right-sibling binary trees in the followeing manner:

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.

Lastly, acoording to Wikipedia, doubly-chained trees have the following property:

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

To me, these three definitions are exactly the same. Is there a difference?

Was it helpful?

Solution

As far as I can tell, a "sibling list" implementation of a suffix tree, a "left-child right-sibling binary tree" and a "doubly-chained tree" are all exactly the same data structure.

Source 1: The NIST Dictionary of Algorithms and Data Structures entry for "binary tree representation of trees" states that this is

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

Source 2: There is actually a Wikipedia book called Data Structures which--at least in the Google books preview--contains the following sentence:

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.

Source 3: These slides from a university CS course refer to this as a tree's

1st Child / Next Sibling List Representation

So I think it's reasonable to conclude that this is simply one data structure with a lot of different names.

P.S. I couldn't find any sources besides that Wikipedia stub which use a name with "right-sibling", so it's possible that "next-sibling" names are more common/standard (and they do seem more intuitive to me).

Licensed under: CC-BY-SA with attribution
scroll top