Pure python implementation of avl trees.
A python dictionary alternative implemented with an AVL Tree.
pip install pyavl3
from pyavl3 import AVLTree a = AVLTree() a = "Hello" a = "world!" print(", ".join(a.values()))
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
|Hashtable||Hashtable(worst case)||AVLTree||AVLTree(worst case)|
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.