大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
AVL树是高度平衡的二叉搜索树,较搜索树而言降低了树的高度;时间复杂度减少了使其搜索起来更方便;
创新互联成立与2013年,公司以成都网站设计、成都网站制作、外贸网站建设、系统开发、网络推广、文化传媒、企业宣传、平面广告设计等为主要业务,适用行业近百种。服务企业客户上千多家,涉及国内多个省份客户。拥有多年网站建设开发经验。为企业提供专业的网站建设、创意设计、宣传推广等服务。 通过专业的设计、独特的风格,为不同客户提供各种风格的特色服务。1.性质:
(1)左子树和右子树高度之差绝对值不超过1;
(2)树中每个左子树和右子树都必须为AVL树;
(3)每一个节点都有一个平衡因子(-1,0,1:右子树-左子树)
(4)遍历一个二叉搜索树可以得到一个递增的有序序列
2.结构:
平衡二叉树是对二叉搜索树(又称为二叉排序树)的一种改进。二叉搜索树有一个缺点就是,树的结构是无法预料的。任意性非常大。它仅仅与节点的值和插入的顺序有关系。往往得到的是一个不平衡的二叉树。在最坏的情况下。可能得到的是一个单支二叉树,其高度和节点数同样,相当于一个单链表。对其正常的时间复杂度有O(lb n)变成了O(n)。从而丧失了二叉排序树的一些应该有的长处。
当插入一个新的节点的时候。在普通的二叉树中不用考虑树的平衡因子,仅仅要将大于根节点的值插入到右子树,小于节点的值插入到左子树,递归就可以。
而在平衡二叉树则不一样,在插入节点的时候,假设插入节点之后有一个节点的平衡因子要大于2或者小于-2的时候,他须要对其进行调整。如今仅仅考虑插入到节点的左子树部分(右子树与此同样)。主要分为下面三种情况:
(1)若插入前一部分节点的左子树高度和右子树高度相等。即平衡因子为0。插入后平衡因子变为1。仍符合平衡的条件不用调整。
(2)若插入前左子树高度小于右子树高度。即平衡因子为-1,则插入后将使平衡因子变为0,平衡性反倒得到调整,所以不必调整。
(3)若插入前左子树的高度大于右子树高度。即平衡因子为1。则插入左子树之后会使得平衡因子变为2,这种情况下就破坏了平衡二叉树的结构。所以必须对其进行调整,使其加以改善。
调整二叉树首先要明确一个定义。即最小不平衡子树。最小不平衡子树是指以离插入节点近期、且平衡因子绝对值大于1的节点做根的子树。
在构建AVL树的时候使用三叉链:parent,left,right方便回溯,也可以用递归或者栈解决;
在插入一个新节点后,一个平衡二叉树可能失衡,失衡情况下相应的调整方法
(1)右旋
(2)左旋
(3)右左双旋
(4)左右双旋
#includeusing namespace std; template struct AVLTreeNode { AVLTreeNode *_left; AVLTreeNode *_right; AVLTreeNode *_parent; K _key; V _value; int _bf;//平衡因子 AVLTreeNode( const K & key,const V& value ):_bf(0) ,_left(NULL) ,_right( NULL) ,_parent( NULL) ,_key( key) ,_value( value) {} }; template class AVLTree { typedef AVLTreeNode Node; protected: Node* _root; public: AVLTree():_root( NULL) {} bool Insert(const K& key,const V& value) { if(_root==NULL ) { _root= new Node (key,value); return true ; } Node* cur=_root; Node* parent=NULL ; while(cur) { if(cur->_key>key ) { parent=cur; cur=cur->_left; } else if (cur->_key _right; } else { return false ; } } //插入 cur= new Node (key,value); if(parent->_key _right=cur; cur->_parent=parent; } else { parent->_left=cur; cur->_parent=parent; } //检查是否平衡 //1更新平衡因子,不满足条件时进行旋转 while(parent) { if(cur==parent->_left) parent->_bf --; else parent->_bf ++; if(parent->_bf ==0) { break; } // -1 1 else if (parent->_bf ==-1||parent->_bf ==1) { cur=parent; parent=cur->_parent; } else { //旋转处理2 -2 if(cur->_bf ==1) { if(parent->_bf==2) RotateL(parent); else//-2 RotateLR(parent); } else { if(parent->_bf ==-2) RotateR(parent); else//2 RotateRL(parent); } break; } } return true ; } //左单旋 void RotateL(Node * parent) { Node* subR=parent ->_right; Node* subRL=subR->_left; if(subRL) subRL->_parent = parent; subR->_left= parent; Node* ppNode=parent ->_parent; parent->_parent=subR; if(ppNode==NULL ) { _root=subR; } else { if(ppNode->_left=parent ) { ppNode->_left=subR; } else { ppNode->_right=subR; } } parent->_bf=subR->_bf=0; } //右单旋 void RotateR(Node * parent) { Node* subL=parent ->_left; Node* subLR=subL->_right; if(subLR) subLR->_parent = parent; subL->_right = parent; Node* ppNode=parent ->_parent; if(ppNode==NULL ) { _root=subL; } else { if(ppNode->_left==parent ) ppNode->_left=subL; else ppNode->_right=subL; } parent->_bf =subL->_bf =0; } //左右双旋 void RotateLR(Node * parent) { Node* subL=parent ->_left; Node* subLR=subL->_right ; int bf=subLR->_bf ; RotateL( parent->_left); RotateR( parent); //根据subLR的平衡因子修正其他节点的平衡因子 if(bf==-1) { subL->_bf =0; parent->_bf =1; } else if (bf==1) { subL->_bf =-1; parent->_bf=0; } } //右左双旋 void RotateRL(Node * parent) { Node* subR=parent ->_right ; Node* subRL=subR->_left ; int bf=subRL->_bf ; RotateR( parent->_right); RotateL( parent); if(bf==1) { subR->_bf =0; parent->_bf =-1; } else if (bf==-1) { subR->_bf = 1; parent->_bf = 0; } } //中序遍历 void Inorder() { _Inorder(_root); cout< _left); cout<< root->_key <<" " ; _Inorder( root->_right ); } //判断是否平衡 bool IsBalence() { return _IsBalence(_root); } bool _IsBalence(Node * root) { if(root ==NULL) return true ; int left=_Height(root ->_left ); int right= _Height(root ->_right ); if(right-left!=root ->_bf || abs(right-left)>1) { cout<< "节点的平衡因子异常" < _key ; return false ; } return _IsBalence(root ->_left)&&_IsBalence(root->_left); } //求子树的高度 int _Height(Node * root) { if(root ==NULL) return 0; int left=_Height(root ->_left ); int right= _Height(root ->_right ); return left>right?left+1:right+1; } //前边方法的优化 //后续遍历先求子书的高度的同时就可以 //判断出子树是否平衡,然后依次求根节点的高度 bool _Isbalence(Node * root, int& height ) { if(root ==NULL) { height=0; return true ; } if(root ->_left ==NULL&& root->_right ==NULL ) { height=1; returnn true; } int leftheight=0; if(_Isbalence(root ->_left ,leftheight)==false) return false ; int rightheight=0; if(_Isbalence(root ->_right ,rightheight)==false) return false ; height=leftheight>rightheight?leftheight:rightheight; } }; void TestTree() { int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15}; AVLTree t; for (size_t i = 0; i < sizeof(a)/ sizeof(a[0]); ++i) { t.Insert(a[i], i); } t.Inorder(); cout<< "是否平衡?" < 另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
新闻标题:数据结构--AVL树-创新互联
网站链接:http://dzwzjz.com/article/gcjio.html