1、AVL树简介

AVL树本质上还是一棵二叉搜索树,又称高度平衡的二叉搜索树。它能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度。对于二叉搜索树的介绍和实现,可查看本人上一篇博客。

2、AVL树的特点

1)本身首先是一棵二叉搜索树。

2)带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。

3)树中的每个左子树和右子树都是AVL树。

4)每个结点都有一个平衡因子,任一结点的平衡因子是-1,0,1.

注:结点的平衡因子 = 右子树高度 - 左子树高度

3、AVL树的效率

一棵AVL树有N个结点,其高度可以保持在lgN,插入/删除/查找的时间复杂度也是lgN。

AVL树的复杂程度真是比二叉搜索树高了整整一个数量级——它的原理并不难弄懂,但要把它用代码实现出来还真的有点费脑筋。下面我们来看看AVL树实现的接口,通过三叉链进行结点的实现。

template<classK,classV>structAVLTreeNode//三叉链{AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode<K,V>*_parent;K_key;V_value;int_bf;//右子树与左子树的高度差AVLTreeNode(constK&key=K(),constV&value=V())//加上K()和V(),可缺省构造:_left(NULL),_right(NULL),_parent(NULL),_key(key),_value(value),_bf(0){}};template<classK,classV>classAVLTree{typedefAVLTreeNode<K,V>Node;public:AVLTree():_root(NULL){}voidInsert(constK&key,constV&value);Node*Find(constK&key);intHeight();boolIsBalance();voidPrintAVLTree();private:Node*_Find(Node*root,constK&key);void_RotateL(Node*&parent);void_RotateR(Node*&parent);void_RotateLR(Node*&parent);void_RotateRL(Node*&parent);int_Height(Node*root);bool_IsBalance(Node*root);void_PrintAVLTree(Node*root);protected:Node*_root;};

下面对插入进行元素的分析:

1)判断树是否为空,为空时,新建根结点。

2)查找插入的key是否存在,存在就退出函数,不存在就执行3)。

3)找到插入key的位置,然后插入结点cur。

4)更新平衡因子:从cur开始向上其父结点进行更新平衡因子,如果结点的平衡因子不满足AVL树,进行旋转调节平衡因子。

template<classK,classV>voidAVLTree<K,V>::insert(constK&key,constV&value){if(_root==NULL){_root=newNode(key,value);return;}if(Find(key))//存在key{return;}Node*prev=NULL;Node*cur=_root;while(cur)//插入key的位置cur{if(key<cur->_key){prev=cur;cur=cur->_left;}elseif(key>cur->_key){prev=cur;cur=cur->_right;}}cur=newNode(key,value);//插如结点curif(prev->_key>key){prev->_left=cur;cur->_parent=prev;}elseif(prev->_key<key){prev->_right=cur;cur->_parent=prev;}//prev为cur的上一个结点,即为cur是prev的父亲结点prev=cur;cur=prev->_parent;while(cur){//更新平衡因子:从插如的cur开始向上更新平衡因子cur->_bf=_Height(cur->_right)-_Height(cur->_left);if(cur->_bf!=-1&&cur->_bf!=1&&cur->_bf!=0)//不满足AVL树的结点,进行旋转调节平衡因子{//平衡因子为2时,一定存在右子树;平衡因子为-2时,一定存在左子树//左单旋:21(平衡因子)if(cur->_bf==2&&cur->_right->_bf==1){_RotateL(cur);//引用传递}//右单旋:-2-1elseif(cur->_bf==-2&&cur->_left->_bf==-1){_RotateR(cur);}//左右旋转:-21elseif(cur->_bf==-2&&cur->_left->_bf==1){_RotateLR(cur);}//右左旋转:2-1elseif(cur->_bf==2&&cur->_right->_bf==-1){_RotateRL(cur);}}prev=cur;cur=cur->_parent;}}

进行旋转调节平衡因子,分四种情况:

(1)左单旋:cur的平衡因子为2,cur->_right的平衡因子为1。

(2)右单旋:cur的平衡因子为-2,cur->_left的平衡因子为-1。

(3)左右旋转:cur的平衡因子为-2,cur->_left的平衡因子为1。

(4)右左旋转:cur的平衡因子为-2,cur->_right的平衡因子为-1。

左右旋转和右左旋转可通过调用左单旋和右单旋进行,注意结束后重置平衡因子。

如果不是很清楚,可以自己画图进行分析。

左单旋:

template<classK,classV>voidAVLTree<K,V>::_RotateL(Node*&parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;//1subR->_parent=parent->_parent;//1subR->_left=parent;//2parent->_parent=subR;//2if(subRL)//注意不为空,进行链接subRL->_parent=parent;parent->_bf=subR->_bf=0;//进行subR的父亲结点和subR的链接if(subR->_parent==NULL)//为空时,parent为根结点,更改根结点_root=subR;else//不为空,进行链接{if(subR->_parent->_key>subR->_key)subR->_parent->_left=subR;elsesubR->_parent->_right=subR;}parent=subR;}

右单旋:

template<classK,classV>voidAVLTree<K,V>::_RotateR(Node*&parent){Node*subL=parent->_left;Node*subLR=subL->_right;//不能变换顺序parent->_left=subL->_right;//1subL->_parent=parent->_parent;//1subL->_right=parent;//2parent->_parent=subL;//2if(subLR)//注意不为空,进行链接subLR->_parent=parent;parent->_bf=subL->_bf=0;//进行subL的父亲结点和subL的链接if(subL->_parent==NULL)//为空时,parent为根结点,更改根结点_root=subL;else//不为空,进行链接{if(subL->_parent->_key>subL->_key)subL->_parent->_left=subL;elsesubL->_parent->_right=subL;}parent=subL;}

左右旋转:

template<classK,classV>voidAVLTree<K,V>::_RotateLR(Node*&parent){Node*pNode=parent;//需重新定义parent,在进行左右旋转后,parent指向发生了变化Node*subLNode=pNode->_left;Node*subLRNode=subLNode->_right;_RotateL(parent->_left);_RotateR(parent);//在单旋时,parent和subL的平衡因子都为0,在进行左右旋转和右左旋转会出错,故重新设置平衡因子//subLRNode的平衡因子存在三种情况:为0,为-1,为1。subLRNode的平衡因子影响parent和subL的平衡因子if(subLRNode->_bf==1){pNode->_bf=1;subLNode->_bf=0;}elseif(subLRNode->_bf==-1){pNode->_bf=0;subLNode->_bf=-1;}else{parent->_bf=0;subLNode->_bf=0;}}

右左旋转:

template<classK,classV>voidAVLTree<K,V>::_RotateRL(Node*&parent){Node*pNode=parent;Node*subRNode=pNode->_right;Node*subRLNode=subRNode->_left;_RotateR(parent->_right);_RotateL(parent);if(subRLNode->_bf==1){pNode->_bf=-1;subRNode->_bf=0;}elseif(subRLNode->_bf==-1){pNode->_bf=0;subRNode->_bf=1;}else{pNode->_bf=0;subRNode->_bf=0;}}

测试用例如下:

voidAVLTreeTest(){AVLTree<int,int>avlt;//intarr[10]={16,3,7,11,9,26,18,14,15,23};intarr[10]={4,2,6,1,3,5,15,7,16,14};for(inti=0;i<10;++i){avlt.insert(arr[i],i);avlt.PrintAVLTree();}cout<<avlt.IsBalance()<<endl;}

看完上述内容,你们对数据结构中的AVL树是什么意思有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注本站行业资讯频道,感谢大家的支持。