Re: Yet another tree labeling

Excellent. However, as I have project meeting this afternoon to discuss my technical specification for our project, I am still not sure whether to recommend Materialized Path or Adjacency List - perhaps you could flesh it out a little more before then ;) ?

"Vadim Tropashko" <vadimtro_at_yahoo.com> wrote in message news:22d2e427.0309151626.116ba0d5_at_posting.google.com...
> We label each tree node with a single positive integer number. This
> labeling is closely related to binary rational interval labeling
> defined in http://www.dbazine.com/tropashko4.html
>
> Given natural number N, let k be maximal integer satisfying 2^k <= N.
> In other words
>
> k = floor(log(2,N))
>
> We define mapping between binary rational interval labeling (x,y) and
> N as follows:
>
> y+(1-x) = 1 - 1/2^(k+1)
>
> 1-x = (N-2^k)/2^k
>
> For example, the node "1.4" or <x=9/16, y=17/32> corresponds to N=23.
>
> The nice property of single integer labeling is very simple definition
> of transitive closure relation. Given 2 nodes i and j such that i <= j
> let k' be maximal integer satisfying i*2^k' <= j. Consider binary
> relation "le" satisfying
>
> i "le" j <=> j-i*2^k' < i*2^(k'-1)/j or i = j.
>
> Here is implementation as a distance function
>
> CREATE or replace
> function dist ( child integer, parent integer )
> RETURN integer IS
> ret integer;
> arifgeom integer;
> pwr integer;
> BEGIN
> if parent > child then
> RETURN -1;
> end if;
> if parent = child then
> RETURN 0;
> end if;
> arifgeom := parent;
> pwr := 0;
> while arifgeom*2 <= child loop
> arifgeom := arifgeom*2;
> pwr := pwr+1;
> end loop;
> if child-arifgeom < arifgeom/(parent*2) then
> RETURN pwr;
> end if;
> RETURN -1;
> END;
> /
>
> select dist(11,3), dist(12,3), dist(13,3), dist(14,3) from dual
> -1 2 2 -1
>
> In other words the function returns distance between parent and child
> in the tree or -1 if child is not reacheable from parent.
>
> I'll submit more readable version to dbazine.com (with pictures!)
Received on Tue Sep 16 2003 - 12:38:03 CEST