Betternestedset talk - Oct 2006 - a bit of theory and vocabulary

Hi,

What does ''roots'' concept mean ?
In nested sets theory, we have one root for each tree.

Example:

menu (1,14)
   + Item 1 (2,3)
   + Item 2 (4,9)
      +SubItem1 (5,6)
      +SubItem2 (7,8)
   +Item3 (10,13)
      +SubItem 3 (11,12)

In some cases you want to store multiple trees in the same table (call 
it a forrest ;-)
The :scope is there to uniquely define one tree among the others.

Another problem is related to menus or forum entries (threaded), where 
the root is never used.
We could simply ignore it, and use root.children as displayed entries 
when all threads are closed.
To avoid storing this useless item, I propose to use directly main 
items/entries, and store them in the tree without any parent. (As if I 
dropped the ''menu'' node in the example above).

This gives:

(menu) = virtual root
+ Item 1 (1,2)
+ Item 2 (3,8)
    +SubItem1 (4,5)
    +SubItem2 (6,7)
+Item3 (9,12)
    +SubItem 3 (10,11)

If ''root'' means ''that has no parent'', Item
1, 2 and 3 are roots in this
case.
Of course it''s not a perfect name (though some indian trees like 
banians have multiple roots afaik :-)
but it leads to simpler code.

Maybe changing this name and use the concept of ''virtual root''
would be
better ?

We could have:

def virtual_root?
   last = self.find(:first, :order => ''rgt DESC'')
   # catch exceptions
   return last.lft != 1
end

and rename roots to branches ;-)

Jean-Christophe Michel
--
symetrie.com

Better Nested Set for rails:
http://opensource.symetrie.com/trac/better_nested_set