平衡二叉树
(1)定义：平衡二叉树又被称为AVL树(区别于AVL算法)，它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
(2)构造与调整方法
平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树、左偏树等。
红黑树：红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 LeoJ. Guibas 和 RobertSedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。
AVL：AVL是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
Treap：Treap是一棵二叉排序树，它的左子树和右子树分别是一个Treap，和一般的二叉排序树不同的是，Treap纪录一个额外的数据，就是优先级。Treap在以关键码构成二叉排序树的同时，还满足堆的性质(在这里我们假设节点的优先级大于该节点的孩子的优先级)。但是这里要注意的是Treap和二叉堆有一点不同，就是二叉堆必须是完全二叉树，而Treap可以并不一定是。
伸展树：伸展树(Splay Tree)是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。
左偏树：堆结构是一种隐式数据结构(implicit data structure)，用完全二叉树表示的堆在数组中是隐式存贮的(即没有明确的指针或其他数据能够重构这种结构)。由于没有存贮结构信息，这种描述方法空间利用率很高，事实上没有空间浪费。尽管堆结构的时间和空间效率都很高，但它不适合于所有优先队列的应用，尤其是当需要合并两个优先队列或多个长度不同的队列时。因此需要借助于其他数据结构来实现这类应用，左偏树(leftist tree)就能满足这种要求。
(3)平衡二叉树
为了保证二叉排序树的高度为lgn，从而保证然二叉排序树上实现的插入、删除和查找等基本操作的平均时间为O(lgn)，在往树中插入或删除结点时，要调整树的形态来保持树的"平衡。使之既保持BST性质不变又保证树的高度在任何情况下均为O(lgn)，从而确保树上的基本操作在最坏情况下的时间均为O(lgn)。
注意：
①平衡二叉树(BalancedBinary Tree)是指树中任一结点的左右子树的高度大致相同。
②任一结点的左右子树的高度均相同(如满二叉树)，则二叉树是完全平衡的。通常，只要二叉树的高度为O(1gn)，就可看作是平衡的。
③平衡的二叉排序树指满足BST性质的平衡二叉树。
④AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。在最坏情况下，n个结点的AVL树的高度约为1.44lgn。而完全平衡的二叉树度高约为lgn，AVL树是接近最优的。
//AVL代码
#ifndefAVL_TREE_H
#defineAVL_TREE_H
#include"dsexceptions.h"
#include
usingnamespace std;
//AvlTree class
//
//CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
//
//******************PUBLIC OPERATIONS*********************
//void insert( x ) --> Insert x
//void remove( x ) --> Remove x(unimplemented)
//bool contains( x ) --> Return trueif x is present
//Comparable findMin( ) --> Returnsmallest item
//Comparable findMax( ) --> Returnlargest item
//boolean isEmpty( ) --> Return trueif empty; else false
//void makeEmpty( ) --> Remove allitems
//void printTree( ) --> Print treein sorted order
//******************ERRORS********************************