跳转至

AVL Trees

Adelson-Velskii-Landis[AVL] Trees

Definition

  • The balance factor BF(node) = \(h_L - h_R\).
  • In an AVL Tree, BF(node) = -1, 0, 1.

Different Trees

  • Perfect Binary Tree
  • Complete Binary Tree
  • Full Binary Tree: has two leaf nodes or not. e.g. Huffman Tree

Rotation

  • LL Rotation/RR Rotation

    • Two Single Rotation
  • LR Rotation/RL Rotation

    • Double Rotation

Analysis

Let \(n_h\) be the minimum number of nodes in a height balanced tree of height \(h\)

\[ \begin{aligned} n_h &= n_{h-1} + n_{h-2} + 1\\ (n_h + 1) &=(n_{h-1}+1)+(n_{h-2}+1)\\ F_h &= F_{h-1} + F_{h}\ [F_{h+2} = n_h + 1,F_3=2=n_1+1]\\ F_h&\approx\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^h\\ n_h&\approx\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{h+2}-1\\ h&=O(\ln{n}) \end{aligned} \]