additionally, after finding a node for insertion and deletion, the amortized complexity of the tree restructuring operations is constant. adding or deleting the node itself is constant time, the amount of rotations is always at most constant and it can be shown that the total amount of rank changes in the nodes is linear in the number of both insertions and deletions.