Generating binary and ternary trees in teh neste4d sets model
- From: -CELKO- <jcelko212@xxxxxxxxxxxxx>
- Date: 7 May 2007 12:40:14 -0700
Bear with me and the set up for the problem.
There are many ways to represent a tree or hierarchy in SQL. This is
called an adjacency list model and it looks like this:
CREATE TABLE OrgChart
(emp_id CHAR(10) NOT NULL PRIMARY KEY,
boss_emp_id CHAR(10) REFERENCES OrgChart(emp_id),
salary_amt DECIMAL(6,2) DEFAULT 100.00 NOT NULL,
<< horrible cycle constraints >>);
OrgChart
emp_id boss_emp_id salary_amt
==============================
'Albert' NULL 1000.00
'Bert' 'Albert' 900.00
'Chuck' 'Albert' 900.00
'Donna' 'Chuck' 800.00
'Eddie' 'Chuck' 700.00
'Fred' 'Chuck' 600.00
Another way of representing trees is to show them as nested sets.
Since SQL is a set oriented language, this is a better model than the
usual adjacency list approach you see in most text books. Let us
define a simple OrgChart table like this.
CREATE TABLE OrgChart
(emp_id CHAR(10) NOT NULL PRIMARY KEY,
lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1),
CONSTRAINT order_okay CHECK (lft < rgt));
OrgChart
emp_id lft rgt
======================
'Albert' 1 12
'Bert' 2 3
'Chuck' 4 11
'Donna' 5 6
'Eddie' 7 8
'Fred' 9 10
The organizational chart would look like this as a directed graph:
Albert (1, 12)
/ \
/ \
Bert (2, 3) Chuck (4, 11)
/ | \
/ | \
/ | \
/ | \
Donna (5, 6) Eddie (7, 8) Fred (9, 10)
Math majors will recognize this as a preorder tree traversal in a thin
disguise. To convert a nested sets model into an adjacency list
model:
SELECT B.emp_id AS boss_emp_id, E.emp_id
FROM OrgChart AS E
LEFT OUTER JOIN
OrgChart AS B
ON B.lft
= (SELECT MAX(lft)
FROM OrgChart AS S
WHERE E.lft > S.lft
AND E.lft < S.rgt);
If I have a complete binary tree, I can use a heap model to build it.
In that model you number the nodes from left to right as you go down
the tree.
1
/\
2 3
/ \ / \
4 5 6 7
A complete tree of depth (n) has (2^n -1) nodes. The left child of a
node (n) is (2*n) and right child is (2*n +1). The parent of a node
(n) is FLOOR(n/2). You can use a loop to traverse this tree with
those formulas, or do a little more algebra and get closed forms. You
can now locate a path without materializing the entire tree.
The same pattern applies to a ternary tree
1
/ | \
2 3 4
/|\ /|\ /|\
5 6 7 8 9 1 1 1 1
0 1 2 3
You get the same sort of pattern, but in 3's and not 2's. Each level
starting at root level = 0) ends with (3^n +1) on the right hand
side. The middle child of node (n) is (3*n), so the left child is
(3*n-1) and the right child is (3*n+1).
Using SQL and avoiding procedural code, if possible:
1) Is there a simple way to generate a nested sets model of a complete
binary tree of any depth?
2) Is there a simple way to generate a nested sets model of a complete
ternary tree of any depth?
3) Is there a simple way to generate a nested sets model of a complete
n-ary tree of any depth?
.
- Prev by Date: Re: more closed-world chatter
- Next by Date: Re: more closed-world chatter
- Previous by thread: Self Joins and optimization
- Next by thread: how different indexing techniques work as dimensionality increases?
- Index(es):
Relevant Pages
|
