data_structures.binary_tree.red_black_tree ========================================== .. py:module:: data_structures.binary_tree.red_black_tree Classes ------- .. autoapisummary:: data_structures.binary_tree.red_black_tree.RedBlackTree Functions --------- .. autoapisummary:: data_structures.binary_tree.red_black_tree.color data_structures.binary_tree.red_black_tree.main data_structures.binary_tree.red_black_tree.print_results data_structures.binary_tree.red_black_tree.pytests data_structures.binary_tree.red_black_tree.test_floor_ceil data_structures.binary_tree.red_black_tree.test_insert data_structures.binary_tree.red_black_tree.test_insert_and_search data_structures.binary_tree.red_black_tree.test_insert_delete data_structures.binary_tree.red_black_tree.test_insertion_speed data_structures.binary_tree.red_black_tree.test_min_max data_structures.binary_tree.red_black_tree.test_rotations data_structures.binary_tree.red_black_tree.test_tree_chaining data_structures.binary_tree.red_black_tree.test_tree_traversal Module Contents --------------- .. py:class:: 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. .. py:method:: __bool__() -> bool .. py:method:: __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. .. py:method:: __eq__(other: object) -> bool Test if two trees are equal. .. py:method:: __len__() -> int Return the number of nodes in this tree. .. py:method:: __repr__() -> str .. py:method:: _insert_repair() -> None Repair the coloring from inserting into a tree. .. py:method:: _remove_repair() -> None Repair the coloring of the tree that may have been messed up. .. py:method:: 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). .. py:method:: 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. .. py:method:: 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. .. py:method:: check_coloring() -> bool A helper function to recursively check Property 4 of a Red-Black Tree. See check_color_properties for more info. .. py:method:: 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. .. py:method:: get_max() -> int | None Returns the largest element in this tree. This method is guaranteed to run in O(log(n)) time. .. py:method:: get_min() -> int | None Returns the smallest element in this tree. This method is guaranteed to run in O(log(n)) time. .. py:method:: inorder_traverse() -> collections.abc.Iterator[int | None] .. py:method:: 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. .. py:method:: is_left() -> bool Returns true iff this node is the left child of its parent. .. py:method:: is_right() -> bool Returns true iff this node is the right child of its parent. .. py:method:: postorder_traverse() -> collections.abc.Iterator[int | None] .. py:method:: preorder_traverse() -> collections.abc.Iterator[int | None] .. py:method:: remove(label: int) -> RedBlackTree Remove label from this tree. .. py:method:: 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). .. py:method:: 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). .. py:method:: 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. .. py:attribute:: color :value: 0 .. py:property:: grandparent :type: RedBlackTree | None Get the current node's grandparent, or None if it doesn't exist. .. py:attribute:: label :value: None .. py:attribute:: left :value: None .. py:attribute:: parent :value: None .. py:attribute:: right :value: None .. py:property:: sibling :type: RedBlackTree | None Get the current node's sibling, or None if it doesn't exist. .. py:function:: color(node: RedBlackTree | None) -> int Returns the color of a node, allowing for None leaves. .. py:function:: main() -> None >>> pytests() .. py:function:: print_results(msg: str, passes: bool) -> None .. py:function:: pytests() -> None .. py:function:: test_floor_ceil() -> bool Tests the floor and ceiling functions in the tree. .. py:function:: test_insert() -> bool Test the insert() method of the tree correctly balances, colors, and inserts. .. py:function:: test_insert_and_search() -> bool Tests searching through the tree for values. .. py:function:: 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. .. py:function:: test_insertion_speed() -> bool Test that the tree balances inserts to O(log(n)) by doing a lot of them. .. py:function:: test_min_max() -> bool Tests the min and max functions in the tree. .. py:function:: test_rotations() -> bool Test that the rotate_left and rotate_right functions work. .. py:function:: test_tree_chaining() -> bool Tests the three different tree chaining functions. .. py:function:: test_tree_traversal() -> bool Tests the three different tree traversal functions.