propose an efficient structure to implement an abstract type that represents\' p
ID: 3649839 • Letter: P
Question
propose an efficient structure to implement an abstract type that represents'partition of non-negative numbers in intervals. A partition is a set
[0, x1), [x1, x2) .....; [xm, 1) with x0 = 0 <x1 <x2 <? .... <Xm and
m = 0, 1: ....... The interface type includes the following operations
with a parameter x> 0
search (x) returns the interval [xi-1, xi) which contains x
merge (x) search x in [xk-1, xk), and replaces the intervals [xk-1, xk) and [xk, xk +1) by [xk-1, xk +1)
wafer (x) search x in [xk-1; xk), and replaces the interval [xk-1; xk) by [xk-1, x) and [x; xk)
Your structure must support the three operations in O (log m)
Explanation / Answer
Any balanced binary tree will be capable of supporting these operations. Read on AVL trees or Red Black trees. You keep the end points of the intervals in the tree. To find which interval x lies in simply search the tree and then find the number just greater than x and number just less than x and these will give you the interval Merge you search for interval in x then delete the number xk wafer(x) just insert x in the tree, message me if you need more explanation on this, first read on one of the trees.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.