Skip to main content

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

Copyright © 2022 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 license 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

pythonic-bst-1.0.1.tar.gz (8.3 kB view hashes)

Uploaded Source

Built Distribution

pythonic_bst-1.0.1-py3-none-any.whl (7.1 kB view hashes)

Uploaded Python 3

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