Insertion
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 ...
Get Swift Data Structure and Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
