I came to the realization that unbalanced btrees are not much more efficient than linked lists. So I've been mulling over a balancing algorithm for them and I was looking for suggestions.
I will use the following terminology:
node - entry in the tree, has 2 children, left child and right child
leaf - a node that has two null pointers for children
root - first node in list
distance - number of nodes in the path from one node to another, minus one
sub tree - a tree extending from any node to it's decendents (that node is the root in the sub tree)
full tree - a tree in which all nodes are either leaves or have 2 non-null children and the distance from the root to any leaf is the same
Which child is greater than, less than is irrelevant. Here is what I have so far:
1. take the root and one of it's children and feed this back into the tree, using the root's other child as the new root.
problems: this will only balance the tree if the number of entries in the old root's left child's sub tree were close to the number of entries in the old root's right child's sub tree (wow, good luck understanding that)
2. find the mean value of the entries in the tree and make this a root in a temporary tree. Take the entries from the first tree, and put them in the temporary tree, then copy the temp tree back to the original
problems: this will only approximately balance the tree if there are no large gaps between the values of the nodes in the tree, otherwise one side will be top heavy
geez, I haven't come up with much, and none of it's very good. Neither of these even come close to giving me a full tree, which would be ideal. The other problem I've come to is deciding when to balance. Now if I had a way to balance that would give me a full tree I imagine I could balance every time I created old_distance^2 nodes, where old_distance is the maximum distance after the last balance. Well I'm confusing myself now and I should probably put some more thought into this, but any help would be greatly appreciated. Thanks
-e
