One more Nested Intervals encoding

June 20, 2008


Dan Hazel developed one more version of continued fraction tree encoding. It is equivalent to matrix based approach with atomic matrices of the kind

[n + 1 n]
[ ]
[ 1 1]

but should be appealing to the readers who find continued fractions more intuitive compared to matrices.

Here is matrix perspective to his work. The atomic matrix in the foundation of Dan’s approach is

[n + 1 n]
[ ]
[ 1 1]

It has determinant equal to one, therefore general path determinants are not alternating, and nested interval orientation does not change when we ascend to the next tree level. Each Dan’s atomic matrix is a product of the familiar atomic matrix

[n 1]
[ ]
[1 1]

with an auxiliary matrix

[1 1]
[ ]
[1 0]

This is why Dan’s continued fractions contain interleaving sequences of 1s.

About these ads

One Response to “One more Nested Intervals encoding”

  1. Greg Lamoree Says:

    Do you have the relevant SQL for this including: inserting nodes, deleting nodes, selecting ancestors, selecting descendants?

    I have read your articles and purchased your book, but even with the errata, there seems to be flaws in the SQL.

    I am trying to implement this variant you site by Dan Hazel, but am unable to determine the correct SQL.

    Your help would be much appreciated.

    Thank you.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: