# How many times is a node rotated towards the root in a weight-balanced tree?

In this paper they prove that the number of rotations after doing $$n$$ insertions or deletions to a weight-balanced tree is $$O(n)$$ (when starting from an empty tree).

What isn't clear to me though is how many times each node becomes the new root of a sub-tree after a single or double rotation takes place. Intuitively, I should expect this to be $$O(1)$$. Is this correct? How can this be shown?

• $O(n)$ is $O(1)$ per insertion/deletion in the the amortized sense. Feb 6 at 10:59
• I'm well aware of that. But ned for a bound for individual nodes, or at least for paths from root to leaves and not in the amortized sense. Consider for example a case where a node has become the new root of a sub-tree $O\left(\frac{n}{2^k\log n}\right)$ times, where $k$ is the depth from the root. In this case, the total for each level in the tree would be $O\left(\frac{n}{\log n}\right)$, and for the whole tree it would be $O(n)$. But if we consider a path from the root to leaves (which is what I'm interested in), we'd have a total of $O\left(\frac{n}{\log n}\right)$ and not $O(\log n)$. Feb 6 at 12:34