Re: double linked list

"--CELKO--" <71062.1056_at_compuserve.com> wrote in message news:c0d87ec0.0302091835.5d250030_at_posting.google.com...
>> >> Granted, but you also lose the ability to order the children, to
>> >> separate the tree structure from the nodes (organizational chart
>> >> versus personnel)
> >> I don't follow here. <<
>
> In a nested set model, the (lft, rgt) pairs are ordered, so I have a
> left-most (oldest) child, a right-most (youngest) child and an
> ordering of the sibling in between.

I understand the ordering. I don't understand "separate the tree structure from the nodes".

> >> there only one adjacency list model. <<
>
> Two.
>
> Albert
> / \
> / \
> Bert Chuck
> / | \
> / | \
> / | \
> / | \
> Donna Eddie Fred
>
>
> CREATE TABLE Parent_Down_Tree
> (parent_id CHAR (8), -- null means child is the root
> child_id CHAR(8) NOT NULL);
>
> parent child
> ======================
> NULL 'Albert'
> 'Albert' 'Bert'
> 'Bert' 'Chuck'

'Albert' 'Chuck' ?

> 'Chuck' 'Donna'
> 'Chuck 'Eddie'
> 'Chuck' 'Fred'
>
> CREATE TABLE Child_Up_Tree
> (parent_id CHAR (8) NOT NULL,
> child_id CHAR(8)); -- null means child is a leaf
>
> parent child
> ======================
> 'Albert' 'Chuck'
> 'Albert' 'Bert'
> 'Bert' NULL'
> 'Donna' NULL
> 'Eddie' NULL
> 'Fred' NULL

I don't agree.

First, there are missing links in your data. Whose child is Donna, for example?

Second, if you reorganize the model into 2 tables: nodes and linkes, then there would be no difference between both your representations (and plus, there would be no NULLs). Essentially, we are talking about "poles and spaces" counting problem. We can relate each pole to the space before, or after it.

Third, for arbitrary graphs you can't merge nodes and links into the same table anymore.

There is only one adjacency model simply because there is only one adjacency matrix definition in graph theory. The fact that we can consider transposed adjacency matrix too is not important. Received on Mon Feb 10 2003 - 18:05:50 CET