psfblack true ruff passed a redblack tree which is a selfbalancing bst binary search tree this tree has similar performance to avl trees but the balancing is less strict so it will perform faster for writingdeleting 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 orgwikiredblacktree unless otherwise specified all asymptotic runtimes are specified in terms of the size of the tree initialize a new redblack tree node with the given values label the value associated with this node color 0 if black 1 if red parent the parent to this node left this node s left child right this node s right child here are functions which are specific to redblack trees 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 o1 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 o1 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 ologn time only possible with an empty tree repair the coloring from inserting into a tree if self parent is none this node is the root so it just needs to be black self color 0 elif colorself parent 0 if the parent is black then it just needs to be red self color 1 else uncle self parent sibling if coloruncle 0 if self isleft and self parent isright self parent rotateright if self right self right insertrepair elif self isright and self parent isleft self parent rotateleft if self left self left insertrepair elif self isleft if self grandparent self grandparent rotateright self parent color 0 if self parent right self parent right color 1 else if self grandparent self grandparent rotateleft self parent color 0 if self parent left self parent left color 1 else self parent color 0 if uncle and self grandparent uncle color 0 self grandparent color 1 self grandparent insertrepair def removeself label int redblacktree noqa plr0912 it s easier to balance a node with at most one child so we replace this node with the greatest one less than it and remove that this node has at most one nonnone child so we don t need to replace this node is red and its child is black the only way this happens to a node with one child is if both children are none leaves we can just remove this node and call it a day the node is black this node and its child are black the tree is now empty this node is black and its child is red move the child node here and make it black repair the coloring of the tree that may have been messed up if self parent is none or self sibling is none or self parent sibling is none or self grandparent is none return if colorself sibling 1 self sibling color 0 self parent color 1 if self isleft self parent rotateleft else self parent rotateright if colorself parent 0 and colorself sibling 0 and colorself sibling left 0 and colorself sibling right 0 self sibling color 1 self parent removerepair return if colorself parent 1 and colorself sibling 0 and colorself sibling left 0 and colorself sibling right 0 self sibling color 1 self parent color 0 return if self isleft and colorself sibling 0 and colorself sibling right 0 and colorself sibling left 1 self sibling rotateright self sibling color 0 if self sibling right self sibling right color 1 if self isright and colorself sibling 0 and colorself sibling right 1 and colorself sibling left 0 self sibling rotateleft self sibling color 0 if self sibling left self sibling left color 1 if self isleft and colorself sibling 0 and colorself sibling right 1 self parent rotateleft self grandparent color self parent color self parent color 0 self parent sibling color 0 if self isright and colorself sibling 0 and colorself sibling left 1 self parent rotateright self grandparent color self parent color self parent color 0 self parent sibling color 0 def checkcolorpropertiesself bool i assume property 1 to hold because there is nothing that can make the color be anything other than 0 or 1 property 2 if self color the root was red printproperty 2 return false property 3 does not need to be checked because none is assumed to be black and is all the leaves property 4 if not self checkcoloring printproperty 4 return false property 5 if self blackheight is none printproperty 5 return false all properties were met return true def checkcoloringself bool if self color 1 and 1 in colorself left colorself right return false if self left and not self left checkcoloring return false if self right and not self right checkcoloring return false return true def blackheightself int none if self is none or self left is none or self right is none if we re already at a leaf there is no path return 1 left redblacktree blackheightself left right redblacktree blackheightself right if left is none or right is none there are issues with coloring below children nodes return none if left right the two children have unequal depths return none return the black depth of children plus one if this node is black return left 1 self color here are functions which are general to all binary search trees def containsself label int bool return self searchlabel is not none def searchself label int redblacktree none if self label label return self elif self label is not none and label self label if self right is none return none else return self right searchlabel else if self left is none return none else return self left searchlabel def floorself label int int none returns the smallest element in this tree which is at least label this method is guaranteed to run in ologn time returns the largest element in this tree this method is guaranteed to run in ologn time go as far right as possible returns the smallest element in this tree this method is guaranteed to run in ologn time go as far left as possible get the current node s grandparent or none if it doesn t exist if self parent is none return none else return self parent parent property def siblingself redblacktree none returns true iff this node is the left child of its parent if self parent is none return false return self parent left is self parent left is self def isrightself bool return the number of nodes in this tree test if two trees are equal if not isinstanceother redblacktree return notimplemented if self label other label return self left other left and self right other right else return false def colornode redblacktree none int code for testing the various functions of the redblack tree test that the rotateleft and rotateright functions work make a tree to test on tree redblacktree0 tree left redblacktree10 parenttree tree right redblacktree10 parenttree tree left left redblacktree20 parenttree left tree left right redblacktree5 parenttree left tree right left redblacktree5 parenttree right tree right right redblacktree20 parenttree right make the right rotation leftrot redblacktree10 leftrot left redblacktree0 parentleftrot leftrot left left redblacktree10 parentleftrot left leftrot left right redblacktree5 parentleftrot left leftrot left left left redblacktree20 parentleftrot left left leftrot left left right redblacktree5 parentleftrot left left leftrot right redblacktree20 parentleftrot tree tree rotateleft if tree leftrot return false tree tree rotateright tree tree rotateright make the left rotation rightrot redblacktree10 rightrot left redblacktree20 parentrightrot rightrot right redblacktree0 parentrightrot rightrot right left redblacktree5 parentrightrot right rightrot right right redblacktree10 parentrightrot right rightrot right right left redblacktree5 parentrightrot right right rightrot right right right redblacktree20 parentrightrot right right if tree rightrot return false return true def testinsertionspeed bool tree redblacktree1 for i in range300000 tree tree inserti return true def testinsert bool tree redblacktree0 tree insert8 tree insert8 tree insert4 tree insert12 tree insert10 tree insert11 ans redblacktree0 0 ans left redblacktree8 0 ans ans right redblacktree8 1 ans ans right left redblacktree4 0 ans right ans right right redblacktree11 0 ans right ans right right left redblacktree10 1 ans right right ans right right right redblacktree12 1 ans right right return tree ans def testinsertandsearch bool found something not in there didn t find something in there test the insert and delete method of the tree verifying the insertion and removal of elements and the balancing of the tree tests the floor and ceiling functions in the tree tree redblacktree0 tree insert16 tree insert16 tree insert8 tree insert24 tree insert20 tree insert22 tuples 20 none 16 10 16 0 8 8 8 50 24 none for val floor ceil in tuples if tree floorval floor or tree ceilval ceil return false return true def testminmax bool tests the three different tree traversal functions tree redblacktree0 tree tree insert16 tree insert16 tree insert8 tree insert24 tree insert20 tree insert22 if listtree inordertraverse 16 0 8 16 20 22 24 return false if listtree preordertraverse 0 16 16 8 22 20 24 return false if listtree postordertraverse 16 8 20 24 22 16 0 return false return true def testtreechaining bool pytests 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 initialize a new red black tree node with the given values label the value associated with this node color 0 if black 1 if red parent the parent to this node left this node s left child right this node s right child here are functions which are specific to red black trees 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 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 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 only possible with an empty tree repair the coloring from inserting into a tree this node is the root so it just needs to be black if the parent is black then it just needs to be red noqa plr0912 remove label from this tree it s easier to balance a node with at most one child so we replace this node with the greatest one less than it and remove that this node has at most one non none child so we don t need to replace this node is red and its child is black the only way this happens to a node with one child is if both children are none leaves we can just remove this node and call it a day the node is black this node and its child are black the tree is now empty this node is black and its child is red move the child node here and make it black repair the coloring of the tree that may have been messed up 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 i assume property 1 to hold because there is nothing that can make the color be anything other than 0 or 1 property 2 the root was red property 3 does not need to be checked because none is assumed to be black and is all the leaves property 4 property 5 all properties were met a helper function to recursively check property 4 of a red black tree see check_color_properties for more info 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 if we re already at a leaf there is no path there are issues with coloring below children nodes the two children have unequal depths return the black depth of children plus one if this node is black here are functions which are general to all binary search trees search through the tree for label returning true iff it is found somewhere in the tree guaranteed to run in o log n time 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 returns the largest element in this tree which is at most label this method is guaranteed to run in o log n time returns the smallest element in this tree which is at least label this method is guaranteed to run in o log n time returns the largest element in this tree this method is guaranteed to run in o log n time go as far right as possible returns the smallest element in this tree this method is guaranteed to run in o log n time go as far left as possible get the current node s grandparent or none if it doesn t exist get the current node s sibling or none if it doesn t exist returns true iff this node is the left child of its parent returns true iff this node is the right child of its parent return the number of nodes in this tree test if two trees are equal returns the color of a node allowing for none leaves code for testing the various functions of the red black tree test that the rotate_left and rotate_right functions work make a tree to test on make the right rotation make the left rotation test that the tree balances inserts to o log n by doing a lot of them test the insert method of the tree correctly balances colors and inserts tests searching through the tree for values found something not in there didn t find something in there test the insert and delete method of the tree verifying the insertion and removal of elements and the balancing of the tree tests the floor and ceiling functions in the tree tests the min and max functions in the tree tests the three different tree traversal functions tests the three different tree chaining functions pytests
from __future__ import annotations

