Thank to Neil Cerutti and Duncan Booth for the answers. I have not tried that C AVL implementation yet.
Duncan Booth: > but for your ordered dictionary if you did that you would have > to fix up the linked list. To fix the list in constant time you probably need a doubly-linked list, this requires more memory (or the bad xor trick) and more code complexity. > Then if you reinsert the deleted value it goes back in at its original order. Uhm, this doesn't sound good. Thank you, I missed this detail :-) Then the doubly-linked list, and the links fixing seem necessary... Bear hugs, bearophile -- http://mail.python.org/mailman/listinfo/python-list
