The following theorem summarizes the performance of the data structure:
Not included in the above theorem is the extra bonus
We will only sketch a proof of Theorem 9.2. By comparing and with the algorithms for adding or removing a leaf in a 2-4 tree, we can convince ourselves that this property is something that is inherited from a 2-4 tree. In particular, if we can show that the total time spent splitting, merging, and borrowing in a 2-4 tree is , then this implies Theorem 9.2.
The proof of this for 2-4 trees uses the potential method of amortized analysis.9.2 Define the potential of an internal node in a 2-4 tree as
Next notice that, if we ignore splitting and merging of nodes, there are only a constant number of nodes whose number of children is changed by the addition or removal of a leaf. When adding a node, one node has its number of children increase by 1, increasing the potential by at most . During the removal of a leaf, one node has its number of children decrease by 1, increasing the potential by at most , and two nodes may be involved in a borrowing operation, increasing their total potential by at most .
To summarize, each merge and split causes the potential to drop by at least 2. Ignoring merging and splitting, each addition or removal causes the potential to rise by at most 3, and the potential is always non-negative. Therefore, the number of splits and merges caused by additions or removals on an initially empty tree is at most . Theorem 9.2 is a consequence of this analysis and the correspondence between 2-4 trees and red-black trees.