Algorithm

successor of an element

Assume that you are given a 2-3 tree T containing n distinct elements (a) (4 points) Show how to find the successor of a given element x E T in time O(logn) b) (4 points) Show that if the input element 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. (c) (6 points) Show that the 2-3 trees can be augmented while maintaining v.succ, such that the INSERET and DELETE operations can still be performed in O(log n) time. (Hint: Think of a doubly-linked list.) Assume that you are given a 2-3 tree T containing n distinct elements (a) (4 points) Show how to find the successor of a given element x E T in time O(logn) b) (4 points) Show that if the input element 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. (c) (6 points) Show that the 2-3 trees can be augmented while maintaining v.succ, such that the INSERET and DELETE operations can still be performed in O(log n) time. (Hint: Think of a doubly-linked list.)