We have built a base class with some helper methods that represents a red-black tree node/tree. We also have an enumeration to handle the colors. We implemented two rotation methods: left and right. You are ready to learn about the insertion process.
The insertion process in the case of red-black trees is tricky, because we always need to maintain the five color conditions. The insertion process has different scenarios where it can impact those rules, so we have to make the process in a way that ensure the rules at all costs.
In order to simplify things, we are going to do the insertion in a two-step process:
Insert the node as we did in binary search trees, by setting the color red by default.
As it is possible that the first step destroyed one or more of the color rules, we will review the tree color structure and make modifications to fix those broken rules.
Let's add the following methods to the RedBlackTreeNode class:
// MARK: Insertion //Insert operation methods public...