3
$\begingroup$

What is the maximal number $c$ of single rotations after deleting a node from an AVL tree? We treat double rotations as two single ones.

I know that it is $O(\log n)$ but I'm trying to find a more precise number – it is in $[\log n, 2\log n]$ of course.

Nevertheless, I am dying to see the exact value of $c$.

$\endgroup$
2
$\begingroup$

Note: This does not answer the question exactly. However, it would be helpful for further study.


Quoted from Section 6.2.3 (entitled "Balanced Trees") of TAOCP "Sorting and Searching", 2nd Edition:

In order to figure out the running time of Algorithm A (for AVL search and insertion; [emphasis mine]), we would like to know the answers to the following questions:

  • How many comparisons are made during the search?
  • How much adjustment is needed in step A6?
  • How often do we need to do a single or double rotation?

Before going into details, it summarizes:

It is not difficult to derive upper bounds on the worst case running time, using Theorem A, but of course in practice we want to know the average behavior. No theoretical determination of the average behavior has been successfully completed as yet, since the algorithm appears to be quite complicated, but several interesting theoretical and empirical results have been obtained.

You would probably be interested in Theorem A mentioned above:

Theorem A (Adelson-Velsky and Landis). The height of a balanced tree with $N$ internal nodes always lies between $\lg(N + 1)$ and $1.4404 \lg(N + 2) - 0.3277$.

You can also find many empirical results (and some theoretical results) in the following paragraphs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.