Mastering Assembly Programming

Tree balancing

Now, when we know what a binary search tree looks like on the Assembly programming level, it would not be correct not to return to the question of binary search tree balancing. There are several approaches to this problem, however, we would only consider one-the Day-Stout-Warren algorithm (included in the accompanying code). The algorithm is simple:

1. Allocate a tree node and make it a "pseudo root" for the tree, making the original root the pseudo root's right child.
2. Convert the tree into a sorted linked list by means of an in-order traversal (this step also calculates the number of nodes in the original tree). No additional allocations are required, as the step reuses existing pointers in tree nodes.
3. Convert the list back ...