数据结构-平衡二叉树之一AVL树详解
1.平衡二叉树的概念
在某些极端的情况下(如在插入的序列是有序的时),二叉搜索树将退化成近似链或链,此时,其操作的时间复杂度将退化成线性的,即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况,但是在进行了多次的操作之后,由于在删除时,我们总是选择将待删除节点的后继代替它本身,这样就会造成总是右边的节点数目减少,以至于树向左偏沉。这同时也会造成树的平衡性受到破坏,提高它的操作的时间复杂度。于是就有了我们下边介绍的平衡二叉树。
平衡二叉树定义:平衡二叉树(Balanced Binary Tree)具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用算法有红黑树、AVL树等。在平衡二叉搜索树中,我们可以看到,其高度一般都良好地维持在O(log2n),大大降低了操作的时间复杂度。
2.平衡二叉树之AVL树
AVL树是最先发明的自平衡二叉查找树,在AVL中任何节点的两个儿子子树的高度最大差别为1,所以它也被称为高度平衡树,n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O(logn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。
AVL树的自平衡操作——旋转:
AVL树最关键的也是最难的一步操作就是旋转。旋转主要是为了实现AVL树在实施了插入和删除操作以后,树重新回到平衡的方法。下面我们重点研究一下AVL树的旋转。
对于一个平衡的节点,由于任意节点最多有两个儿子,因此高度不平衡时,此节点的两颗子树的高度差2.容易看出,这种不平衡出现在下面四种情况:
1) 6节点的左子树3节点高度比右子树7节点大2,左子树3节点的左子树1节点高度大于右子树4节点,这种情况成为左左。
2) 6节点的左子树2节点高度比右子树7节点大2,左子树2节点的左子树1节点高度小于右子树4节点,这种情况成为左右。
3) 2节点的左子树1节点高度比右子树5节点小2,右子树5节点的左子树3节点高度大于右子树6节点,这种情况成为右左。
4) 2节点的左子树1节点高度比右子树4节点小2,右子树4节点的左子树3节点高度小于右子树6节点,这种情况成为右右。
从图2中可以可以看出,1和4两种情况是对称的,这两种情况的旋转算法是一致的,只需要经过一次旋转就可以达到目标,我们称之为单旋转。2和3两种情况也是对称的,这两种情况的旋转算法也是一致的,需要进行两次旋转,我们称之为双旋转。
》左单旋:
AVL树实现源码:
//AVL树节点信息 template<class T> class TreeNode { public: TreeNode():lson(NULL),rson(NULL),freq(1),hgt(0){} T data;//值 int hgt;//高度 unsigned int freq;//频率 TreeNode* lson;//指向左儿子的地址 TreeNode* rson;//指向右儿子的地址 }; //AVL树类的属性和方法声明 template<class T> class AVLTree { private: TreeNode<T>* root;//根节点 void insertpri(TreeNode<T>* &node,T x);//插入 TreeNode<T>* findpri(TreeNode<T>* node,T x);//查找 void insubtree(TreeNode<T>* node);//中序遍历 void Deletepri(TreeNode<T>* &node,T x);//删除 int height(TreeNode<T>* node);//求树的高度 void SingRotateLeft(TreeNode<T>* &k2);//左左情况下的旋转 void SingRotateRight(TreeNode<T>* &k2);//右右情况下的旋转 void DoubleRotateLR(TreeNode<T>* &k3);//左右情况下的旋转 void DoubleRotateRL(TreeNode<T>* &k3);//右左情况下的旋转 int Max(int cmpa,int cmpb);//求最大值 public: AVLTree():root(NULL){} void insert(T x);//插入接口 TreeNode<T>* find(T x);//查找接口 void Delete(T x);//删除接口 void traversal();//遍历接口 }; //计算节点的高度 template<class T> int AVLTree<T>::height(TreeNode<T>* node) { if(node!=NULL) return node->hgt; return -1; } //求最大值 template<class T> int AVLTree<T>::Max(int cmpa,int cmpb) { return cmpa>cmpb?cmpa:cmpb; } //左左情况下的旋转 template<class T> void AVLTree<T>::SingRotateLeft(TreeNode<T>* &k2) { TreeNode<T>* k1; k1=k2->lson; k2->lson=k1->rson; k1->rson=k2; k2->hgt=Max(height(k2->lson),height(k2->rson))+1; k1->hgt=Max(height(k1->lson),k2->hgt)+1; } //右右情况下的旋转 template<class T> void AVLTree<T>::SingRotateRight(TreeNode<T>* &k2) { TreeNode<T>* k1; k1=k2->rson; k2->rson=k1->lson; k1->lson=k2; k2->hgt=Max(height(k2->lson),height(k2->rson))+1; k1->hgt=Max(height(k1->rson),k2->hgt)+1; } //左右情况的旋转 template<class T> void AVLTree<T>::DoubleRotateLR(TreeNode<T>* &k3) { SingRotateRight(k3->lson); SingRotateLeft(k3); } //右左情况的旋转 template<class T> void AVLTree<T>::DoubleRotateRL(TreeNode<T>* &k3) { SingRotateLeft(k3->rson); SingRotateRight(k3); } //插入 template<class T> void AVLTree<T>::insertpri(TreeNode<T>* &node,T x) { if(node==NULL)//如果节点为空,就在此节点处加入x信息 { node=new TreeNode<T>(); node->data=x; return; } if(node->data>x)//如果x小于节点的值,就继续在节点的左子树中插入x { insertpri(node->lson,x); if(2==height(node->lson)-height(node->rson)) if(x<node->lson->data) SingRotateLeft(node); else DoubleRotateLR(node); } else if(node->data<x)//如果x大于节点的值,就继续在节点的右子树中插入x { insertpri(node->rson,x); if(2==height(node->rson)-height(node->lson))//如果高度之差为2的话就失去了平衡,需要旋转 if(x>node->rson->data) SingRotateRight(node); else DoubleRotateRL(node); } else ++(node->freq);//如果相等,就把频率加1 node->hgt=Max(height(node->lson),height(node->rson)); } //插入接口 template<class T> void AVLTree<T>::insert(T x) { insertpri(root,x); } //查找 template<class T> TreeNode<T>* AVLTree<T>::findpri(TreeNode<T>* node,T x) { if(node==NULL)//如果节点为空说明没找到,返回NULL { return NULL; } if(node->data>x)//如果x小于节点的值,就继续在节点的左子树中查找x { return findpri(node->lson,x); } else if(node->data<x)//如果x大于节点的值,就继续在节点的左子树中查找x { return findpri(node->rson,x); } else return node;//如果相等,就找到了此节点 } //查找接口 template<class T> TreeNode<T>* AVLTree<T>::find(T x) { return findpri(root,x); } //删除 template<class T> void AVLTree<T>::Deletepri(TreeNode<T>* &node,T x) { if(node==NULL) return ;//没有找到值是x的节点 if(x < node->data) { Deletepri(node->lson,x);//如果x小于节点的值,就继续在节点的左子树中删除x if(2==height(node->rson)-height(node->lson)) if(node->rson->lson!=NULL&&(height(node->rson->lson)>height(node->rson->rson)) ) DoubleRotateRL(node); else SingRotateRight(node); } else if(x > node->data) { Deletepri(node->rson,x);//如果x大于节点的值,就继续在节点的右子树中删除x if(2==height(node->lson)-height(node->rson)) if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) )) DoubleRotateLR(node); else SingRotateLeft(node); } else//如果相等,此节点就是要删除的节点 { if(node->lson&&node->rson)//此节点有两个儿子 { TreeNode<T>* temp=node->rson;//temp指向节点的右儿子 while(temp->lson!=NULL) temp=temp->lson;//找到右子树中值最小的节点 //把右子树中最小节点的值赋值给本节点 node->data=temp->data; node->freq=temp->freq; Deletepri(node->rson,temp->data);//删除右子树中最小值的节点 if(2==height(node->lson)-height(node->rson)) { if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) )) DoubleRotateLR(node); else SingRotateLeft(node); } } else//此节点有1个或0个儿子 { TreeNode<T>* temp=node; if(node->lson==NULL)//有右儿子或者没有儿子 node=node->rson; else if(node->rson==NULL)//有左儿子 node=node->lson; delete(temp); temp=NULL; } } if(node==NULL) return; node->hgt=Max(height(node->lson),height(node->rson))+1; return; } //删除接口 template<class T> void AVLTree<T>::Delete(T x) { Deletepri(root,x); } //中序遍历函数 template<class T> void AVLTree<T>::insubtree(TreeNode<T>* node) { if(node==NULL) return; insubtree(node->lson);//先遍历左子树 cout<<node->data<<" ";//输出根节点 insubtree(node->rson);//再遍历右子树 } //中序遍历接口 template<class T> void AVLTree<T>::traversal() { insubtree(root); }