Minimalistic, unbalanced Binary Search Tree
Project description
PYTHONIC BST
A minimalistic, unbalanced Binary Search Tree written in pure Python. Originally developed as an example in a Python course.
The class BST
works almost like a dict
with sorted keys, and supports slicing and broadcasting. The methods exploit lazy execution when possible, all relevant operations are $O(log)$ complexity.
BASIC USAGE
Install the latest stable version from PyPi:
~$ pip install pythonic-bst
then
from bst import BST
- Create an empty BST:
foo = BST()
- Add/update an item:
foo[k] = v
- Remove an existing item:
rm foo[k]
- Count items:
len(foo)
- Check wether key $k$ is present:
if k in foo: ...
- Check if the BST is not empty:
if foo: ...
- Iterate forward:
for k, v in foo: ...
- Iterate backward:
for k, v in reversed(foo): ...
- Generate all the keys:
foo.keys()
- Generate all the values:
foo.values()
- Generate all $(k, v)$ pairs:
foo.items()
- Standard BST-esque visits:
foo.visit_in_order()
,foo.visit_pre_order()
,foo.visit_post_order()
INITIALIZATION / CONVERSION
A BST can be initialized from a sequence of $(k, v)$ pairs, like another BST's iterator.
- Duplicate a BST:
bar = BST(foo)
- Initialize a BST from a generic sequence of pairs:
foo = BST([(18, 5), (23, 10)])
A dictionary may be used directly to initialize a BST and vice-versa.
- Initialize from a dictionary:
foo = BST(baz)
- Create a dictionary from a BST:
baz = dict(foo)
SLICING / BROADCASTING
Notes: Slices are half-open. In [k1:k2]
, key k1
must be present in the BST, key k2
is never included. The step
can be +1
(default) for forward and -1
for backward.
-
Iterate forward on keys $k \in [k_1, k_2[$:
for k, v in foo[k1:k2]: ...
-
Iterate backward on keys $k \in ]k_1, k_2]$:
for k, v in foo[k2:k1:-1]: ...
-
Update the first three items with keys $k \in [k_1, k_2[$:
foo[k1:k2] = [v1, v2, v3]
-
Set all items with keys $k < k_2$ to a specific value:
foo[:k2] = v
-
Remove item with key $k_1$ and all subsequent ones:
rm foo[k1:]
PERFORMANCES
The height (longest path from the root), the density (percentage of internal nodes that have two successors), and the unbalance (relative difference between the longest and the shortest path from the root) may be accessed as properties, although at a significant cost.
foo = BST()
for n in range(1_000_000):
foo[random.random()] = n
print(foo.height, foo.density, foo.unbalance)
# Initializing from known data creates an optimized structure
bar = BST(foo)
print(bar.height, bar.density, bar.unbalance)
may yield something like
49 0.4997143041393656 0.8775510204081632
20 0.9073503634459752 0.05
TESTING
Some unsystematic unit test has been implemented using pytest and Coverage.py.
LICENSE
Copyright © 2023 by Giovanni Squillero
Distributed under a Zero-Clause BSD License (SPDX: 0BSD), which allows unlimited freedom with the software without the requirement to include legal notices. See the full text for details.
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
Built Distribution
File details
Details for the file pythonic-bst-1.0.3.tar.gz
.
File metadata
- Download URL: pythonic-bst-1.0.3.tar.gz
- Upload date:
- Size: 8.5 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.2 CPython/3.10.9
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5ed9df20b351716c7105a6c64dc918f1de8bb49d525db0ed0f2ac87d8dc1d465 |
|
MD5 | bb913090725d5160bf00e8b7d9935f2b |
|
BLAKE2b-256 | 94b5fe3f85b40a4c1448c98c9a1d12ede332417c83095652873fa66f3deedf01 |
File details
Details for the file pythonic_bst-1.0.3-py3-none-any.whl
.
File metadata
- Download URL: pythonic_bst-1.0.3-py3-none-any.whl
- Upload date:
- Size: 7.2 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.2 CPython/3.10.9
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 365ec487a00a1a4721bb54d7114454fa24a343ffdc4bf32841a5708b3785c53c |
|
MD5 | 559d0228e391b3a4b0eebe0354699d95 |
|
BLAKE2b-256 | 0907411e05297e35bd67bd2ad7806b400194b8ffaf4c85cf55a6e2698920481d |