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