from collections.abc import Iterator


class RedBlackTree:
    

    def __init__(
        self,
        label: int | None = None,
        color: int = 0,
        parent: RedBlackTree | None = None,
        left: RedBlackTree | None = None,
        right: RedBlackTree | None = None,
    ) -> None:
        
        self.label = label
        self.parent = parent
        self.left = left
        self.right = right
        self.color = color

    

    def rotate_left(self) -> RedBlackTree:
        
        parent = self.parent
        right = self.right
        if right is None:
            return self
        self.right = right.left
        if self.right:
            self.right.parent = self
        self.parent = right
        right.left = self
        if parent is not None:
            if parent.left == self:
                parent.left = right
            else:
                parent.right = right
        right.parent = parent
        return right

    def rotate_right(self) -> RedBlackTree:
        
        if self.left is None:
            return self
        parent = self.parent
        left = self.left
        self.left = left.right
        if self.left:
            self.left.parent = self
        self.parent = left
        left.right = self
        if parent is not None:
            if parent.right is self:
                parent.right = left
            else:
                parent.left = left
        left.parent = parent
        return left

    def insert(self, label: int) -> RedBlackTree:
        
        if self.label is None:
            
            self.label = label
            return self
        if self.label == label:
            return self
        elif self.label > label:
            if self.left:
                self.left.insert(label)
            else:
                self.left = RedBlackTree(label, 1, self)
                self.left._insert_repair()
        else:
            if self.right:
                self.right.insert(label)
            else:
                self.right = RedBlackTree(label, 1, self)
                self.right._insert_repair()
        return self.parent or self

    def _insert_repair(self) -> None:
        
        if self.parent is None:
            
            self.color = 0
        elif color(self.parent) == 0:
            
            self.color = 1
        else:
            uncle = self.parent.sibling
            if color(uncle) == 0:
                if self.is_left() and self.parent.is_right():
                    self.parent.rotate_right()
                    if self.right:
                        self.right._insert_repair()
                elif self.is_right() and self.parent.is_left():
                    self.parent.rotate_left()
                    if self.left:
                        self.left._insert_repair()
                elif self.is_left():
                    if self.grandparent:
                        self.grandparent.rotate_right()
                        self.parent.color = 0
                    if self.parent.right:
                        self.parent.right.color = 1
                else:
                    if self.grandparent:
                        self.grandparent.rotate_left()
                        self.parent.color = 0
                    if self.parent.left:
                        self.parent.left.color = 1
            else:
                self.parent.color = 0
                if uncle and self.grandparent:
                    uncle.color = 0
                    self.grandparent.color = 1
                    self.grandparent._insert_repair()

    def remove(self, label: int) -> RedBlackTree:  
        
        if self.label == label:
            if self.left and self.right:
                
                
                
                value = self.left.get_max()
                if value is not None:
                    self.label = value
                    self.left.remove(value)
            else:
                
                
                child = self.left or self.right
                if self.color == 1:
                    
                    
                    
                    
                    if self.parent:
                        if self.is_left():
                            self.parent.left = None
                        else:
                            self.parent.right = None
                else:
                    
                    if child is None:
                        
                        if self.parent is None:
                            
                            return RedBlackTree(None)
                        else:
                            self._remove_repair()
                            if self.is_left():
                                self.parent.left = None
                            else:
                                self.parent.right = None
                            self.parent = None
                    else:
                        
                        
                        self.label = child.label
                        self.left = child.left
                        self.right = child.right
                        if self.left:
                            self.left.parent = self
                        if self.right:
                            self.right.parent = self
        elif self.label is not None and self.label > label:
            if self.left:
                self.left.remove(label)
        else:
            if self.right:
                self.right.remove(label)
        return self.parent or self

    def _remove_repair(self) -> None:
        
        if (
            self.parent is None
            or self.sibling is None
            or self.parent.sibling is None
            or self.grandparent is None
        ):
            return
        if color(self.sibling) == 1:
            self.sibling.color = 0
            self.parent.color = 1
            if self.is_left():
                self.parent.rotate_left()
            else:
                self.parent.rotate_right()
        if (
            color(self.parent) == 0
            and color(self.sibling) == 0
            and color(self.sibling.left) == 0
            and color(self.sibling.right) == 0
        ):
            self.sibling.color = 1
            self.parent._remove_repair()
            return
        if (
            color(self.parent) == 1
            and color(self.sibling) == 0
            and color(self.sibling.left) == 0
            and color(self.sibling.right) == 0
        ):
            self.sibling.color = 1
            self.parent.color = 0
            return
        if (
            self.is_left()
            and color(self.sibling) == 0
            and color(self.sibling.right) == 0
            and color(self.sibling.left) == 1
        ):
            self.sibling.rotate_right()
            self.sibling.color = 0
            if self.sibling.right:
                self.sibling.right.color = 1
        if (
            self.is_right()
            and color(self.sibling) == 0
            and color(self.sibling.right) == 1
            and color(self.sibling.left) == 0
        ):
            self.sibling.rotate_left()
            self.sibling.color = 0
            if self.sibling.left:
                self.sibling.left.color = 1
        if (
            self.is_left()
            and color(self.sibling) == 0
            and color(self.sibling.right) == 1
        ):
            self.parent.rotate_left()
            self.grandparent.color = self.parent.color
            self.parent.color = 0
            self.parent.sibling.color = 0
        if (
            self.is_right()
            and color(self.sibling) == 0
            and color(self.sibling.left) == 1
        ):
            self.parent.rotate_right()
            self.grandparent.color = self.parent.color
            self.parent.color = 0
            self.parent.sibling.color = 0

    def check_color_properties(self) -> bool:
        
        
        
        
        if self.color:
            
            print("Property 2")
            return False
        
        
        
        if not self.check_coloring():
            print("Property 4")
            return False
        
        if self.black_height() is None:
            print("Property 5")
            return False
        
        return True

    def check_coloring(self) -> bool:
        
        if self.color == 1 and 1 in (color(self.left), color(self.right)):
            return False
        if self.left and not self.left.check_coloring():
            return False
        if self.right and not self.right.check_coloring():
            return False
        return True

    def black_height(self) -> int | None:
        
        if self is None or self.left is None or self.right is None:
            
            return 1
        left = RedBlackTree.black_height(self.left)
        right = RedBlackTree.black_height(self.right)
        if left is None or right is None:
            
            return None
        if left != right:
            
            return None
        
        
        return left + (1 - self.color)

    

    def __contains__(self, label: int) -> bool:
        
        return self.search(label) is not None

    def search(self, label: int) -> RedBlackTree | None:
        
        if self.label == label:
            return self
        elif self.label is not None and label > self.label:
            if self.right is None:
                return None
            else:
                return self.right.search(label)
        else:
            if self.left is None:
                return None
            else:
                return self.left.search(label)

    def floor(self, label: int) -> int | None:
        
        if self.label == label:
            return self.label
        elif self.label is not None and self.label > label:
            if self.left:
                return self.left.floor(label)
            else:
                return None
        else:
            if self.right:
                attempt = self.right.floor(label)
                if attempt is not None:
                    return attempt
            return self.label

    def ceil(self, label: int) -> int | None:
        
        if self.label == label:
            return self.label
        elif self.label is not None and self.label < label:
            if self.right:
                return self.right.ceil(label)
            else:
                return None
        else:
            if self.left:
                attempt = self.left.ceil(label)
                if attempt is not None:
                    return attempt
            return self.label

    def get_max(self) -> int | None:
        
        if self.right:
            
            return self.right.get_max()
        else:
            return self.label

    def get_min(self) -> int | None:
        
        if self.left:
            
            return self.left.get_min()
        else:
            return self.label

    @property
    def grandparent(self) -> RedBlackTree | None:
        
        if self.parent is None:
            return None
        else:
            return self.parent.parent

    @property
    def sibling(self) -> RedBlackTree | None:
        
        if self.parent is None:
            return None
        elif self.parent.left is self:
            return self.parent.right
        else:
            return self.parent.left

    def is_left(self) -> bool:
        
        if self.parent is None:
            return False
        return self.parent.left is self.parent.left is self

    def is_right(self) -> bool:
        
        if self.parent is None:
            return False
        return self.parent.right is self

    def __bool__(self) -> bool:
        return True

    def __len__(self) -> int:
        
        ln = 1
        if self.left:
            ln += len(self.left)
        if self.right:
            ln += len(self.right)
        return ln

    def preorder_traverse(self) -> Iterator[int | None]:
        yield self.label
        if self.left:
            yield from self.left.preorder_traverse()
        if self.right:
            yield from self.right.preorder_traverse()

    def inorder_traverse(self) -> Iterator[int | None]:
        if self.left:
            yield from self.left.inorder_traverse()
        yield self.label
        if self.right:
            yield from self.right.inorder_traverse()

    def postorder_traverse(self) -> Iterator[int | None]:
        if self.left:
            yield from self.left.postorder_traverse()
        if self.right:
            yield from self.right.postorder_traverse()
        yield self.label

    def __repr__(self) -> str:
        from pprint import pformat

        if self.left is None and self.right is None:
            return f"'{self.label} {(self.color and 'red') or 'blk'}'"
        return pformat(
            {
                f"{self.label} {(self.color and 'red') or 'blk'}": (
                    self.left,
                    self.right,
                )
            },
            indent=1,
        )

    def __eq__(self, other: object) -> bool:
        
        if not isinstance(other, RedBlackTree):
            return NotImplemented
        if self.label == other.label:
            return self.left == other.left and self.right == other.right
        else:
            return False


