Hi! This is my webpage about red black trees. They're one of my favorite topics that I've learned about in CS400, and this webpage is devoted to documenting their awesomeness!
Red black trees (RBTs) are a special type of binary search tree (BST).
I'm glad you asked! A BST is a data structure where each node can have at most 2 children. Each value to the left of a node in the BST is less than (or equal to) the value in the starting node. Similarly, each value to the right of a node in a BST is greater than the value in the starting node. BSTs are good for storing sorted data because it takes less time to lookup data in them than in a data structure like an ArrayList.
RBTs have the same properties as BSTs. The key difference is that every node in an RBT is assigned a color: red or black. The extra properties of an RBT is related to the color of the nodes in the tree. These properties are:
Above are two examples of RBTs. The one on the left is incorrect and the one on the right is. The one on the let is incorrect because it violates the first and second proprty listed above. 21 and 60 are both red, yet 60 is 21's parent. This violates the first property (a red child cannot have a red parent). Moreover, if you trace the path from 100 to 60 to 21, the black height is one. However, if you trace the path from 100 to 145, the black height is two. Therefore, the black height is not equal throughout the tree (which violates the second property).
The RBT on the right is correct. There are no red nodes that have a red parent, and the black height is consistent throughout all paths through the tree. All of these paths are listed below, and you can see that the black height for each of these paths is 2.
The properties described above help balance an RBT. While BSTs have the potential to have a height equal to the number of elements, the color restrictions help an RBT have a maximum height of 2*log(n+1), where n is the number of nodes. This lower maximum height can make RBTs more efficient at finding values in the tree. That's pretty cool!
That's awesome! You've only seen the surface of RBTs and their awesomeness, and have a lot of fun things to learn about (including their insertion, removal, and rotation algorithms). One great resource to start you on this journey is this great RBT introduction by Geeks for Geeks!