Skip to main content

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

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 Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page