The importance of Knuth's investigations and analyses of BSTs and much else would be difficult to exaggerate, but they are [theoretical computer} science rather than engineering.
The design of a system is a typical engineering task that requires that conflicting objectives for it be compromised economically. One may, for example, decide to put messages into a priority queue because it is an appropriate structure for the standard tasks of message processing. Having done so one will then confront other, conflicting needs, to cancel or delete messages, change their priorities or destinations, etc., etc; and such needs bring in train requirements to search structures that are not optimal for search operations. For reasons of this sort search operations in an ordered linear list, traversals in a BST, and the like are often of great interest even when they must be performed suboptimally. If we had our druthers and one of them were the only operation of interest, we would of course do them differently in another structure, but very often neither is the case. Conflicting goals cannot be optimized simultaneously. What we can and must do instead is make orderly, hopefully quantified tradeoffs among them. John Gilmore, Ashland, MA 01721 - USA -- John Gilmore, Ashland, MA 01721 - USA