def color(node: RedBlackTree | None) -> int:
    
    if node is None:
        return 0
    else:
        return node.color





def test_rotations() -> bool:
    
    
    tree = RedBlackTree(0)
    tree.left = RedBlackTree(-10, parent=tree)
    tree.right = RedBlackTree(10, parent=tree)
    tree.left.left = RedBlackTree(-20, parent=tree.left)
    tree.left.right = RedBlackTree(-5, parent=tree.left)
    tree.right.left = RedBlackTree(5, parent=tree.right)
    tree.right.right = RedBlackTree(20, parent=tree.right)
    
    left_rot = RedBlackTree(10)
    left_rot.left = RedBlackTree(0, parent=left_rot)
    left_rot.left.left = RedBlackTree(-10, parent=left_rot.left)
    left_rot.left.right = RedBlackTree(5, parent=left_rot.left)
    left_rot.left.left.left = RedBlackTree(-20, parent=left_rot.left.left)
    left_rot.left.left.right = RedBlackTree(-5, parent=left_rot.left.left)
    left_rot.right = RedBlackTree(20, parent=left_rot)
    tree = tree.rotate_left()
    if tree != left_rot:
        return False
    tree = tree.rotate_right()
    tree = tree.rotate_right()
    
    right_rot = RedBlackTree(-10)
    right_rot.left = RedBlackTree(-20, parent=right_rot)
    right_rot.right = RedBlackTree(0, parent=right_rot)
    right_rot.right.left = RedBlackTree(-5, parent=right_rot.right)
    right_rot.right.right = RedBlackTree(10, parent=right_rot.right)
    right_rot.right.right.left = RedBlackTree(5, parent=right_rot.right.right)
    right_rot.right.right.right = RedBlackTree(20, parent=right_rot.right.right)
    if tree != right_rot:
        return False
    return True


