On 2/27/06, Ross Paterson
We are planning to move to AVL trees for A. Hey, which do not provide a O(1) size function.
What will be gain for this move? And what will we lose, apart from O(1) size?
The gains: 1. Christian Maeder and others report a significant performance improvement. This is the main motivating factor. 2. The AVL tree library is very comprehensive and can be very useful by itself. 3. A separate balanced Tree infrastructure provide many benefits: * Shared code between Map and Set. * Conversion between those should then become more efficient (requested by John Meacham) * Possibility to base more data structures on AVL trees (eg. StringMap) * It should be easier to fine-tune algorithms. We will provide toTree/unsafeFromSortedTree that will allow users to write code that have access to the tree structure. An alternative is to keep the same tree implentation, and separate the Tree data type from the high-level Set/Map abstract type. This is yet more work however, and ignores the fact that the trees in set and map are actually different types. The loss: * More code to maintain. AVL trees are also trickier. * Transitional costs: changes in behaviour may affect user code. (Despite many efforts to be as compatible as possible) Cheers, JP.