Balanced Tree grow()

[Brian Alliet]

I was just about to implement grow() in BalancedTree but I hit a snag.

When we grow() the numbers of each node obviously are going to change.
That means the root node in every BalancedTree instance needs to
change. Unfortunately we have no way of getting a reference to every
BalancedTree instance. Without doing something ugly with weak pointers
I don't think it is possible.

One thing I was thinking of doing is adding an extra layer of
indirection for the root node. BalancedTree would contain a static
array of root nodes and each BalancedTree instance would point to one
element of that arrray. (That is called a handle right?)

Anybody else have any suggestions?

-Brian

[Adam Megacz]

Post by Brian Alliet
When we grow() the numbers of each node obviously are going to
change. That means the root node in every BalancedTree instance needs
to change. Unfortunately we have no way of getting a reference to
every BalancedTree instance. Without doing something ugly with weak
pointers I don't think it is possible.

Yeah, that's why I didn't implement grow(). I couldn't come up with a
good way to do it.

Post by Brian Alliet
One thing I was thinking of doing is adding an extra layer of
indirection for the root node. BalancedTree would contain a static
array of root nodes and each BalancedTree instance would point to one
element of that arrray. (That is called a handle right?)

Definately possible. But ugly. Are we really running out of
NUM_SLOTS?

- a

[Brian Alliet]

Are we really running out of NUM_SLOTS?

Not yet.

However, because we don't implement grow we can't put any limits on the
maximum distance a node can be from its "ideal" location. That means
indexOf() has no way of failing if the object doesn't exist in the tree
(it is forced to search through the tree forever).

I guess we could put some kind of limit in there and just fall back to
a linear search through the array if we hit the limit. This would
eliminate any non-deterministic behavior. That is pretty ugly, and
slow, but I don't think doing an indexOf() on a non-existent node
should happen too often.

-Brian

[David Crawshaw]

Post by Brian Alliet
When we grow() the numbers of each node obviously are going to change.
That means the root node in every BalancedTree instance needs to
change.

A little unsure about the nature of BalancedTree, but is the change in
the root node number proportional to the growth of NUM_SLOTS?

If so, could the root node be defined as:

int root() { return growth_factor * node_num; }

where growth_factor is a static?

-- d

[Adam Megacz]

Post by David Crawshaw
A little unsure about the nature of BalancedTree, but is the change in
the root node number proportional to the growth of NUM_SLOTS?

Not always. It's basically a hash table with quadradic probing for
collision resolution (like Hash.java). So the collisions all change.

This is the big downside of quadradic probing. The upside is way less
crud on the heap for the GC to scan.

- a