def test_insertion_speed() -> bool:
    
    tree = RedBlackTree(-1)
    for i in range(300000):
        tree = tree.insert(i)
    return True


def test_insert() -> bool:
    
    tree = RedBlackTree(0)
    tree.insert(8)
    tree.insert(-8)
    tree.insert(4)
    tree.insert(12)
    tree.insert(10)
    tree.insert(11)
    ans = RedBlackTree(0, 0)
    ans.left = RedBlackTree(-8, 0, ans)
    ans.right = RedBlackTree(8, 1, ans)
    ans.right.left = RedBlackTree(4, 0, ans.right)
    ans.right.right = RedBlackTree(11, 0, ans.right)
    ans.right.right.left = RedBlackTree(10, 1, ans.right.right)
    ans.right.right.right = RedBlackTree(12, 1, ans.right.right)
    return tree == ans


def test_insert_and_search() -> bool:
    
    tree = RedBlackTree(0)
    tree.insert(8)
    tree.insert(-8)
    tree.insert(4)
    tree.insert(12)
    tree.insert(10)
    tree.insert(11)
    if 5 in tree or -6 in tree or -10 in tree or 13 in tree:
        
        return False
    if not (11 in tree and 12 in tree and -8 in tree and 0 in tree):
        
        return False
    return True


