24、平衡二叉树

　　(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 // For NULL

　　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********************************