AVL Trees¶
Why we need AVL Trees?¶
Target of AVL Trees¶
The target of AVL Trees is to speed up searching, especially to handle dynamic searching.
What is dynamic searching?¶
Dynamic searching is a searching with insertion and deletion.
The data set is not fixed. It's dynamic.
Ex: Binary search tree.
In some case, we would get a skew tree which skew to one side.(也就是一棵向一边偏的树)
Average search time¶
每个节点的高度（最上方为0）+1之和/节点数
The function of AVL tree¶
The function of AVL tree is to keep the tree dynamically balanced.
If the tree is not balanced, then we let them become balanced.
添加很简单，删除很难
The definition of AVL tree¶
BF (Balance factor)¶
Single rotations¶
Trouble finder¶
The trouble finder is the first node that signals the trouble.
Ex
In this example, trouble finder is Mar.
Double rotation¶
Other ways to implement AVL trees¶
- For example, we can use height to replace BF to construct an AVL tree.
The height of the AVL tree¶
We know that \(T_p=O(h)\), where h is the height og the tree.
But \(h=?\)
推导证明\(h=O(\ln n)\)
so we can gain function like this:
证明成功
Problem Set¶
1¶
Result shown as below.
So the answer is B.
2¶
From the formula: $$ n_h=n_{h-1}+n_{h-2}+1 $$ 然后我们就可以依次列出答案