作者：一觉亮天 日期：2007-7-21

AVL树的定义 

说AVL树要先说二叉搜索树。二叉搜索树(Binary
Search Tree)是这样的二叉树：二叉树的左子树如果不为空，则所有节点的值都小于父节点；二叉树的右子树如果不为空，则所有节点的值都大于父节点。

二叉搜索树中查找操作的平均时间复杂度是O(logn)，以这种方式组织数据可以节约查找时间。但二叉搜索树如果构造不恰当的话，最坏情况下，查找操作的时间复杂度可能会是O(n)。比如下面图1这种情况：

图1

图1所示的树被认为是不平衡的，为此引入了平衡二叉搜索树(Balanced Binary Search Tree)的概念。平衡二叉搜索树就是给二叉搜索树增加一些平衡条件，使她不是太瘦高。AVL树就是平衡二叉树的一种。AVL是两个人名字的首字母缩写。在说AVL树平衡条件之前需要引入树的高度的概念。由图2就可以理解对树的高度的定义了。规定空树的高度是-1。

图2

AVL树规定树二叉搜索树的左子树的高度和右子树的高度之差的绝对值不能大于1。

AVL树的插入和删除操作

AVL树的插入操作和删除操作的第一步和普通二叉搜索树的插入和删除操作相同。

插入操作就是依照二叉搜索树的定义把插入的元素放在合适的位置。

删除操作可以以下面的算法完成：

找到要删除的节点，如果是叶子节点则直接删除；如果只包含左子树或右子树，则删除此节点，相应的左子树或右子树位置上移；如果既包含左子树又包含右子树，则可以找到此节点右子树中最小的节点，把值赋给待删除节点，然后在此节点的右子树删除最小的节点。

进行完普通二叉搜索树的插入操作和删除操作后，有可能破坏AVL树的平衡条件，这时就可以通过树的旋转操作来使她重新平衡。

树的旋转操作

往AVL树中插入元素，如果导致了树的不平衡，能通过下面的任意一种旋转操作使树重新平衡。

RR

图3

如图3所示，节点5的左子树高度是1，右子树高度是-1，需要对树进行右旋操作。右旋操作的步骤是：节点5的左子树指向节点4的右子树，结点4的右子树指向节点5。

RL

图4

如图4所示，节点4的左子树高度是1，右子树高度是-1，需要对树进行右旋操作。但是如果单纯做右旋操作的话，并不能使树平衡。这时需要两次旋转，先对4节点的左子树进行左旋操作，然后再对节点4进行右旋操作。

判断进行RL操作还是进行RR操作是看要进行右旋操作的树的左子树是右重还是左重。右重即树的右子树高度大于左子树。如果要进行右旋操作的树的左子树是右重，则进行RL操作，否则进行RR操作。

LL

图5

如图5所示，LL操作和RR操作对称。

LR

图6

如图6所示LR操作和RL操作对称。

AVL树的实现

// AVLTree.h: interface for the AVLTree class.<br /> //<br /> //////////////////////////////////////////////////////////////////////</p> <p>#if !defined(AFX_AVLTREE_H__D78D2C76_87EF_4B00_9AF7_C2FF4076B620__INCLUDED_)<br /> #define AFX_AVLTREE_H__D78D2C76_87EF_4B00_9AF7_C2FF4076B620__INCLUDED_</p> <p>#if _MSC_VER > 1000<br /> #pragma once<br /> #endif // _MSC_VER > 1000</p> <p>class AVLTree;<br /> typedef AVLTree* AVLTreePtr;</p> <p>class AVLTree<br /> {<br /> public:<br /> AVLTree();<br /> virtual ~AVLTree();<br /> static AVLTreePtr Delete(AVLTreePtr tree,int data);<br /> static void Dump(AVLTreePtr tree);<br /> static void Test();<br /> static AVLTreePtr Insert(AVLTreePtr tree,int data);<br /> public:<br /> AVLTreePtr m_left,m_right;<br /> int m_data;<br /> int m_height;<br /> private:<br /> static AVLTreePtr FindMin(AVLTreePtr tree);<br /> static AVLTreePtr DeleteData(AVLTreePtr tree, int data);<br /> static int Height(AVLTreePtr tree);<br /> static AVLTreePtr InsertData(AVLTreePtr tree,AVLTreePtr parent,int data);<br /> static AVLTreePtr RightLeft(AVLTreePtr tree);<br /> static AVLTreePtr LeftRight(AVLTreePtr tree);<br /> static AVLTreePtr LeftLeft(AVLTreePtr tree);<br /> static AVLTreePtr RightRight(AVLTreePtr tree);<br /> static void Output(AVLTreePtr tree);<br /> };</p> <p>#endif // !defined(AFX_AVLTREE_H__D78D2C76_87EF_4B00_9AF7_C2FF4076B620__INCLUDED_)<br />

