<p>I know that for an AVL tree of N nodes, the depth of the tree is bounded by
<span class="math-container">$$ \log_2(N + 1) -1 \leq height \leq c \log_2(N + 2) + b$$</span></p>
<p>where <span class="math-container">$c,b$</span> are taken from the golden ratio linked to the worst case of the tree, i.e. <span class="math-container">$c = 1/ \log_2(\varphi)$</span> and <span class="math-container">$b = c/2 \log_2(5) - 3$</span>.</p>
<p>I am interested in reducing this bound (up to some probability) granted that the elements inserted in the trees are generated randomly, with entropy <span class="math-container">$H$</span>. In my application, I have exactly <span class="math-container">$2^k$</span> elements of size <span class="math-container">$2^l$</span> to be inserted, where <span class="math-container">$k\ll l$</span>.</p>
<p>I know that asymptotically a randomly generated tree will have depth very close to the theoretical lower bound, and I could find some experimental results reducing this upper bound - I can refer to <em><strong>Data Structures and Algorithms</strong></em> by Drozdek or <em><strong>The Art of Computer Programming</strong></em> by Knuth (which itself refers to the work of C. C. Foster) - but I am looking for a more concrete answer with error probability rather than only asymptotic arguments or experimental results. Would you happen to have any material support discussing this approach, of random or pseudo-random insertions in a sorted tree?</p>
<p><strong>Note:</strong> For those interested, Knuth suggests an average of  <span class="math-container">$1.01 \log(N) + 0.1$</span> comparisons for the <span class="math-container">$N$</span>th insertion in an AVL tree with random elements, except for small <span class="math-container">$N$</span>. From my own experiments, it seems that a close upper bound would be <span class="math-container">$1.2 \log(N) + 0.1$</span>, though I could not test it over <span class="math-container">$2^{24}$</span> due to insufficient memory.</p>

CC BY-SA 4.0
2020-08-19T02:00:48.523Z
Are you aware of Flajolet's work on average-case analysis of data structures?  I don't know if there is anything specifically relevant to your question, but if you haven't checked you might try.  E.g. https://dl.acm.org/doi/10.5555/114872.114881
Neal Young
CC BY-SA 4.0
2020-08-19T02:27:41.647Z
I didn't know about it. Thanks! I'll check this out
Binou
CC BY-SA 4.0
2020-08-19T14:44:33.853Z
In their book "An Introduction to the Analysis of Algorithms", Sedgewick and Flajolet give the generating function of AVL trees of some height. May be you can derive a formula for your problem from this generating function, but it doesn't seem to be easy.
Lamine
<sorting><tree><binary-trees><bounded-depth>
Height of AVL tree with random elements
Binou
# Height of AVL tree with random elements

(Asked by: username_0 on 2020-08-18)

I know that for an AVL tree of N nodes, the depth of the tree is bounded by
$$ \log\_2(N + 1) -1 \leq height \leq c \log\_2(N + 2) + b$$

where $c,b$ are taken from the golden ratio linked to the worst case of the tree, i.e. $c = 1/ \log\_2(\varphi)$ and $b = c/2 \log\_2(5) - 3$.

I am interested in reducing this bound (up to some probability) granted that the elements inserted in the trees are generated randomly, with entropy $H$. In my application, I have exactly $2^k$ elements of size $2^l$ to be inserted, where $k\ll l$.

I know that asymptotically a randomly generated tree will have depth very close to the theoretical lower bound, and I could find some experimental results reducing this upper bound - I can refer to ***Data Structures and Algorithms*** by Drozdek or ***The Art of Computer Programming*** by Knuth (which itself refers to the work of C. C. Foster) - but I am looking for a more concrete answer with error probability rather than only asymptotic arguments or experimental results. Would you happen to have any material support discussing this approach, of random or pseudo-random insertions in a sorted tree?

**Note:** For those interested, Knuth suggests an average of $1.01 \log(N) + 0.1$ comparisons for the $N$th insertion in an AVL tree with random elements, except for small $N$. From my own experiments, it seems that a close upper bound would be $1.2 \log(N) + 0.1$, though I could not test it over $2^{24}$ due to insufficient memory.

**Tags:** sorting, tree, binary-trees, bounded-depth
> **Comments:**
> **username_1**: Are you aware of Flajolet's work on average-case analysis of data structures?  I don't know if there is anything specifically relevant to your question, but if you haven't checked you might try.  E.g. https://dl.acm.org/doi/10.5555/114872.114881  
> **username_0**: I didn't know about it. Thanks! I'll check this out  
> **username_2**: In their book "An Introduction to the Analysis of Algorithms", Sedgewick and Flajolet give the generating function of AVL trees of some height. May be you can derive a formula for your problem from this generating function, but it doesn't seem to be easy.  

---

## 0 answers

