http://www.jsoftware.com/jwiki/Essays/Quicksort has an example of trees.
----- Original Message ----- From: Raul Miller <[EMAIL PROTECTED]> Date: Monday, December 3, 2007 4:44 Subject: Re: [Jprogramming] APL2007 pictures -> Guy Steele's keynote To: Programming forum <[email protected]> > On Dec 2, 2007 11:47 PM, Devon McCormick <[EMAIL PROTECTED]> > wrote:> However, upon reading the section in "A Programming > Language" dealing with > > trees, it looks as though trees are represented by using > matrixes. A directed > > graph is shown represented as a boolean matrix with a one in > the row and > > column where node "row number" goes to node "column > > number". > > You can also represent a tree using flat lists -- with a list of > integers representing > structure (for each node, the index of the parent node, > with some special value > representing the root node) and a parallel list representing > node data. > > Of course, these representations work best for operations > performed on the tree > as a whole, and work poorly for scalar operations on > trees. But that tends to > be true with J and APL overall. > > Put differently, if trees are being used to optimize scalar > processing, you > probably should not be trying to copy this approach in J -- you > would do > better working from first principles (perhaps using a small > cache of recent > changes represented against some larger archive structure, or perhaps > doing something completely different...). > > However, I can also see trees represented in J using boxed lists. > This could be a boxed structure of indices into some flat clump > of data > (which you would need to carefully manage so updates use special > code). Or, for keyed trees, you might want to maintain a > pair of > parallel boxed lists (one of indices and the other of > keys). In all > cases you should have fairly shallow trees with fat nodes. And > I think you would have to be using explicit coding for at least some > critical operations. > > That said, I do not feel like coding up any examples at the moment, > in part because this subject is so broad that specific examples > might not be interesting, but also because I have no immediate > uses for trees. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
