Array representations and "pointer" representations of trees both have
their uses. In the end it depends on what problem you are trying to solve.
As Devon demonstrated, for his purpose, array representation was not a
hindrance at all. But, as Dan mentions, trees are also used to implement
abstract data structures with certain run-time properties where finding the
children of a node or inserting / moving sub-trees in less than constant
time is not acceptable. J already can do the "pointer" representation with
boxed arrays but as stated by others previously, there are insufficient
primitives for working with them conveniently without additional overhead.
I have played around with code similar to Pascal's for working with trees.
I felt, however, this type of stuff has limited usefulness in production
code without help from the interpreter to optimize it. It's the same idea
as a "zipper" data structure in other languages. Here is a bare bones
implementation with lots of room for more bells and whistles if desired.
x=. @ [
y=. @ ]
focus=. (3&{::) y
addrs=. (2&{::) y
crumbs=. (1&{::) y
stack=. (0&{::) y
zip=. '';'';'';<
unzip=. focus @: (zout ^: (#@crumbs))
zin=. (stack) ; (crumbs , <@focus) ; (addrs , <x) ; <@([ {:: focus)
zout=. (stack) ; (}:@crumbs) ; (}:@addrs) ; <@(0 (([:*@L. _1{::crumbs)
<y^:[ focus)`(_1{::addrs)`(_1{::crumbs)} ])
zam=. <x 3} ] NB. amend
zap=. (@ focus)(<@:)(`((3})`]))(`:6) NB. apply
zpush=. (stack , <@focus) ; (crumbs) ; (addrs) ; (<@focus) NB. push focus
in temp stack
zpop=. (}:@stack) ; (crumbs) ; (addrs) ; <@(_1{::stack) NB. pop from temp
stack
zswap=. (}:@stack,<@focus) ; (crumbs) ; (addrs) ; <@(_1{::stack) NB. swap
focus and top of temp stack
]T=. (i.3 3);(11;22;<(_1;i.5));(<'AAA';<'BBB';'CCC')
┌─────┬──────────────────────┬───────────────┐
│0 1 2│┌──┬──┬──────────────┐│┌───┬─────────┐│
│3 4 5││11│22│┌──┬─────────┐│││AAA│┌───┬───┐││
│6 7 8││ │ ││_1│0 1 2 3 4││││ ││BBB│CCC│││
│ ││ │ │└──┴─────────┘│││ │└───┴───┘││
│ │└──┴──┴──────────────┘│└───┴─────────┘│
└─────┴──────────────────────┴───────────────┘
NB. zip tree
zip T
┌┬┬┬──────────────────────────────────────────────┐
││││┌─────┬──────────────────────┬───────────────┐│
│││││0 1 2│┌──┬──┬──────────────┐│┌───┬─────────┐││
│││││3 4 5││11│22│┌──┬─────────┐│││AAA│┌───┬───┐│││
│││││6 7 8││ │ ││_1│0 1 2 3 4││││ ││BBB│CCC││││
│││││ ││ │ │└──┴─────────┘│││ │└───┴───┘│││
│││││ │└──┴──┴──────────────┘│└───┴─────────┘││
││││└─────┴──────────────────────┴───────────────┘│
└┴┴┴──────────────────────────────────────────────┘
NB. Change 'CCC' to 'DDD'
unzip 'DDD' zam _1 zin _1 zin _1 zin zip T
┌─────┬──────────────────────┬───────────────┐
│0 1 2│┌──┬──┬──────────────┐│┌───┬─────────┐│
│3 4 5││11│22│┌──┬─────────┐│││AAA│┌───┬───┐││
│6 7 8││ │ ││_1│0 1 2 3 4││││ ││BBB│DDD│││
│ ││ │ │└──┴─────────┘│││ │└───┴───┘││
│ │└──┴──┴──────────────┘│└───┴─────────┘│
└─────┴──────────────────────┴───────────────┘
NB. Copy the third sub-tree down into the second
unzip zpop _1 zin (,&a:) zap 2 zin 1 zin zout zpush 2 zin zip T
┌─────┬──────────────────────────────────────┬───────────────┐
│0 1 2│┌──┬──┬──────────────────────────────┐│┌───┬─────────┐│
│3 4 5││11│22│┌──┬─────────┬───────────────┐│││AAA│┌───┬───┐││
│6 7 8││ │ ││_1│0 1 2 3 4│┌───┬─────────┐││││ ││BBB│CCC│││
│ ││ │ ││ │ ││AAA│┌───┬───┐│││││ │└───┴───┘││
│ ││ │ ││ │ ││ ││BBB│CCC│││││└───┴─────────┘│
│ ││ │ ││ │ ││ │└───┴───┘││││ │
│ ││ │ ││ │ │└───┴─────────┘│││ │
│ ││ │ │└──┴─────────┴───────────────┘││ │
│ │└──┴──┴──────────────────────────────┘│ │
└─────┴──────────────────────────────────────┴───────────────┘
NB. This time swap the sub-trees in the previous example
unzip zpop 2 zin zout zout zswap 2 zin 1 zin zout zpush 2 zin zip T
┌─────┬───────────────────────┬──────────────┐
│0 1 2│┌──┬──┬───────────────┐│┌──┬─────────┐│
│3 4 5││11│22│┌───┬─────────┐│││_1│0 1 2 3 4││
│6 7 8││ │ ││AAA│┌───┬───┐│││└──┴─────────┘│
│ ││ │ ││ ││BBB│CCC││││ │
│ ││ │ ││ │└───┴───┘│││ │
│ ││ │ │└───┴─────────┘││ │
│ │└──┴──┴───────────────┘│ │
└─────┴───────────────────────┴──────────────┘
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
