patternMinor
Maximal number of rotations after deleting a node in an AVL tree
Viewed 0 times
afterdeletingnumbernoderotationsavlmaximaltree
Problem
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$.
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$.
Solution
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:
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.
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.
Context
StackExchange Computer Science Q#52369, answer score: 2
Revisions (0)
No revisions yet.