Pure python implementation of avl trees.
Project description
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
| Hashtable | Hashtable(worst case) | AVLTree | AVLTree(worst case) | |
|---|---|---|---|---|
| Space | O(n) | O(n) | O(n) | O(n) |
| Search | O(1) | O(n) | O(logn) | O(logn) |
| Insert | O(1) | O(n) | O(logn) | O(logn) |
| Delete | O(1) | O(n) | O(logn) | O(logn) |
| Resize | O(n) | O(n) | N/A | N/A |
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
