Flexible Python Red Black Tree Implementation

1.22 · active · verified Sat Apr 11

This library provides a flexible Python implementation of red-black trees, offering a low standard deviation in operation times for insertion, deletion, and lookup. It includes modules for both set-like (enforcing uniqueness) and dictionary-like use. The library is known to work across CPython 2.x, CPython 3.x, PyPy, and Jython. The current version is 1.22, with an infrequent release cadence; the last major update was in December 2023.

Warnings

gotcha The library's release history shows a significant gap between versions 1.20 (November 2013) and 1.21 (November 2022). While not explicitly documented as breaking, this long period, coupled with the library's Python 2.x and 3.x compatibility, could imply subtle behavioral changes or a lack of explicit updates for new Python idioms introduced in intermediate versions. Users migrating from very old versions should test thoroughly.
Fix: Review the PyPI release notes for version 1.21 and later for any unstated behavioral changes. Thoroughly test existing code when upgrading from versions prior to 1.21.
gotcha The project description mentions 'a pair of python modules' for implementing red-black trees, one for uniqueness (set-like) and another for dictionary-like use. However, the primary quickstart examples and common usage patterns on PyPI often feature `red_black_dict_mod.RedBlackTree`. The import path or class name for the dedicated 'set-like' module is not explicitly detailed, potentially causing confusion for users seeking only set functionality.
Fix: Examine the installed package contents (e.g., `pip show red-black-tree-mod` and explore the source) to identify the correct module for set-like functionality if `red_black_dict_mod` does not suit your needs.
gotcha For use cases requiring very high performance, scalability, or more active maintenance, alternative libraries like `SortedContainers` might be more suitable. This `red-black-tree-mod` library prioritizes flexibility and broad Python version/runtime compatibility, which might come at the cost of peak performance compared to Python 3-optimized alternatives.
Fix: Evaluate performance requirements. If absolute maximum performance for sorted collections is critical, consider benchmarking against or migrating to libraries like `SortedContainers`.

Install

pip install red-black-tree-mod Install with pip

Imports

RedBlackTree
```
from red_black_dict_mod import RedBlackTree
```
The library provides multiple modules; 'red_black_dict_mod' is used for dictionary-like functionality. The specific module to import depends on whether dictionary-like or set-like behavior is desired, as implied by the project description.

Quickstart

Demonstrates basic dictionary-like usage, including insertion, lookup, iteration (keys are sorted), and deletion.

from red_black_dict_mod import RedBlackTree

# Dictionary-like usage
rbd = RedBlackTree()

# Insert items
for i in range(10):
    rbd[i] = f"value_{i}"

print(f"Tree size: {len(rbd)}")
print(f"Value for key 5: {rbd[5]}")

# Check for existence
print(f"Is 7 in tree? {7 in rbd}")
print(f"Is 100 in tree? {100 in rbd}")

# Iterate through items (keys are sorted)
print("Items in sorted order:")
for k, v in rbd.items():
    print(f"  {k}: {v}")

# Delete an item
del rbd[5]
print(f"Tree size after deleting 5: {len(rbd)}")
print(f"Value for key 5 after deletion (should raise KeyError):\n")
try:
    print(rbd[5])
except KeyError as e:
    print(f"  {e}")

# Set-like usage (not directly shown in quickstart, but implied by documentation)
# The documentation states: 'A module is provided for red black trees that enforce uniqueness. 
# They allow for set-like use and dictionary-like use.'
# It's likely you would import a different module or use RedBlackTree directly for this, 
# but without clear examples, this quickstart focuses on the dictionary aspect.

view raw JSON →