1. 树的基本概念

树是一种重要的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

现在通过实例来分析平衡二叉树的实现过程，以便更好地理解。

选取一组数据分别为

AVL tree基本概念

AVL树前提是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。

平衡因子BF（balance Factor）：二叉树结点的左子树深度与右子树深度的值，AVL树上所有节点的BF只能是-1、0、1，如果二叉树上有一个节点的BF的绝对值大于1，那么这个二叉树就是不平衡的。