Re: Other tree representations in SQL

From: Damjan S. Vujnovic <damjan_at_NOSPAMgaleb.etf.bg.ac.yu>
Date: Wed, 4 Dec 2002 20:32:26 -0800
Message-ID: <asll8m$b1m$1_at_news.etf.bg.ac.yu>

I'm still working on the solution when representing binary trees with

(inorder_traversal_sequence_number, level)

but in the meantime, consider the following representation of binary trees when each node is represented with the number (index) according to the following scheme:

                              01
              02                              03
      04              05              06              07
  08      09      10      11      12      13      14      15

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

From now on, we'll call those number indexes. So, the tree:

    a
b c
  d e f

         g h

would be represented with:

INSERT INTO Tree(node, indx) VALUES('a', 1);
INSERT INTO Tree(node, indx) VALUES('b', 2);
INSERT INTO Tree(node, indx) VALUES('c', 3);
INSERT INTO Tree(node, indx) VALUES('d', 5);
INSERT INTO Tree(node, indx) VALUES('e', 6);
INSERT INTO Tree(node, indx) VALUES('f', 7);
INSERT INTO Tree(node, indx) VALUES('g', 14);
INSERT INTO Tree(node, indx) VALUES('h', 15);

Getting the parent of a given child is trivial:

SELECT *, :my_child
 FROM Tree
 WHERE indx

• (SELECT FLOOR(indx/2) AS parent FROM Tree T1 WHERE T1.node = :my_child)

Finding a subtree rooted at a particular node is a little bit complicated. Note that indexes of child nodes of a node with index n are:

 2*n,       2*n+1
 4*n, ...,  4*n+3
 8*n, ...,  8*n+7
16*n, ..., 16*n+15

...

so, the node with index s is a child of a node with index n if and only if exists k such that:

(2^k)*n <= s < (2^k)*n + 2^k

Math says that is such k exists, then (log's base is 2):

k=FLOOR(log(s/n))

In other words if:

s < [2^FLOOR(log(s/n))]*n + 2^FLOOR(log(s/n))

then the node with index s is a child of a node with index n. Example:

n=3, s=13
13 < (2^2)*3 + (2^2)
TRUE n=2, s=12
12 < (2^2)*2 + (2^2)
FALSE In SQL (I know that log is natural logarithm, but log2 can be expressed using it):

SELECT :my_root, T1.*
  FROM Tree T1, Tree T2
 WHERE T2.node = :my_root AND

       T1.indx < POWER(2,FLOOR(log(T1.indx/T2.indx)))*n + POWER(2,FLOOR(log(T1.indx/T2.indx)))

Well, that's it. Of course it can be generalized for n-ary tree, but if maximum n is known in advance. We could improve it's performance by adding node level too...

regards,
Damjan S. Vujnovic

University of Belgrade
School of Electrical Engineering
Department of Computer Engineering & Informatics Belgrade, Yugoslavia

http://galeb.etf.bg.ac.yu/~damjan/ Received on Thu Dec 05 2002 - 05:32:26 CET