数据结构之——AVL树-创新互联
- 创新互联建站服务紧随时代发展步伐,进行技术革新和技术进步,经过10年的发展和积累,已经汇集了一批资深网站策划师、设计师、专业的网站实施团队以及高素质售后服务人员,并且完全形成了一套成熟的业务流程,能够完全依照客户要求对网站进行网站设计、成都做网站、建设、维护、更新和改版,实现客户网站对外宣传展示的首要目的,并为客户企业品牌互联网化提供全面的解决方案。
AVL树又称为高度平衡的二叉搜索树,它能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度;
AVL树的性质
高度之差的绝对值不超过1
#pragma once templatestruct AVLTreeNode { K _key; V _val; AVLTreeNode * _left; AVLTreeNode * _right; AVLTreeNode * _parent; int _bf;//平衡因子 AVLTreeNode(const K& key, const K& val) :_key(key) ,_val(val) ,_left(NULL) ,_right(NULL) ,_parent(NULL) ,_bf(0) {} }; template class AVLTree { typedef AVLTreeNode Node; public: AVLTree() :_root(NULL) {} ~AVLTree() { _Clear(_root); } bool Insert(const K& key, const V& val) { if(_root == NULL)//如果根结点为NULL,则创建一个结点,返回真 { _root = new Node(key, val); return true; } Node* cur = _root; Node* prev = NULL; while(cur != NULL)//查找合适的位置插入 { if(cur->_key == key)//如果结点已存在,则返回假 return false; else if(cur->_key > key)//如果要插入值小于当前结点,则去左子树查找 { prev = cur; cur = cur->_left; } else//如果插入值大于当前结点,则去右子树查找 { prev = cur; cur = cur->_right; } } //循环结束,则表明找到了合适的位置,判断应插入左边还是右边 Node* tmp = new Node(key, val); if(key < prev->_key) prev->_left = tmp; else prev->_right = tmp; tmp->_parent = prev; //插入结点之后,需要判断当前树是否满足AVL树的规则,若不满足,进行相应的调整 while(prev != NULL) { //平衡因子为右边高度减去左边高度 if(prev->_left == tmp) --(prev->_bf); else ++(prev->_bf); if(prev->_bf == 0)//如果平衡因子为0,则一定平衡,因为可以看做是在同一层插入了一个结点,对高度并无影响 break; else if(prev->_bf == 1 || prev->_bf == -1)//如果平衡因子为1/-1,则表明高度有所变化,需要继续向上调整 { tmp = prev; prev = prev->_parent; } else//说明平衡因子的绝对值大于1,则这个时候不满足AVL树的性质,需要进行调整 { if(prev->_bf == 2) { if(tmp->_bf == 1) _RotateL(prev); else { _RotateR(tmp); _RotateL(prev); } } else { if(tmp->_bf == -1) _RotateR(prev); else { _RotateL(tmp); _RotateR(prev); } } break; } } return true; } void InOrder() { _InOrder(_root); cout< _left); _Clear(root->_right); delete root; root = NULL; } } //左单旋 void _RotateL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if(subRL != NULL) 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; } subR->_parent = ppNode; parent->_bf = subR->_bf = 0; } //右单旋 void _RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if(subLR != NULL) subLR->_parent = parent; subL->_right = parent; Node* ppNode = parent->_parent; parent->_parent = subL; if(ppNode == NULL) _root = subL; else { if(ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; } subL->_parent = ppNode; parent->_bf = subL->_bf = 0; } void _InOrder(Node* root) { if(root != NULL) { _InOrder(root->_left); cout< _key<<" "; _InOrder(root->_right); } } protected: Node* _root; }; void Test() { int arr[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14}; //int arr[] = {16, 3, 7, 11, 9, 26, 18, 14, 15}; AVLTree t; for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i) t.Insert(arr[i], i); t.InOrder(); }
其中的左右单旋如下图所示:
《完》
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网页标题:数据结构之——AVL树-创新互联
当前网址:http://myzitong.com/article/iphgj.html