Mathias Panzenböck <grosser.meister.morti@gmx.net> wrote:
Ok, now. Forget all I said. Just a short question: When you have to store values accosiated with keys and the keys have to be accessible in a sorted manner. What container type would you use? What data structure would you implement? (I just thought a AVL tree would have been a good choice.)
If you want to use only things that are available in base Python, use a list and the bisect module. If you need O(logn) insertion and removal, then an AVL/Red-Black/2-3 tree with the semantics you described would also work. (I think there is both an AVL and Red-Black tree implementation in the Python package index [1]) If you only need to concern yourself with ordering every once in a while, then x = dct.items();x.sort() works reasonably well. Sometimes a "pair heap" can get you what you are looking for [2]. Data structure choices are tricky. It is usually better to describe the problem and one's approach (why you choose to use a particular algorithm and structure), rather than strictly asking "where can I find data structure X". - Josiah [1] http://www.python.org/pypi/ [2] http://mail.python.org/pipermail/python-dev/2006-November/069845.html