Q49.Marks: +2.0UGC NET Paper 2: Computer Sc 23rd August 2024 Shift 1
_________ is a Self Balancing binary search tree, where the path from the root to the furthest leaf is no more than twice as long as the path from the root to nearest leaf.
1.Expression tree
2.Game tree
3.Red-Black tree✓ Correct
4.Threaded tree
Solution
The correct answer is Red-Black tree
Key Points
Red-Black Tree: A Red-Black tree is a type of self-balancing binary search tree.
It maintains balance by ensuring that the longest path from the root to a leaf is no more than twice as long as the shortest path from the root to any leaf.
This balancing property ensures that the tree remains approximately balanced, allowing operations such as insertion, deletion, and lookup to be performed in O(logn) time.
Additional Information
Expression Tree: A binary tree used to represent expressions, not necessarily balanced.
Game Tree: A tree representation of the possible moves in a game, not a self-balancing binary search tree.
Threaded Tree: A binary tree in which null pointers are made to point to the in-order predecessor or successor, not specifically self-balancing.
