pyavl3 1.0.0

Pure python implementation of avl trees.

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