Balanced Binary Tree

掌握平衡二叉树的创建

所有非叶结点的平衡因子均为 1 （即平衡二叉树满足平衡的最少结点情况）的平衡二叉树，其结点数的递推公式：

$n_0=0,n_1=1,n_2=2,n_h=1+n_{h-1}+n_{h-2}$ ($h$ 为平衡二叉树的高度，$n_h$ 为构造此高度的平衡二叉树所需的最少结点数)

《王道数据结构》P192 T13

AVL树的定义

AVL树 可视化

AVL，在二叉排序树的基础上，任意结点的平衡因子的绝对值不超过1。

平衡因子：左子树高度-右子树高度

平衡二叉树的意义：

避免二叉排序树变成“链表”，即最坏的情况。

保证搜索的效率。

高度为h的最小平衡二叉树的 结点数$N_h$

递推关系：$N_h=N_{h-1}+N_{h-2}+1$ $N_0=0,N_1=1$

平衡二叉树的判断

利用递归的后序遍历过程：

1. 判断左子树是平衡二叉树
2. 判断右子树是平衡二叉树
3. 判断以该结点为根的二叉树为平衡二叉树