数据结构--平衡二叉树AVL-创新互联
一、平衡二叉树( AVL树 )
网站建设哪家好,找创新互联!专注于网页设计、网站建设、微信开发、成都小程序开发、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了汉南免费建站欢迎大家使用!1、定义:AVL树又称为高度平衡的二叉搜索树,是1962年有俄罗斯的数学家G.M.Adel'son-Vel'skii和E.M.Landis提出来的。它能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度。
2、出现原因:搜索二叉树若出现严重退化,查找或使用时会造成资源浪费。
3、特性:
AVL树是一个三叉链;
左、右子树的 | 高度之差| 不超过 1;
左右子树都是AVL树;
每个节点的平衡因子 = 右子树高度 - 左子树高度;(平衡因子:-1,1,0)
4、效率:
一棵AVL树有N个节点,其高度可以保持在log2N,插入/删除/查找的时间复杂度:log2N,即 O(lgN)。
二、AVL相关
1、右单旋
2、左单旋
3、右左单旋及左右单旋
根据左单旋、右单旋及树的情况进行选择,旋转后需要更新平衡因子,以防失误。
4、节点平衡因子的更新:
(1)插入节点的右孩子,及平衡因子bf++;左孩子,bf--;
(2)若插入节点后,计算得bf==0,则平衡,不需更新平衡因子;bf==1或-1,则需向上查看是否需要平衡因子;bf==2或-2,则根据情况进行旋转,并更新平衡因子。
5、判断AVL树:
(1)计算左、右子树高度,平衡因子;
(2)若平衡因子 < 2,即其子树为AVL树;
三、源代码
1、节点
templatestruct AVLTreeNode { AVLTreeNode *_left; AVLTreeNode *_right; AVLTreeNode *_parent; K _key;//权值 V _value; int _bf;//平衡因子 AVLTreeNode(const K& key,const V& value) :_key(key) ,_value(value) ,_left(NULL) ,_right(NULL) ,_parent(NULL) {} };
2、AVL树及相关实现
templateclass AVLTree { typedef AVLTreeNode Node; public: AVLTree() :_root(NULL) {} void InOrder() { _InOrder(_root); cout< _left; Node *subLR=subL->_right; parent->_left=subLR; if(subLR) subLR->_parent=parent; subL->_right=parent; Node *ppNode=parent->_parent; parent->_parent=subL; if(ppNode == NULL) { _root=subL; subL->_parent=NULL; } else { if(ppNode->_left == parent) ppNode->_left=subL; else ppNode->_right=subL; subL->_parent=ppNode; } } void RotateL(Node *parent)//左旋转 { Node *subR=parent->_right; Node *subRL=subR->_left; parent->_right=subR; if(subRL) subRL->_parent=parent; subRL->_left=parent; Node *ppNode=parent->_parent; parent->_parent=subR; if(ppNode == NULL) { _root=subR; subR->_parent=NULL; } else { if(ppNode->_left == parent) ppNode->_left=subR; else ppNode->_right=subR; subR->_parent=ppNode; } } void RotateRL(Node *parent)//右左旋转 { Node *subR=parent->_right; Node *subRL=subR->_left; int bf=subR->_bf; RotateR(parent->_right); RotateL(parent); //更正平衡因子 if(bf == 1) { parent->_bf=-1; subR->_bf=0; } else if(bf == -1) { parent->_bf=0; subR->_bf=1; } else // 0 { subR->_bf=parent->_bf=0; subRL->_bf=0; } } void RotateLR(Node *parent)//左右旋转 { Node *subL=parent->_left; Node *subLR=subL->_right; int bf=subLR->_bf; RotateL(parent->_left); RotateR(parent); //更正平衡因子 if(bf == 1) { parent->_bf=-1; subL->_bf=0; } else if(bf == -1) { parent->_bf=0; subL->_bf=1; } else // 0 { subL->_bf=parent->_bf=0; subLR=0; } } 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 < key) { parent=cur; cur=cur->_right; } else return false; } cur=new Node(key,value); if(parent->_key < key) parent->_right=new Node(key,value); else parent->_left=new Node(key,value); //更新平衡因子 while(parent) { if(cur == parent->_right) parent->_bf++; else parent->_bf--; if(parent->_bf == 0) break; // 树平衡 else if(parent->_bf == 1 || parent->_bf == -1) { cur=parent; parent=cur->_parent; } else // -2或2 { //旋转 if(parent->_bf == -2) { if(cur->_bf == -1) RotateR(parent);//右旋转 else // -2 RotateLR(parent);//左右旋转 } else // 2 { if(cur->_bf == 1) RotateL(parent);//左旋转 else RotateRL(parent);//右左旋转 } break; } } return false; } protected: void _InOrder(Node *root) { if(_root == NULL) return; _InOrder(_root->_left); cout<<_root->_key<<" "; _InOrder(_root->_right); } 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; } protected: Node *_root; };
3、总结:
AVL树是对搜索二叉树的进一步优化,根据平衡因子使搜索二叉树高度平衡。其的插入、删除、查找都和搜索二叉树类似,只是需要注意平衡因子的问题。
AVL树解决了搜索二叉树的退化问题,需要注意树的旋转问题及平衡因子的更新问题。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站题目:数据结构--平衡二叉树AVL-创新互联
网站网址:http://pwwzsj.com/article/dehsdg.html