平衡二叉树
(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********************************
//Throws UnderflowException as warranted
template
classAvlTree
{
public:
AvlTree( ) : root( NULL ) { }
AvlTree( const AvlTree & rhs ) : root(NULL )
{
*this = rhs;
}
~AvlTree( )
{
makeEmpty( );
}
/**
* Find the smallest item in the tree.
* Throw UnderflowException if empty.
*/
const Comparable & findMin( ) const
{
if( isEmpty( ) )
throw UnderflowException( );
return findMin( root )->element;
}
/**
* Find the largest item in the tree.
* Throw UnderflowException if empty.
*/
const Comparable & findMax( ) const
{
if( isEmpty( ) )
throw UnderflowException( );
return findMax( root )->element;
}
/**
* Returns true if x is found in the tree.
*/
bool contains( const Comparable & x )const
{
return contains( x, root );
}
/**
* Test if the tree is logically empty.
* Return true if empty, false otherwise.
*/
bool isEmpty( ) const
{
return root == NULL;
}
/**
* Print the tree contents in sorted order.
*/
void printTree( ) const
{
if( isEmpty( ) )
cout << "Emptytree" << endl;
else
printTree( root );
}
/**
* Make the tree logically empty.
*/
void makeEmpty( )
{
makeEmpty( root );
}
/**
* Insert x into the tree; duplicates areignored.
*/
void insert( const Comparable & x )
{
insert( x, root );
}
/**
* Remove x from the tree. Nothing is doneif x is not found.
*/
void remove( const Comparable & x )
{
cout << "Sorry, removeunimplemented; " << x <<
" still present"<< endl;
}
/**
* Deep copy.
*/
const AvlTree & operator=( constAvlTree & rhs )
{
if( this != &rhs )
{
makeEmpty( );
root = clone( rhs.root );
}
return *this;
}
private:
struct AvlNode
{
Comparable element;
AvlNode *left;
AvlNode *right;
int height;
AvlNode( const Comparable &theElement, AvlNode *lt,
AvlNode *rt, int h = 0 )
: element( theElement ), left( lt ),right( rt ), height( h ) { }
};
AvlNode *root;
/**
* Internal method to insert into asubtree.
* x is the item to insert.
* t is the node that roots the subtree.
* Set the new root of the subtree.
*/
void insert( const Comparable & x,AvlNode * & t )
{
if( t == NULL )
t = new AvlNode( x, NULL, NULL );
else if( x < t->element )
{
insert( x, t->left );
if( height( t->left ) - height(t->right ) == 2 )
if( x left->element )
rotateWithLeftChild( t );
else
doubleWithLeftChild( t );
}
else if( t->element < x )
{
insert( x, t->right );
if( height( t->right ) - height(t->left ) == 2 )
if( t->right->element< x )
rotateWithRightChild( t );
else
doubleWithRightChild( t );
}
t->height = max( height( t->left), height( t->right ) ) + 1;
}
/**
* Internal method to find the smallestitem in a subtree t.
* Return node containing the smallestitem.
*/
AvlNode * findMin( AvlNode *t ) const
{
if( t == NULL )
return NULL;
if( t->left == NULL )
return t;
return findMin( t->left );
}
/**
* Internal method to find the largest itemin a subtree t.
* Return node containing the largest item.
*/
AvlNode * findMax( AvlNode *t ) const
{
if( t != NULL )
while( t->right != NULL )
t = t->right;
return t;
}
/**
* Internal method to test if an item is ina subtree.
* x is item to search for.
* t is the node that roots the tree.
*/
bool contains( const Comparable & x,AvlNode *t ) const
{
if( t == NULL )
return false;
else if( x < t->element )
return contains( x, t->left );
else if( t->element < x )
return contains( x, t->right );
else
return true; // Match
}
/****** NONRECURSIVEVERSION*************************
bool contains( const Comparable & x,AvlNode *t ) const
{
while( t != NULL )
if( x < t->element )
t = t->left;
else if( t->element < x )
t = t->right;
else
return true; // Match
return false; // No match
}
*****************************************************/
/**
* Internal method to make subtree empty.
*/
void makeEmpty( AvlNode * & t )
{
if( t != NULL )
{
makeEmpty( t->left );
makeEmpty( t->right );
delete t;
}
t = NULL;
}
/**
* Internal method to print a subtreerooted at t in sorted order.
*/
void printTree( AvlNode *t ) const
{
if( t != NULL )
{
printTree( t->left );
cout << t->element<< endl;
printTree( t->right );
}
}
/**
* Internal method to clone subtree.
*/
AvlNode * clone( AvlNode *t ) const
{
if( t == NULL )
return NULL;
else
return new AvlNode( t->element,clone( t->left ), clone( t->right ), t->height );
}
// Avl manipulations
/**
*Return the height of node t or -1 if NULL.
*/
int height( AvlNode *t ) const
{
return t == NULL ? -1 : t->height;
}
int max( int lhs, int rhs ) const
{
return lhs > rhs ? lhs : rhs;
}
/**
* Rotate binary tree node with left child.
* For AVL trees, this is a single rotationfor case 1.
* Update heights, then set new root.
*/
void rotateWithLeftChild( AvlNode * &k2 )
{
AvlNode *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max( height(k2->left ), height( k2->right ) ) + 1;
k1->height = max( height(k1->left ), k2->height ) + 1;
k2 = k1;
}
/**
* Rotate binary tree node with rightchild.
* For AVL trees, this is a single rotationfor case 4.
* Update heights, then set new root.
*/
void rotateWithRightChild( AvlNode * &k1 )
{
AvlNode *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max( height(k1->left ), height( k1->right ) ) + 1;
k2->height = max( height(k2->right ), k1->height ) + 1;
k1 = k2;
}
/**
* Double rotate binary tree node: firstleft child.
* with its right child; then node k3 withnew left child.
* For AVL trees, this is a double rotationfor case 2.
* Update heights, then set new root.
*/
void doubleWithLeftChild( AvlNode * &k3 )
{
rotateWithRightChild( k3->left );
rotateWithLeftChild( k3 );
}
/**
* Double rotate binary tree node: firstright child.
* with its left child; then node k1 withnew right child.
* For AVL trees, this is a double rotationfor case 3.
* Update heights, then set new root.
*/
void doubleWithRightChild( AvlNode * &k1 )
{
rotateWithLeftChild( k1->right );
rotateWithRightChild( k1 );
}
};
#endif
济宁人力资源和社会保障局济宁2015年下半年软考证书领取联系电话
[考试动态]2016年4月26日邹城人力资源和社会保障局邹城2015年下半年软考补办证书合格人员名单
[考试动态]2016年4月26日邹城人力资源和社会保障局邹城2015年下半年软考证书领取联系电话
[考试动态]2016年4月26日邹城人力资源和社会保障局邹城2015年下半年软考证书领取办理方式
[考试动态]2016年4月26日邹城人力资源和社会保障局邹城2015年下半年软考合格人员名单
[考试动态]2016年4月26日