In this article , I have covered some basic concepts of Red Black Trees !
What are Red Black Trees ?
In Red-black trees each node is associated with an extra attribute: the color, which is either red or black. To get logarithmic complexity we impose the following restrictions.
Definition: A Red-black tree is a binary search tree that satisfies the following properties:
1. Each tree node is colored either red or black.
2. The root node of the tree is always black.
3. Every path from the root to any of the leaf nodes must have the same number of black nodes.
4. No two red nodes can be adjacent, i.e., a red node cannot be the parent or the child of another red node.
Why we use Red Black Trees ?
In short, it simplifies the implementation of the tree and the operations. We can use the same operations as for a binary tree (for example, finding a value works exactly the same way as in a “normal” binary tree).
Since the Red Black Trees are also self balancing like AVL , it is slightly better then AVL in terms of numbers of rotation .
What is the Speciality of Red Black Trees ?
The time complexity of insetion or deletion in Red Black Trees is always : O(log n) , either best or worst . While in AVL trees , the worst time complexity if O(h) sometimes .
Where to go from here ?
My LinkedIn :- linkedin.com/in/my-pro-file
Topics You may Interested IN :
- Representation of Graph and Intro to it : https://medium.com/@mdcode2021/representation-and-introduction-of-graph-dfb232a1ae2e
- BST , Tree : https://medium.com/dev-genius/trees-binary-search-trees-and-traversal-ab63e192f3a7
- Heap and Prioriy Queue : https://medium.com/@mdcode2021/heap-and-priority-queue-fbd41333dc0d
- All About Doubly Linked List : https://medium.com/@mdcode2021/all-about-doubly-linked-list-30f0f08afb9c
