0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ $O(n)$ is $O(1)$ per insertion/deletion in the the amortized sense. $\endgroup$
    – user16034
    Commented Feb 6, 2023 at 10:59
  • $\begingroup$ 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)$. $\endgroup$
    – MotiNK
    Commented Feb 6, 2023 at 12:34

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.