Security News
Introducing the Socket Python SDK
The initial version of the Socket Python SDK is now on PyPI, enabling developers to more easily interact with the Socket REST API in Python projects.
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.
Install the latest stable version from PyPi:
~$ pip install pythonic-bst
then
from bst import BST
foo = BST()
foo[k] = v
rm foo[k]
len(foo)
if k in foo: ...
if foo: ...
for k, v in foo: ...
for k, v in reversed(foo): ...
foo.keys()
foo.values()
foo.items()
foo.visit_in_order()
, foo.visit_pre_order()
, foo.visit_post_order()
A BST can be initialized from a sequence of $(k, v)$ pairs, like another BST's iterator.
bar = BST(foo)
foo = BST([(18, 5), (23, 10)])
A dictionary may be used directly to initialize a BST and vice-versa.
foo = BST(baz)
baz = dict(foo)
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:]
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
Some unsystematic unit test has been implemented using pytest and Coverage.py.
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.
FAQs
Minimalistic, unbalanced Binary Search Tree
We found that pythonic-bst demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
The initial version of the Socket Python SDK is now on PyPI, enabling developers to more easily interact with the Socket REST API in Python projects.
Security News
Floating dependency ranges in npm can introduce instability and security risks into your project by allowing unverified or incompatible versions to be installed automatically, leading to unpredictable behavior and potential conflicts.
Security News
A new Rust RFC proposes "Trusted Publishing" for Crates.io, introducing short-lived access tokens via OIDC to improve security and reduce risks associated with long-lived API tokens.