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? It just has to be some kind of relation between a key and a value, and the keys should be accessible in a sorted way (and you should not to have to sort them every time). So it would be possible to slice such a container.
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: struct tree_node { struct tree_node left; struct tree_node right; void * data; }; struct list_node { struct list_node prev; struct list_node next; void * data; };
- Josiah