I have iterative AVL algorithms in C# and C++. I was reading your article and it indicated that information needs to be recorded on the search for the insertion point. The algorithms that I use record no information when searching for the insertion point. In fact, an insertion point can be given from a different search or via some other means and the insertion can still be effected. It is possible to start at the bottom of a tree, insert a node and balance upwards with no previous state information.
Yours Sincerely, Ben McNamara.
