AVL树是高度平衡的而二叉树。它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。
AVL树本质上还是一棵二叉搜索树，它的特点是：
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
既然是树，那么就要有节点：
View Code接下来我们给出AVL树的定义
template <class T> class AVLTree{ private: //根节点 AVLTreeNode<T>* Root; public: AVLTree():Root(NULL){}//构造函数 void add(T data);//添加节点的外部接口 int height();//查询高度的外部接口 int max(int a, int b);//比较两个数据的大小 private: AVLTreeNode<T>* add(AVLTreeNode<T>* &tree, T data);//添加节点的内部接口 int height(AVLTreeNode<T>* tree);//查询高度的内部接口 AVLTreeNode<T>* LL_Rotation(AVLTreeNode<T>* k2);//左左旋转的具体实现 AVLTreeNode<T>* RR_Rotation(AVLTreeNode<T>* k1);//右右旋转的具体实现 AVLTreeNode<T>* LR_Rotation(AVLTreeNode<T>* k3);//左右旋转的具体实现 AVLTreeNode<T>* RL_Rotation(AVLTreeNode<T>* k1);//右左旋转的具体实现 };
1.查询高度
/* 高度 作用：获取树的高度 */ template <class T>int AVLTree<T>::height(AVLTreeNode<T>* tree) { if (tree != NULL) return tree->height; return 0; } template <class T>int AVLTree<T>::height() { return height(Root); }
2.比较大小
