TIRGUL 4 in Data Structure – solution of last question – draft

(Remember that these notes are unchecked and spelling mistakes and inaccuracies may be plentiful)

Elad Verbin

March 30, 2006

\underline{Exercise:} Prove that a sequence of m insertions into an initially-empty 2-4 tree costs a total of O(m) time, assuming that at each insertion you are given a pointer to the location where the item should be inserted.

\underline{Proof:} Using the potential method. We use the potential Φ which is equal to the number of nodes of degree 4. (many other potential functions would also work). We have to prove two things: (1) That the potential is initially equal to 0 and is always nonnegative; and (2) That for any operation op, cost(op) + ΔΦ ≤ O(1).

(1) is obvious. Let us prove (2). Every insertion operation costs O(1) + k where k is the number of SPLIT operations that are performed. Every split causes a node of degree 4 to split into a node of degree 2 and a node of degree 3. Therefore, every SPLIT operation decreases the potential by 1. This is true except for the first SPLIT, which is on a leaf and therefore splits a node with degree 0 to two nodes with degree 0, and for the last SPLIT, which indeed splits a node v of degree 4 to two nodes of degrees 2 and 3, but the father may change to be of degree 4 which may increase the potential back by 1. But since these are only the first and last SPLIT, all other SPLITs decrease the potential by 1, and so ΔΦ ≤ −(k − 2). From this it follows that, indeed, cost(op) + ΔΦ = O(1).

(I will review this in the beginning of the next TIRGUL).