Tree — Part2
In this story, I want to talk about Binary Tree Traversal.
Totaly we have 3 different types of left-to-right Traversal which names are:
1- Pre-Order
2- Post-Order
3- In-Order
let me talk about the above types and after that, I try to explain one of my favourable BST algorithms which name is RED-BLACK.
Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time. Not only does this make them valuable in time-sensitive applications such as real-time applications, but it makes them valuable building blocks in other data structures which provide worst-case guarantees.
1- Pre-Order Traversal
When we first visit a root Node and then visit Left Node and Right Node recursively.
The Root will be the First Node Visited.
2- Post-Order Traversal
When we first visit recursively left and right nodes and then visit a root node.
The root will be the last node visit.
3- In-Order Traversal
When we visit the left child recursively, then the root node and then the right child nodes.
In continue, I want to talk about RED-Black and write an example for inserting and Deleting in the tree with RED-Black, and I want to ask two questions that:
What is Red-Black?
In a short answer, I should say, Red-Black Tree is a self-balancing Binary Search Tree (BST) where every node follows the following rules.
Why Red-Black Trees?
Most of the BST operations such as search, max, min, insert, delete, and …take O(h) time where h is the height of the BST.
The cost of these operations may become O(n) and If we make sure that the height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of a Red-Black tree is always O(Logn) where n is the number of nodes in the tree.
So according to the above explanation, I want to add a field in my Node Class that I wrote in the previous story.
Insertion
Basic Strategy is to maintain a 1–1 correspondence with 2–3 tree by applying elementary Red-Black BST operations.
In simply put, In each situation if you add value on the right node you should do rotate right node to balance a max of three-node (left-root-right) on the root of three nodes.
Case 1:
Insert into a 2-node at the bottom.
- Do standard BST insert; Color new link Red.
- If new Red-link is a right link, rotate left.
Case 2:
Insert into a 3-node at the bottom.
- Do standard BST insertion; color new link Red.
- Rotate to Balance the 4-node (if needed)
- Flip colors to pass red link up one level.
- Rotate to make lean left (if needed)
For Implementing :
- Right child red, left child black: Call Rotate Left Method
(left rotation: Orient a right-leaning red link to lean left)
- Left child and left-left grandchild red: Call Rotate Right Method
(right rotation: Orient a left-leaning red link to lean right)
- Both children Red: call FlipColor Method
(recolor to split a 4-node)
and finally, insert method:
Height of tree is ≤2lgN in the worst-case, every path from the root to null has the same number of black links and never two red links in-a-row.
Please for checking the Deletion method, visit the Complete source of Red-Black in my GitHub.
To access to the completed source, please check Room Project on this link, also you can find different challenges approach of LeetCode and HackerRank in the mentioned Link.
Resources: Algorithms Robert Sedgewick, Wikipedia
