pyavl3

A python dictionary alternative implemented with an AVL Tree.

Quick Start

pip install pyavl3

from pyavl3 import AVLTree

a = AVLTree()
a[1] = "Hello"
a[2] = "world!"

print(", ".join(a.values()))

Why?

Python dictionaries are implemented on hashmaps. Hashmaps, besides being awesome, are a balancing act between efficiency and memory utilization. Python's builtin algorithm is solid and probably the correct choice 99 times out 100. Not really a supprise. But, hashmaps suffers from the need to resize and resizing is pretty expensive. For those few cases where resizing large in-memory blocks of sequentional memory is not going to work, AVLTrees might be a better option. Oh, and AVLTrees are effectivly sorted. So, iterators are deterministic and always in order.

This table compairs the runtime characteristics of Hashtables and AVLTrees