Balanced trees

[Marko Rauhamaa]

Chris Angelico <rosuav at gmail.com>:

> Supposed to have? What does that mean, a language isn't ISO-compliant
> unless it provides both?

It's an ancient, fundamental data structure, right up there with dynamic
lists. There's no reason it shouldn't be available in every programming
environment.

> With a high level language like Python, using the provided hash table
> will almost always cream any hand-built tree, no matter how
> advantageous the data is to the tree.

The main thing is there are use cases where order is essential. That's
why I have had to implement the AVL tree in Python myself. No biggie,
but a C implementation would probably be much faster. Also, a standard
version would likely be reviewed and tested better and have all Pythonic
accessors in place.


Marko