data_structures.binary_tree.red_black_tree

Classes

RedBlackTree

A Red-Black tree, which is a self-balancing BST (binary search

Functions

color(→ int)	Returns the color of a node, allowing for None leaves.
main(→ None)
print_results(→ None)
pytests(→ None)
test_floor_ceil(→ bool)	Tests the floor and ceiling functions in the tree.
test_insert(→ bool)	Test the insert() method of the tree correctly balances, colors,
test_insert_and_search(→ bool)	Tests searching through the tree for values.
test_insert_delete(→ bool)	Test the insert() and delete() method of the tree, verifying the
test_insertion_speed(→ bool)	Test that the tree balances inserts to O(log(n)) by doing a lot
test_min_max(→ bool)	Tests the min and max functions in the tree.
test_rotations(→ bool)	Test that the rotate_left and rotate_right functions work.
test_tree_chaining(→ bool)	Tests the three different tree chaining functions.
test_tree_traversal(→ bool)	Tests the three different tree traversal functions.

Module Contents

class data_structures.binary_tree.red_black_tree.RedBlackTree(label: int | None = None, color: int = 0, parent: RedBlackTree | None = None, left: RedBlackTree | None = None, right: RedBlackTree | None = None)

A Red-Black tree, which is a self-balancing BST (binary search tree). This tree has similar performance to AVL trees, but the balancing is less strict, so it will perform faster for writing/deleting nodes and slower for reading in the average case, though, because they’re both balanced binary search trees, both will get the same asymptotic performance. To read more about them, https://en.wikipedia.org/wiki/Red-black_tree Unless otherwise specified, all asymptotic runtimes are specified in terms of the size of the tree.

__bool__() → bool

__contains__(label: int) → bool

Search through the tree for label, returning True iff it is found somewhere in the tree. Guaranteed to run in O(log(n)) time.

__eq__(other: object) → bool

Test if two trees are equal.

__len__() → int

Return the number of nodes in this tree.

__repr__() → str

_insert_repair() → None

Repair the coloring from inserting into a tree.

_remove_repair() → None

Repair the coloring of the tree that may have been messed up.

black_height() → int | None

Returns the number of black nodes from this node to the leaves of the tree, or None if there isn’t one such value (the tree is color incorrectly).

ceil(label: int) → int | None

Returns the smallest element in this tree which is at least label. This method is guaranteed to run in O(log(n)) time.

check_color_properties() → bool

Check the coloring of the tree, and return True iff the tree is colored in a way which matches these five properties: (wording stolen from wikipedia article)

1. Each node is either red or black.

2. The root node is black.

3. All leaves are black.

4. If a node is red, then both its children are black.

5. Every path from any node to all of its descendent NIL nodes has the same number of black nodes.

This function runs in O(n) time, because properties 4 and 5 take that long to check.

check_coloring() → bool

A helper function to recursively check Property 4 of a Red-Black Tree. See check_color_properties for more info.

floor(label: int) → int | None

Returns the largest element in this tree which is at most label. This method is guaranteed to run in O(log(n)) time.

get_max() → int | None

Returns the largest element in this tree. This method is guaranteed to run in O(log(n)) time.

get_min() → int | None

Returns the smallest element in this tree. This method is guaranteed to run in O(log(n)) time.

inorder_traverse() → collections.abc.Iterator[int | None]

insert(label: int) → RedBlackTree

Inserts label into the subtree rooted at self, performs any rotations necessary to maintain balance, and then returns the new root to this subtree (likely self). This is guaranteed to run in O(log(n)) time.

is_left() → bool

Returns true iff this node is the left child of its parent.

is_right() → bool

Returns true iff this node is the right child of its parent.

postorder_traverse() → collections.abc.Iterator[int | None]

preorder_traverse() → collections.abc.Iterator[int | None]

remove(label: int) → RedBlackTree

Remove label from this tree.

rotate_left() → RedBlackTree

Rotate the subtree rooted at this node to the left and returns the new root to this subtree. Performing one rotation can be done in O(1).

rotate_right() → RedBlackTree

Rotate the subtree rooted at this node to the right and returns the new root to this subtree. Performing one rotation can be done in O(1).

search(label: int) → RedBlackTree | None

Search through the tree for label, returning its node if it’s found, and None otherwise. This method is guaranteed to run in O(log(n)) time.

color

property grandparent: RedBlackTree | None

Get the current node’s grandparent, or None if it doesn’t exist.

label

left

parent

right

property sibling: RedBlackTree | None

Get the current node’s sibling, or None if it doesn’t exist.

data_structures.binary_tree.red_black_tree.color(node: RedBlackTree | None) → int

Returns the color of a node, allowing for None leaves.

data_structures.binary_tree.red_black_tree.main() → None

>>> pytests()

data_structures.binary_tree.red_black_tree.print_results(msg: str, passes: bool) → None

data_structures.binary_tree.red_black_tree.pytests() → None

data_structures.binary_tree.red_black_tree.test_floor_ceil() → bool

Tests the floor and ceiling functions in the tree.

data_structures.binary_tree.red_black_tree.test_insert() → bool

Test the insert() method of the tree correctly balances, colors, and inserts.

data_structures.binary_tree.red_black_tree.test_insert_and_search() → bool

Tests searching through the tree for values.

data_structures.binary_tree.red_black_tree.test_insert_delete() → bool

Test the insert() and delete() method of the tree, verifying the insertion and removal of elements, and the balancing of the tree.

data_structures.binary_tree.red_black_tree.test_insertion_speed() → bool

Test that the tree balances inserts to O(log(n)) by doing a lot of them.

data_structures.binary_tree.red_black_tree.test_min_max() → bool

Tests the min and max functions in the tree.

data_structures.binary_tree.red_black_tree.test_rotations() → bool

Test that the rotate_left and rotate_right functions work.

data_structures.binary_tree.red_black_tree.test_tree_chaining() → bool

Tests the three different tree chaining functions.

data_structures.binary_tree.red_black_tree.test_tree_traversal() → bool

Tests the three different tree traversal functions.