平衡二叉树(AVL树)

定义左右子树的高度为该结点的平衡因子，平衡二叉树的平衡因子只能是-1,0,1

• 平衡二叉树任意结点的左右子树高度差不超过1

• 平衡二叉树节点递推公式

  • n₀=1,n₁=1,n₂=2,n_h=n_h-2+n_h-1+1....( 斐波那契数，n₁是第一层，即根结点 )

• ALV是高度平衡的二叉树，查找效率最高，O(log₂n)

• ALV和红黑树的查找，删除，插入的平均时间复杂度都相同

调整

每次执行插入操作都需要进行调整使其再次成为平衡二叉树

每次调整的对象都是最小不平衡子树

• LL（左结点的左子树）

  • 右单旋转
  • 新插入的结点在BL上
  • 

• RR（右结点的右子树）

  • 左单旋转
  • 新插入的结点在BR上
  • 

• LR（左结点的右子树）

  • 先左后右双旋转
  • 新插入的结点在CL上
  • 

• RL（右结点的左子树）

  • 先右后左双旋转
  • 新插入的结点在CL上
  • 例：插入[15,3,7,10,9,8]

查找

n_h表示树高为h的AVL树含有的最少结点数

n₁=1,n₂=2,n₃=4,...,n_h=n_h-1+n_h-2+1

含有n个结点的平衡二叉树的最大高度为O(log₂n) 平均查找长度为O(log₂n)

删除

删除的时间复杂度：O(log₂n)

错题集

1. 

   答案与解析：

   
   答案： C
   解析：
   构造h层AVL树至少需要n_h个结点
   n₀=0
   n₁=1
   n₂=2
   n₃=1+2+1=4
   n₄=1+4+2=7
   n₅=1+7+4=12
   n₆=1+12+7=20
   

2. 

   答案与解析：

   
   答案： B
   解析：
   

3. 

   答案与解析：

   
   答案： A
   解析：