3
$\begingroup$

I need some help with the following problem

Definition: A (2,5)-tree is an external search tree, where all leaves have the same depth. Each inner node in a (2,5)-tree has at least 2, and at most 5 children.

An insert-operation consists of two parts. In the first part, we go down a suitable path from the tree's root to a leaf and the additional node is inserted as a child of the parent of this leaf. However, in doing this the condition on the degree ($\deg \le 5$) of the parent may be violated. So in a second part of the insert-operation, we must make up for this. (By splitting the parent into two nodes, and assigning to each node half the children)

The costs of this second part will be called rebalancing costs in the following. (The costs are given by how many times a node changes its parent)

A delete-operation works similarly: localise the node in a first step, then cut it off and rectify possible violations of the condition on the degree. (By either adopting an additional child from a neighbour or by combining the parent and a neighbour into a single node)


Problem: Using amortized analysis, prove the following:

  • Starting with an empty (2,5)-tree, inserting $n$ Elements has a total cost of no more than $2n$.
  • Starting with an empty (2,5)-tree, $n$ insert-/delete-operations (in arbitrary order) have a cost of no more than $2n$.

(This is my try at a translation from German, so I apologize if it is hard/impossible to follow; if you feel you can improve readability, please do so)

I think I can get an upper bound of $5n$ for the first part: Let $\phi(i)$ be the number of nodes with $5$ children after $i$ insert-operations. Then

$$\phi(i) - \phi(i-1) = \begin{cases} 0 & \text{if the inserted node has $<4$ siblings} \\ 1 & \text{if the inserted node has $4$ siblings} \\ -m & \text{if we have to rebalance $m$ times} \end{cases}$$

And the time-costs are (after inserting the node: to rebalance once, we must create a new parent and assign $3$ children to the new parent - giving a rebalancing-cost of 4)

$$t(i)- t(i-1) = \begin{cases} 1 & \text{if the inserted node has $<4$ siblings} \\ 1 & \text{if the inserted node has $4$ siblings} \\ 1+4m & \text{if we have to rebalance $m$ times} \end{cases}$$

Therefore $[t(i)+4\phi(i)]- [t(i-1)+4\phi(i-1)] \le 5$, implies

$$t(n) \le t(n) + 4\phi(n) \le 5n + t(0) + 4\phi(0) = 5n$$

How could I improve this estimate? What is the right potential here? Should I maybe use a different method?

Any suggestions would be very much appreciated! Thanks for reading.

  • 0
    If I remember correctly, this can be done using the Accounting method.2012-01-26
  • 0
    This is what is meant by "amortised analysis". Sam, I don't see how `insert` as described by you ensures that all leaves are on the same level. You should give precise formulations of the investigated operations, in particular rebalancing.2012-01-27
  • 0
    I think your $t(i) - t(i-1)$ is wrong. In particular, why should the difference be one in the trivial cases? The inserted nodes might end up on the same level and thusly cause the same cost.2012-01-27
  • 0
    Yea, I think "cost" should be read in a way that makes it dependent on elemnt depth, otherwise it does not make much sense imho. Can you ask the person who gave you the problem? Note that what you describe does not "re*balance*" the tree; in general, a linear list may be constructed.2012-01-27
  • 0
    @Raphael: I think you misunderstood the rebalancing-operation. Let me try to describe it better: Say we insert a note $x_0$ into some part of the tree. If the parent $x_1$ of $x_0$ now has more than $5$ children, then we create a new node $x_1'$ and assign half the children of $x_1$ to $x_1'$. Let $x_2$ be the common parent of $x_1$ and $x_1'$ (I think this is where I was unclear in my description - we create the new node as a child of $x_1$'s parent, not as a child of $x_1$). $x_2$ now has an additional child. If it has more than 5, create a new node $x_2'$, assign half the children of...2012-01-27
  • 0
    ... $x_2$ to $x_2'$ and look at the common parent $x_3$ of $x_2$ and $x_2'$. Check whether $x_3$ has more than 5 children. If so then create a new node $x_3'$ assign half of $x_3$'s children to $x_3'$ and check whether $x_4$ (the common parent of $x_3$ and $x_3'$) has more than 5 children etc. etc. going up the tree, dividing nodes as long as we have to divide them, in order to keep a balanced tree.2012-01-27
  • 0
    @Aryabhata: Thanks for your suggestion. Do you maybe remember *where* you might have seen this done using the accounting method? Any pointers where I could look for it would be welcome!2012-01-27
  • 0
    @Sam: Sorry I don't recollect. Perhaps when I took the course a long time back.2012-01-27
  • 0
    @Aryabhata: Ok, never mind then. Thanks for the hint anyways. =)2012-01-27

0 Answers 0