✨ Add Red-Black Tree Implementation

[Kalkwst]

A red-black tree is a type of self-balancing binary search tree, which is used to efficiently store and retrieve data. It is similar to other types of self-balancing trees, such as AVL and AA trees, in that it automatically adjusts the structure of the tree to maintain a balance between its left and right branches. This ensures that the tree remains relatively balanced even as elements are added or removed, which improves the performance of search and insertion operations.

From a more technical perspective, a red-black tree is a self-balancing binary search tree that uses the concept of colour to ensure balance. Each node in the tree can be coloured either red or black, and the tree is balanced by enforcing certain constraints on the colour of the nodes. The constraints ensure that the number of black nodes on any path from the root to a leaf is the same for all paths and that no red node has a red child. When a new node is added to the tree, it is placed in the correct position based on its value and the tree is adjusted accordingly to maintain the balance and the constraints of the colour. The tree can be adjusted by performing rotations on the nodes and/or flipping the colour of the nodes. This way the tree can be adjusted to maintain the balance and ensure the constraints of the colour. The time complexity for search, insertion and deletion operations in a red-black tree is O(log n), which is faster than the O(n) time complexity of a typical unbalanced binary search tree.