Knuth algorithm 6.2.3A (Balanced Tree Search and Insertion) (AVL) is not much more work. A couple instructions for a single rotate, a few more when double rotate is needed. Students coded it pretty quickly.
Michael Stack At 03:39 PM 1/19/2012 -0700, you wrote: >On 1/18/2012 1:20 PM, Gerhard Postpischil wrote: >>On 1/18/2012 2:45 PM, Michael Stack wrote: >>>While binary search trees have been mentioned (by John >>>Gilmore, IIRC), I keep wondering why so many other solutions >>>are being suggested. For any repetitive search of a linked >>>list, converting to a BST seems an almost obvious solution. >>>See Knuth's Algorithm 6.2.2T (Tree Search and Insertion), for >>>example. Or am I missing something? >There are a set of POSIX interfaces in /usr/include/search.h > >>I suspect, but have no confirmation, that this algorithm is >>neglected due to Knuth's omission (homework?) of any way to read >>the tree sequentially, something likely to be required in a >>commercial environment? >Perhaps because traversal by recursive descent was deemed trivial? > >Alas, none of several implementations of these functions I've tested >balance the trees. > >-- gil