// AVLTree.cpp: implementation of the AVLTree class.<br /> //<br /> //////////////////////////////////////////////////////////////////////</p> <p>#include "stdafx.h"<br /> #include "AVLTree.h"<br /> #include <assert.h><br /> //#include <stdio.h><br /> //#include <math.h><br /> //#include <stdlib.h><br /> #define max(a,b) (a)<(b)?(b):(a)</p> <p>//////////////////////////////////////////////////////////////////////<br /> // Construction/Destruction<br /> //////////////////////////////////////////////////////////////////////</p> <p>AVLTree::AVLTree()<br /> {<br /> m_left=m_right=NULL;<br /> m_height=0;<br /> }</p> <p>AVLTree::~AVLTree()<br /> {</p> <p>}</p> <p>AVLTreePtr AVLTree::Insert(AVLTreePtr tree,int data)<br /> {<br /> bool inserted=false;<br /> tree=InsertData(tree,NULL,data);<br /> return tree;<br /> }</p> <p>AVLTreePtr AVLTree::InsertData(AVLTreePtr tree, AVLTreePtr parent,int data)<br /> {<br /> AVLTreePtr nodePtr,rotateTree;<br /> int lHeight,rHeight,lSubHeight,rSubHeight;<br /> if(NULL==tree)<br /> {<br /> nodePtr=new AVLTree;<br /> nodePtr->m_data=data;<br /> nodePtr->m_height=0;<br /> return nodePtr;<br /> }</p> <p> rotateTree=tree;</p> <p> if(data<tree->m_data)<br /> {<br /> tree->m_left=InsertData(tree->m_left,tree,data);<br /> lHeight=Height(tree->m_left);<br /> rHeight=Height(tree->m_right);<br /> if(rHeight-lHeight==-2)<br /> {<br /> lSubHeight=Height(tree->m_left->m_left);<br /> rSubHeight=Height(tree->m_left->m_right);<br /> if(lSubHeight>rSubHeight)<br /> {<br /> rotateTree=RightRight(tree);<br /> }<br /> else<br /> {<br /> rotateTree=RightLeft(tree);<br /> }<br /> }</p> <p> }<br /> else if(data>tree->m_data)<br /> {<br /> tree->m_right=InsertData(tree->m_right,tree,data);<br /> lHeight=Height(tree->m_left);<br /> rHeight=Height(tree->m_right);<br /> if(rHeight-lHeight==2)<br /> {<br /> lSubHeight=Height(tree->m_right->m_left);<br /> rSubHeight=Height(tree->m_right->m_right);<br /> if(lSubHeight<rSubHeight)<br /> {<br /> rotateTree=LeftLeft(tree);<br /> }<br /> else<br /> {<br /> rotateTree=LeftRight(tree);<br /> }<br /> }<br /> }<br /> else<br /> {<br /> assert(false);<br /> }</p> <p> lHeight=Height(rotateTree->m_left);<br /> rHeight=Height(rotateTree->m_right);<br /> rotateTree->m_height=1+max(lHeight,rHeight);</p> <p> if(parent!=NULL)<br /> {<br /> if(parent->m_left==tree)<br /> {<br /> parent->m_left=rotateTree;<br /> }<br /> else<br /> {<br /> parent->m_right=rotateTree;<br /> }<br /> } </p> <p> return rotateTree;<br /> }</p> <p>AVLTreePtr AVLTree::Delete(AVLTreePtr tree, int data)<br /> {<br /> return DeleteData(tree,data);<br /> }</p> <p>AVLTreePtr AVLTree::DeleteData(AVLTreePtr tree, int data)<br /> {<br /> AVLTreePtr nodePtr;<br /> int lHeight,rHeight,lSubHeight,rSubHeight;</p> <p> if(NULL==tree) return NULL;<br /> if(data<tree->m_data)<br /> {<br /> tree->m_left = DeleteData(tree->m_left,data);<br /> }<br /> else if(data>tree->m_data)<br /> {<br /> tree->m_right = DeleteData(tree->m_right,data);<br /> }<br /> else<br /> {<br /> if(tree->m_left && tree->m_right)<br /> {<br /> nodePtr=FindMin(tree->m_right);<br /> tree->m_data=nodePtr->m_data;<br /> tree->m_right=DeleteData(tree->m_right,nodePtr->m_data);<br /> }<br /> else if(tree->m_left)<br /> {<br /> nodePtr=tree;<br /> tree=tree->m_left;<br /> delete nodePtr;<br /> }<br /> else if(tree->m_right)<br /> {<br /> nodePtr=tree;<br /> tree=tree->m_right;<br /> delete nodePtr;<br /> }<br /> else<br /> {<br /> delete tree;<br /> tree=NULL;<br /> }<br /> }</p> <p> if(NULL==tree) return NULL;</p> <p> lHeight=Height(tree->m_left);<br /> rHeight=Height(tree->m_right);</p> <p> if(rHeight-lHeight==-2)<br /> {<br /> lSubHeight=Height(tree->m_left->m_left);<br /> rSubHeight=Height(tree->m_left->m_right);<br /> if(lSubHeight>rSubHeight)<br /> {<br /> tree=RightRight(tree);<br /> }<br /> else<br /> {<br /> tree=RightLeft(tree);<br /> }<br /> }<br /> else if(rHeight-lHeight==2)<br /> {<br /> lSubHeight=Height(tree->m_right->m_left);<br /> rSubHeight=Height(tree->m_right->m_right);<br /> if(lSubHeight<rSubHeight)<br /> {<br /> tree=LeftLeft(tree);<br /> }<br /> else<br /> {<br /> tree=LeftRight(tree);<br /> }<br /> }</p> <p> lHeight=Height(tree->m_left);<br /> rHeight=Height(tree->m_right);<br /> tree->m_height=1+max(lHeight,rHeight);</p> <p> return tree;<br /> }</p> <p>AVLTreePtr AVLTree::FindMin(AVLTreePtr tree)<br /> {<br /> if(NULL==tree) return NULL;<br /> if(tree->m_left) return FindMin(tree->m_left);<br /> return tree;<br /> }</p> <p>int AVLTree::Height(AVLTreePtr tree)<br /> {<br /> if(NULL==tree) return -1;<br /> int lHeight=Height(tree->m_left);<br /> int rHeight=Height(tree->m_right);<br /> int h=lHeight>rHeight?lHeight:rHeight;<br /> return h+1;<br /> }</p> <p>AVLTreePtr AVLTree::RightRight(AVLTreePtr tree)<br /> {<br /> AVLTreePtr subNode=tree->m_left;<br /> tree->m_left=subNode->m_right;<br /> subNode->m_right=tree;</p> <p> int lHeight,rHeight;<br /> lHeight=Height(subNode->m_left);<br /> rHeight=Height(subNode->m_right);<br /> subNode->m_height=1+max(lHeight,rHeight);</p> <p> lHeight=Height(tree->m_left);<br /> rHeight=Height(tree->m_right);<br /> tree->m_height=1+max(lHeight,rHeight); </p> <p> return subNode;<br /> }</p> <p>AVLTreePtr AVLTree::LeftLeft(AVLTreePtr tree)<br /> {<br /> AVLTreePtr subNode=tree->m_right;<br /> tree->m_right=subNode->m_left;<br /> subNode->m_left=tree;</p> <p> int lHeight,rHeight;<br /> lHeight=Height(subNode->m_left);<br /> rHeight=Height(subNode->m_right);<br /> subNode->m_height=1+max(lHeight,rHeight);</p> <p> lHeight=Height(tree->m_left);<br /> rHeight=Height(tree->m_right);<br /> tree->m_height=1+max(lHeight,rHeight); </p> <p> return subNode;<br /> }</p> <p>AVLTreePtr AVLTree::RightLeft(AVLTreePtr tree)<br /> {<br /> AVLTreePtr subNode=tree->m_left;<br /> tree->m_left = LeftLeft(subNode);<br /> return RightRight(tree);<br /> }</p> <p>AVLTreePtr AVLTree::LeftRight(AVLTreePtr tree)<br /> {<br /> AVLTreePtr subNode=tree->m_right;<br /> tree->m_right=RightRight(subNode);<br /> return LeftLeft(tree);<br /> }</p> <p>void AVLTree::Output(AVLTreePtr tree)<br /> {<br /> if(NULL==tree) return;</p> <p> printf("(");<br /> if(tree->m_left)<br /> {<br /> Output(tree->m_left);<br /> }<br /> else<br /> {<br /> printf("*,");<br /> }</p> <p> printf("%d,",tree->m_data); </p> <p> if(tree->m_right)<br /> {<br /> Output(tree->m_right);<br /> }<br /> else<br /> {<br /> printf("*");<br /> }<br /> printf(")"); </p> <p>}</p> <p>void AVLTree::Dump(AVLTreePtr tree)<br /> {<br /> Output(tree);<br /> printf("/n");<br /> }</p> <p>void AVLTree::Test()<br /> {<br /> AVLTreePtr tree=NULL;<br /> tree=Insert(tree,9);<br /> Dump(tree);<br /> tree=Insert(tree,7);<br /> Dump(tree);<br /> tree=Insert(tree,10);<br /> Dump(tree);<br /> tree=Insert(tree,8);<br /> Dump(tree);</p> <p> tree=Delete(tree,10);<br /> Dump(tree);<br /> }</p> <p>