Summary
We saw how a simple BST could degenerate into a linked list, for example, when we insert sorted data into the tree. In this case, instead of logarithmic lookup complexity, we should get a far slower, O(n) runtime complexity.
To make sure that the tree operations are logarithmic, we need to balance the tree. We learned about perfectly balanced trees, which are rare. Instead, height-balanced trees, which are almost balanced are good for us.
We touched upon some terms such as height of a node and internal nodes. Next, we looked at tree rotations, which are the basic building blocks for rebalancing a tree.
Red-Black trees are balanced BSTs, with every node colored in either red or black. There are two important invariants that need to be maintained.
We then had a detailed look at how inserting a node into a Red-Black tree keeps it balanced. Rebalancing is somewhat involved; however, we saw each case separately. Using in-order traversal, we showed how the rotations rebalance the tree without...