def test_insert_delete() -> bool:
    
    tree = RedBlackTree(0)
    tree = tree.insert(-12)
    tree = tree.insert(8)
    tree = tree.insert(-8)
    tree = tree.insert(15)
    tree = tree.insert(4)
    tree = tree.insert(12)
    tree = tree.insert(10)
    tree = tree.insert(9)
    tree = tree.insert(11)
    tree = tree.remove(15)
    tree = tree.remove(-12)
    tree = tree.remove(9)
    if not tree.check_color_properties():
        return False
    if list(tree.inorder_traverse()) != [-8, 0, 4, 8, 10, 11, 12]:
        return False
    return True


def test_floor_ceil() -> bool:
    
    tree = RedBlackTree(0)
    tree.insert(-16)
    tree.insert(16)
    tree.insert(8)
    tree.insert(24)
    tree.insert(20)
    tree.insert(22)
    tuples = [(-20, None, -16), (-10, -16, 0), (8, 8, 8), (50, 24, None)]
    for val, floor, ceil in tuples:
        if tree.floor(val) != floor or tree.ceil(val) != ceil:
            return False
    return True


def test_min_max() -> bool:
    
    tree = RedBlackTree(0)
    tree.insert(-16)
    tree.insert(16)
    tree.insert(8)
    tree.insert(24)
    tree.insert(20)
    tree.insert(22)
    if tree.get_max() != 22 or tree.get_min() != -16:
        return False
    return True


