Yet another tree labeling

From: Vadim Tropashko <vadimtro_at_yahoo.com>
Date: 15 Sep 2003 17:26:34 -0700
Message-ID: <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 - 02:26:34 CEST