On Jul 14, 8:10 am, Piet van Oostrum <p...@cs.uu.nl> wrote: > Of course you can take any BST algorithm and replace pointers by indices > in the array and allocate new elements in the array. But then you need > array elements to contain the indices for the children explicitely.
And why is this a problem? This is how binary heaps are typically implemented, and it all works swimmingly. The node rotations for keeping a binary heap balanced turn out to be suitable for representation in a flat array. I.e., when you do the node rotations, you only ever have to copy log n array elements. In general, however, you can't move nodes around so easily when represented in a flat array. A node movement in a tree represented with pointers, might involves changing just two pointers, while when represented as a flat array, might involve copying most of the array to maintain the tree invariants. It just so turns out that maintaining the invariants for a binary heap does not have this issue. This is why I was curious about treaps, which are a type of binary heap. The CLRS textbook on algorithms discusses treaps, but doesn't ever mention whether they are as fortunate as less constrained binary heaps. I'm sure I could work out for myself whether the treap rotations are suitable for storage in a flat array, but I might make a mistake somewhere in my reasoning, and then never know the true answer! |>ouglas -- http://mail.python.org/mailman/listinfo/python-list
