A little research clarified what we see here: apparently it's part of the definition of a binary tree that the left node be smaller than its parent but the right one is greater. Right away, I see a problem for the predecessor-index representation of a tree that I'm advocating as it does not distinguish between right and left nodes as it is usually implemented.
On Mon, Sep 8, 2014 at 3:03 PM, Devon McCormick <devon...@gmail.com> wrote: > Do you have a reference to a good example of this? Looking at the > "before" and "after" pictures on the right here - > http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree - the > rebalancing seems arbitrary as it preserves some relations but changes > others. > > > On Mon, Sep 8, 2014 at 2:30 PM, Dan Bron <j...@bron.us> wrote: > >> Raul wrote: >> > Note that J already supports trees. >> >> Devon wrote: >> > I have J code that uses trees which I run daily and >> > have been doing so for years. >> >> Pascal wrote: >> > I think trees are done at least ok, if not "right" already. >> >> Challenge: express, in J, the logic of rebalancing a heap (say, a >> Fibonacci >> heap, but I'm not particularly picky). >> >> For the sake of this exercise, you may ignore considerations of efficiency >> (though that's a bit of a self-contradiction, because heaps are frequently >> introduced specifically for the sake of efficiency). I am only interested >> in the directness, simplicity, elegance (lyricality) of the notation, in >> its current form, for expressing ideas about trees. We can make it >> efficient "later" (Pepe's TCO utility is a start). >> >> -Dan >> >> >> >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm >> > > > > -- > Devon McCormick, CFA > > -- Devon McCormick, CFA ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
