Defination
An empty binary tree is height balanced. If T is a nonempty binary tree with $T_L$ and $T_R$ as its left and right subtrees, then T is height balanced iff
(1) $T_L$ and $T_R$ are height balanced
(2) $| h_L - h_R | \leq 1$ where $h_L$ and $h_R$ are the heights of $T_L$ and $T_R$ , respectively.
Insertion
Case 1: RR
Case 2: LL
similar to RR
Case 3: LR
Case 4: RL
Let $n_h$ be the minimum number of nodes in a height balanced tree of height h.
Then $n_h = n_{h-1}+n_{h-2}+1$
Fibonacci numbers:
$F_0=0,F_1=1,F_i=F_{i-1}+F_{i-2}$ , for $i > 1$
$\Rightarrow$ $n_h = F_{h+2}-1$, for $h \geq 0$
$\Rightarrow$ h = O(ln n)
性能评估
每次操作需要遍历从最底端到root的各个节点,时间复杂度为O(h),调整操作时间复杂度为O(1)。故每次操作时间复杂度为O(h)。
又 h = O(lnN)
故操作时间复杂度为O(lnN)
Exercises
$n_h = F_{h+2}-1 = F_{7+2}-1 = 34 - 1 = 33$
Code
1 |
|
1 | /** |
References
https://blog.csdn.net/Woolseyyy/article/details/51505383