def test_tree_traversal() -> bool:
    
    tree = RedBlackTree(0)
    tree = tree.insert(-16)
    tree.insert(16)
    tree.insert(8)
    tree.insert(24)
    tree.insert(20)
    tree.insert(22)
    if list(tree.inorder_traverse()) != [-16, 0, 8, 16, 20, 22, 24]:
        return False
    if list(tree.preorder_traverse()) != [0, -16, 16, 8, 22, 20, 24]:
        return False
    if list(tree.postorder_traverse()) != [-16, 8, 20, 24, 22, 16, 0]:
        return False
    return True


def test_tree_chaining() -> bool:
    
    tree = RedBlackTree(0)
    tree = tree.insert(-16).insert(16).insert(8).insert(24).insert(20).insert(22)
    if list(tree.inorder_traverse()) != [-16, 0, 8, 16, 20, 22, 24]:
        return False
    if list(tree.preorder_traverse()) != [0, -16, 16, 8, 22, 20, 24]:
        return False
    if list(tree.postorder_traverse()) != [-16, 8, 20, 24, 22, 16, 0]:
        return False
    return True


def print_results(msg: str, passes: bool) -> None:
    print(str(msg), "works!" if passes else "doesn't work :(")


def pytests() -> None:
    assert test_rotations()
    assert test_insert()
    assert test_insert_and_search()
    assert test_insert_delete()
    assert test_floor_ceil()
    assert test_tree_traversal()
    assert test_tree_chaining()


def main() -> None:
    
    print_results("Rotating right and left", test_rotations())
    print_results("Inserting", test_insert())
    print_results("Searching", test_insert_and_search())
    print_results("Deleting", test_insert_delete())
    print_results("Floor and ceil", test_floor_ceil())
    print_results("Tree traversal", test_tree_traversal())
    print_results("Tree traversal", test_tree_chaining())
    print("Testing tree balancing...")
    print("This should only be a few seconds.")
    test_insertion_speed()
    print("Done!")


if __name__ == "__main__":
    main()