Editor">
Editor Staff asked 5 months ago
Editor Staff asked 5 months ago
LLRB maintains 1-1 correspondence with 2–3 trees.
(a) True
(b) False
This is a very interesting question from B-Trees topic in section B-Trees of Data Structures & Algorithms I
The question was posed to me during an online exam.
1 Answers
Editor">Editor Staff answered 5 months ago
Editor Staff answered 5 months ago
Right option is (a) True
Easiest explanation – LLRB (Left Leaning Red Black tree)is the data structure which is used to implement the 2-3 tree with very basic code. The LLRB is like the 2-3 tree where each node has one key and two links. In LLRB the 3-node is implemented as two 2-nodes connected by the red link that leans left. Thus, LLRB maintains 1-1 correspondence with 2–3 tree.
