help with celko's tree model

[Nick Chan]

hello i have implemented joe celko's model to store heirarchy and it
works well and nice
i have a question about SQL

this is the actual table

member side left right
------------------------------------------
nancy L 1 36
andrew L 4 21
steven R 5 12
ina L 6 7
david R 10 11
margaret L 13 20
ann R 14 15
laura L 18 19
janet R 24 35
michael L 25 30
dan R 26 27
ron L 28 29
robert R 33 34
the Side column is to tell its left, or right. this is a binary
heirarcy.
i have this problem i have to solve, im still banging my head. If
given the member

'Nancy' , i need to find left-most(Laura) and right-most(Robert)
'Janet' = left most is ron, right most is robert
'Andrew = left most is laura, right most is David
Hope u get my plan. could u help me with the sql ?

[Hugo Kornelis]

On 24 Oct 2004 23:04:40 -0700, Nick Chan wrote:

hello i have implemented joe celko's model to store heirarchy and it
works well and nice (snip)the Side column is to tell its left, or right. this is a binary
heirarcy.
Hi Nick,

You seem to have a slight misunderstanding about Joe Celko's nested set
model. A bit of googling got me this quote (from a message in another
newsgroup, written by Joe Celko himself):

"The nested set model has an implied ordering of siblings which
the adjacency list model does not."

From the context, it was clear that Joe meant that for each pair of
siblings, the one with the lower lft and rgt values should be considered
to be to the left of the one with the higher lft and rgt values.

I've drawn a picture of your hierarchy with the "left" descendant always
on the left side and the "right" descendant always on the right side; then
I re-assigned the lft and rgt numbers according to Joe Celko's nested set
model. The result looks like this:

member lft rgt
-------------------------
nancy 1 26
andrew 2 15
margaret 3 8
laura 4 5
ann 6 7
steven 9 14
ina 10 11
david 12 13
janet 16 25
michael 17 22
ron 18 19
dan 20 21
robert 23 24

i have this problem i have to solve, im still banging my head. If
given the member

'Nancy' , i need to find left-most(Laura) and right-most(Robert)
'Janet' = left most is ron, right most is robert
'Andrew = left most is laura, right most is David

After re-arranging the lft and rgt values as above, it's not too hard
anymore:

SELECT o.member AS member, l.member AS leftmost, r.member AS rightmost
FROM hierarchy AS o
INNER JOIN hierarchy AS l
ON l.rgt = (SELECT MIN(rgt)
FROM hierarchy
WHERE lft BETWEEN o.lft AND o.rgt)
INNER JOIN hierarchy AS r
ON r.lft = (SELECT MAX(lft)
FROM hierarchy
WHERE lft BETWEEN o.lft AND o.rgt)
WHERE o.member IN ('nancy', 'janet', 'andrew')
Best, Hugo
--

(Remove _NO_ and _SPAM_ to get my e-mail address)

[--CELKO--]

>> I have implemented Joe Celko's model to store heirarchy and it
works well and nice I have a question about SQL <<

You might want to buy a copy of my book TREES & HIERARCHIES IN SQL :)

This is the actual table .. the Side column is to tell its left, or right. This is a binary heirarchy. <<

I have a better model for binary trees! Remember "heapsort" from your
first data structures/algorithms class in college?

CREATE TABLE Heap
(member CHAR(15) NOT NULL,
place INTEGER NOT NULL PRIMARY KEY
CHECK(place > 1);

root = 1
place of left child of member (n) = (2*n)
place of right child of member (n) = (2*n +1)

Use integer division to travel toward the root of the tree.

('Somebody', 2, 3) is missing in the data you posted, but it looks
like ('nancy', 1) is the root of the tree.
'Nancy', I need to find left-most(Laura) and right-most(Robert) <<

Is this correct? I keep going left (or right) until I get to a leaf
node in the tree or to a node without a left (or right) child:

A
/ \
/ \
B C
/ \
/ \
D E

leftmost(A) = B
rightmost(A) = E
leftmost(C) = D
rightmost(C) = E
leftmost(D) = NULL
rightmost(D) = NULL

So the leftmost(n) member is MAX(2* .. (2*n) ..) if the whole
generated set is in the heap. The rightmost(n) member is MAX(2* ..
(2*n+1) ..+1) +1) if the whole generated set is in the heap.

You can use a loop, recursion or a look-up table for the math.

[Vaxman]

Saw the first part of your question on experts-exchange and asked a
buddy of mine (Corey Aldebol) how his tree model would work for your
problem. Take a look here for his reply:
http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=41772

*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!