Skip to main content

Pure python implementation of avl trees.

Project description


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()))


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

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

pyavl3-1.0.0.tar.gz (6.5 kB view hashes)

Uploaded source

Built Distribution

pyavl3-1.0.0-py3-none-any.whl (8.2 kB view hashes)

Uploaded py3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page