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
| 4 | |
| 5 | |
| 6 | class RedBlackTree: |
| 7 | """ |
| 8 | A Red-Black tree, which is a self-balancing BST (binary search |
| 9 | tree). |
| 10 | This tree has similar performance to AVL trees, but the balancing is |
| 11 | less strict, so it will perform faster for writing/deleting nodes |
| 12 | and slower for reading in the average case, though, because they're |
| 13 | both balanced binary search trees, both will get the same asymptotic |
| 14 | performance. |
| 15 | To read more about them, https://en.wikipedia.org/wiki/Red-black_tree |
| 16 | Unless otherwise specified, all asymptotic runtimes are specified in |
| 17 | terms of the size of the tree. |
| 18 | """ |
| 19 | |
| 20 | def __init__( |
| 21 | self, |
| 22 | label: int | None = None, |
| 23 | color: int = 0, |
| 24 | parent: RedBlackTree | None = None, |
| 25 | left: RedBlackTree | None = None, |
| 26 | right: RedBlackTree | None = None, |
| 27 | ) -> None: |
| 28 | """Initialize a new Red-Black Tree node with the given values: |
| 29 | label: The value associated with this node |
| 30 | color: 0 if black, 1 if red |
| 31 | parent: The parent to this node |
| 32 | left: This node's left child |
| 33 | right: This node's right child |
| 34 | """ |
| 35 | self.label = label |
| 36 | self.parent = parent |
| 37 | self.left = left |
| 38 | self.right = right |
| 39 | self.color = color |
| 40 | |
| 41 | # Here are functions which are specific to red-black trees |
| 42 | |
| 43 | def rotate_left(self) -> RedBlackTree: |
| 44 | """Rotate the subtree rooted at this node to the left and |
| 45 | returns the new root to this subtree. |
| 46 | Performing one rotation can be done in O(1). |
| 47 | """ |
| 48 | parent = self.parent |
| 49 | right = self.right |
| 50 | if right is None: |
| 51 | return self |
| 52 | self.right = right.left |
| 53 | if self.right: |
| 54 | self.right.parent = self |
| 55 | self.parent = right |
| 56 | right.left = self |
| 57 | if parent is not None: |
| 58 | if parent.left == self: |
| 59 | parent.left = right |
| 60 | else: |
| 61 | parent.right = right |
| 62 | right.parent = parent |
| 63 | return right |
no outgoing calls