Python red-black trees
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.
What is this for?
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 useing the SortedContainers library.
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.
Standard red-black tree interface
A new red-black tree can be constructed as follows:
bst = RedBlackTree()
Items can be inserted into a tree using the
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
Minimum and maximum
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.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.
Predecessor and successor
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 use various printing methods:
bst.print_tree() # prints an ASCII representation of the whole tree bst.preorder() # prints a preorder traversal bst.inorder() # prints an inorder traveral bst.postorder() # prints a postorder traversal
bst = 4 # Store the value 4 with the key 80 bst # Retrieve the value associated with the key 80