Red-Black Tree - Understanding and Implementation.
Introduction In this article we will attempt to do the following: Gain an understanding on what a Red-Black Tree is, Get an idea on why we take the effort to reorder and recolor the RB-Tree every time we insert or remove a node, further, we will look into the algorithm for a RB-Tree insertion and removal, along with code implementation for the same in Java. Prerequisites: Java, Binary-Search Tree, Tree rotations. What is a Red-Black Tree? A Red-Black Tree (RB-Tree) is a self balancing Binary-Search Tree(BS-Tree), that follows a certain algorithm while inserting and removing nodes from the tree. This is done to guarantee an O(log n) search time(where n is the number of nodes in the tree), for every element. Further along with the usual variables, the nodes of a RB Tree has a bit(or any representation) that signify it as a red or black node. These colors will add a certain order to the nodes(we will get back to this) and is necessary for the algorithm. The main properties of a RB T...