That is a problem for this representation – we would need to support matrix resizing to add and remove nodes. In general, adding and removing nodes is inefficient.
On Thu, Oct 9, 2014 at 12:03 PM, John Myles White <[email protected]> wrote: > When you add a new node in this representation, do you reshape to a > vector, resize the vector, then reshape to a matrix again? > > -- John > > On Oct 9, 2014, at 8:55 AM, Stefan Karpinski <[email protected]> wrote: > > The self-link-is-null-link solution only works when the structure is > acyclic (or more specifically when nodes cannot validly link to > themselves). You only need to have null links when there's a fixed number > of link "slots" – if the number of links is a variable-sized array, you can > just use an empty array for the "no links" case. However, I've found that > on modern machines I've found that keeping the data in one place and the > link structure in another place is a *huge* win. For example, to represent > a k-ary tree of strings, you could do this: > > data = Array(UTF8String, n) > links = Array(Int, n, k) > > > where links[i,j] represents the index of the jth child of the ith node and > 0 indicates no child. If the tree has variable arrity, then that's a > different issue, but a sparse matrix representation is likely to be a good > choice. > > >
