Generating binary and ternary trees in teh neste4d sets model

From: -CELKO- <jcelko212_at_earthlink.net>
Date: 7 May 2007 12:40:14 -0700
Message-ID: <1178566814.931738.222970_at_l77g2000hsb.googlegroups.com>

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?

Received on Mon May 07 2007 - 21:40:14 CEST