Assume that you are given a 2-3 tree T containing n distinct elements. Show how
ID: 674647 • Letter: A
Question
Assume that you are given a 2-3 tree T containing n distinct elements. Show how to find the successor of a given element x T in time O(log n). Show that if the input element x is chosen uniformly at random from T, then your procedure from part (a) runs in expected time O(1). Assume that we wish to augment our 2-3 tree data structure so that that each node v maintains a pointer v.succ to the successor of v, so that queries for the successor of an element can be answered in O(1) time worst-case. Show that the 2-3 trees can be augmented while maintaining v.succ, such that the Insert and Delete operations can still be performed in O(logn) time.Explanation / Answer
(a) (4 points) Show how to find the successor of a given element x T in time O (log n ).
Solution:
Tree-Successor ( x ) 1 If x 6 = x.p.right 2 Return x.p.left (If there is a middle child, then return x.p.middle ) 3 Else 4 y = x.p 5 While y = y.p.right and y.p 6 = NIL 6 y = y.p 7 If y.p = NIL 8 Return NIL 9 y = y.right 10 While y.left 6 = NIL 11 y = y.left 12 Return y.
(b) (4 points) Show that if the input element x is chosen uniformly at random from T , then your procedure from part (a) runs in expected time O (1).
Solution:
If the input element x is chosen uniformly at random from T , the probability of choosing each node is 1 n . If the chosen node is not the right child of its parent, then the running time is O (1). If the chosen node is the right child, the algorithm would check if its parent is the right child. In this condition, the expected running time T ( n ) = O (1).
(c) (6 points) Show that the 2-3 trees can be augmented while maintaining v.succ , such that the Insert and Delete operations can still be performed in O (log n ) time. ( Hint : Think of a linked list).
Solution:
Insert ( T,z ) 1 y = NIL 2 x = T.root 3 While x has children 4 y = x 5 If z.key < x.left.key 6 x = y.left 7 Else If z.key < x.middle.key (if there is a middle child) 8 x = y.middle 9 Else x = y.right 10 If y.num = 2 11 z.p = y 12 If z.key < x.key 13 x.pred.succ = z 14 z.pred = x.pred 15 z.succ = x 16 x.pred = z 17 Else 18 x.succ = z 19 z.pred = x 20 z.succ = NIL 21 Else 22 Split node y , Let z and x share a same parent 23 If z.key < x.key 24 Maintain the linked list as step 13 - 16 25 Else 26 Maintain the linked list as step 18 - 20 27 Recursively maintain the 2-3 tree Delete ( T,z ) 1 If z.p.num = 3 2 z.pred.succ = z.succ 3 z.succ.pred = z.pred 4 Else 5 z.pred.succ = z.succ 6 z.succ.pred = z.pred 7 If an adjacent sibling s has three children 8 s gives z.p one of its children 9 Else s and z.p are merged into a single node 10 Recursively do above step to maintain 2-3 tree.