A Python implementation of red-black trees. This code was originally copied from programiz.com, but I have made a few tweaks to improve the user interface. I have also fixed a hard-to-catch but serious bug in the original implementation (which has since been propogated to a number of tutorials on the internet), and added a rigorous testing suite to ensure there are no further bugs.

I made this repo so that students in my algorithms class can try out red-black trees without needing to use C++. Feel free to use it for similar educational purposes! For more practical use-cases, you're probably better off using the SortedContainers library, which is more efficient, more scalable, and better maintained.

This data structure is designed to be used either as a standard red-black binary search tree or as a red-black tree backed dictionary.

A new red-black tree can be constructed as follows:

bst = RedBlackTree()

Items can be inserted into a tree using the insert method:

bst.insert(5)  # inserts a node with value 5

Items can be removed from the tree using the delete method. This method will do nothing if there is no item in the tree with the specific key.

bst.delete(5)  # removes a node with value 5

The minimum and maximum value in the tree can be found with the corresponding methods. If the tree is empty, these methods will both return the special value bst.TNULL

bst.minimum()  # returns minimum value
bst.maximum()  # returns maximum value

bst.minimum() == bst.TNULL  # Check whether tree is empty

Tree size can be accessed via the size member variable:

bst.size  # contains the tree's size

To find a specific item in the tree, you can use the search method:

bst.search(6)  # returns the node containing 6. Will return bst.TNULL if item is not present.

To get a node's predecessor or sucessor;

bst.predecessor(bst.search(6))  # Gets the predecessor a node containing 6
bst.successor(bst.search(6))  # Gets the successor a node containing 6

To know more about the contents of the tree, you can print it to stdout:

bst.print_tree()  # prints an ASCII representation of the whole tree

To contents of the tree can be collected into an array in any of three ways. The tree itself can be used anywhere a collection is used.

bst.preorder()      # creates a preorder traversal list
bst.inorder()       # creates an inorder traveral list
bst.postorder()     # creates a postorder traversal list

key_string = ""
bst.set_iteration_style("pre")
for node in bst:
    key_string += str(node.get_key()) + " "

bst[80] = 4  # Store the value 4 with the key 80
bst[80]      # Retrieve the value associated with the key 80