Mathias Panzenböck <grosser.meister.morti@gmx.net> wrote:
Josiah Carlson schrieb:
However, the problem with choosing to use an AVL (Red-Black, 2-3, etc.) tree is deciding semantics. Do you allow duplicate keys?
Does dict? no. so no.
Do you allow insertion and removal by position?
Does dict? no. so no.
Do you allow the fetching of the key/value at position X?
Does dict? no. so no.
Do you allow the fetching of the position for key X?
Does dict? no. so no.
Insertion before/after (bisect_left, bisect_right equivalents). Etcetera.
Why should all this be relevant?
Very few use-cases of trees involve an ordered key/value dictionary. In 90% of the cases where I have needed (and implemented) trees involved one of the following use-cases; sorted keys (but no values), no but fast insertion of value based on position, sorted keys indexed by position or key with (and without) values, etc. Please also understand that the semantics of Python's dictionary is a function of its implementation as an open-addressed hash table. It's useful for 95% of use-cases, but among the remaining 5% (which includes the use-case you have in mind for the structure), there is a huge variety of just as significant uses that shouldn't be discounted.
In many cases, using a sorted list gets you what you want, is almost as fast, and has the benefit of using less memory.
AFAIK does a doubled link list use the same amount of memory as a (very) simple AVL tree:
Python lists aren't linked lists. If you didn't know this, then you don't know enough about the underlying implementation to make comments about what should or should not be available in the base language. - Josiah