Balanced trees (was: Re: Tuples and immutability)

Ian Kelly ian.g.kelly at gmail.com
Sat Mar 8 12:03:00 CET 2014


On Sat, Mar 8, 2014 at 1:34 AM, Marko Rauhamaa <marko at pacujo.net> wrote:
> Speaking of which, are there plans to add a balanced tree to the
> "batteries" of Python? Timers, cache aging and the like need it. I'm
> using my own AVL tree implementation, but I'm wondering why Python
> still doesn't have one.

None currently that I'm aware of.  If you want to propose adding one,
I suggest reading:

http://docs.python.org/devguide/stdlibchanges.html

> In fact, since asyncio has timers but Python doesn't have balanced
> trees, I'm led to wonder how good the asyncio implementation can be.

Peeking at the code, it appears to use a heapq-based priority queue.
Why would a balanced binary tree be better?



More information about the Python-list mailing list