__________ is a Self Balancing binary search tree, where the path from the…

Answer: Red-Black tree

Explanation: A red-black tree is a self-balancing binary search tree that enforces color and black-height properties so that no path from the root to a leaf is more than twice as long as any other. This ensures the tree height is O(log n).

• Each node is colored either red or black.

• The root is black, and all leaves (external NIL nodes) are considered black.

• If a node is red, both its children must be black (no two consecutive red nodes).

• For every node, every path to its descendant leaves contains the same number of black nodes (black-height).

• Consequence: the longest root-to-leaf path is at most twice the shortest, ensuring balanced height and O(log n) time for search, insert, and delete.