I found an implementation of red-black trees on rosettacode: http://rosettacode.org/wiki/Pattern_matching#J ... It might be relevant or may not be.
On Mon, Sep 8, 2014 at 3:45 PM, Devon McCormick <devon...@gmail.com> wrote: > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
