AVL树又称高度平衡的二叉搜索树,是1962年俄罗斯的数学家提出来的。它能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度。
创新互联长期为上千家客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为瑞安企业提供专业的成都做网站、成都网站建设,瑞安网站改版等技术服务。拥有10多年丰富建站经验和众多成功案例,为您定制开发。AVL的性质:
(1)左子树和右子树的高度之差的绝对值不超过1。
(2)树中的每个左子树和右子树都是AVL树。
(3)每个节点都有一个平衡因子,任一节点的平衡因子是-1,0,1(每个节点的平衡因子等于右子树的高度减去左子树的高度)。
代码实现如下:
#include<iostream> using namespace std; template<class K,class V> struct AVLTreeNode{ AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; K _key; V _value; int _bf; //平衡因子 AVLTreeNode(const K& key,const V& value) :_key(key) , _value(value) , _left(NULL) , _right(NULL) , _parent(NULL) , _bf(0) {} }; template<class K,class V> class AVLTree{ typedef AVLTreeNode<K, V> Node; 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 < key) { parent = cur; cur = cur->_right; } else { return false; } } cur = new Node(key,value); if (parent->_key > key) { parent->_left = cur; cur->_parent = parent; } else { parent->_right = cur; cur->_parent = parent; } //更新平衡因子 //不平衡,则进行旋转 while (parent) { if (parent->_right==cur) parent->_bf++; else parent->_bf--; //父节点平衡因子为0时,退出(说明父节点的两边高度一样,算路径长度的话都一样,没有影响) if (parent->_bf == 0) break; //父节点平衡因子为1或-1的时候(说明是从0+1或0-1得来的),父节点两边高度不同,故需要继续更新平衡因子 else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = cur->_parent; } //父节点平衡因子为2或-2时,旋转 else //(parent->_bf==2||parent->_bf==-2) 旋转 { if (parent->_bf == -2) { if (cur->_bf == -1)//右单旋 { _RotateR(parent); } else //(cur->_bf==1) 左右单旋 { _RotateLR(parent); } } else //(parent->_bf==2) { if (cur->_bf == 1) //左单旋 { _RotateL(parent); } else //(cur->_bf==-1)右左单旋 { _RotateRL(parent); } } break; } } } Node* Find(const K& key) { if (_root == NULL) return false; Node* cur = _root; while (cur) { if (cur->_key > key) cur = cur->_left; else if (cur->_key < key) cur = cur->_right; else return cur; } return false; } bool Remove(const K& key) { if (_root == NULL) return false; Node* parent = NULL; Node* cur = _root; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } else { Node* del; if (cur->_right == NULL) { del = cur; if (parent == NULL) { _root = cur->_left; //_root->_bf = 0; } else { if (parent->_left == cur) { parent->_left = cur->_left; parent->_bf++; } else { parent->_right = cur->_left; parent->_bf--; } } delete del; } else if (cur->_left == NULL) { del = cur; if (parent == NULL) { _root = cur->_right; _root->_bf = 0; } else { if (parent->_left == cur) { parent->_left = cur->_right; parent->_bf++; } else { parent->_right = cur->_right; parent->_bf--; } } delete del; } else { parent = cur; Node* left = cur->_right; while (left->_left) { parent = left; left = left->_left; } del = left; cur->_key = left->_key; cur->_value = left->_value; if (parent->_left == left) { parent->_left = left->_right; parent->_bf++; } else { parent->_right = left->_right; parent->_bf--; } delete del; } break; } } if (cur == NULL) { return false; } while (parent) { if (parent->_bf == 0) { break; } else if (parent->_bf == 1 || parent->_bf == -1) { break; } else //parent->_bf=2||parent->_bf=-2 { if (parent->_bf == -2) { if (cur->_bf == -1) _RotateR(parent); else //cur->_bf=1 _RotateLR(parent); } else { if (cur->_bf == 1) _RotateL(parent); else _RotateRL(parent); } break; } } return true; } void InOrder() { _InOrder(_root); cout << endl; } //判断这棵树是否是平衡搜索树 bool IsBlance() { return _IsBlance(_root); } protected: 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; subL->_parent = NULL; } else { if (ppNode->_left == parent) { ppNode->_left = subL; subL->_parent = ppNode; } else { ppNode->_right = subL; subL->_parent = ppNode; } } subL->_bf = parent->_bf = 0; } 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; subR->_parent = NULL; } else { if (ppNode->_left == parent) { ppNode->_left = subR; subR->_parent = ppNode; } else { ppNode->_right = subR; subR->_parent = ppNode; } } subR->_bf = 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) //从subRL的右边插入 { parent->_bf = -1; subR->_bf = 0; } else if (bf == -1) //从subRL的左边插入 { parent->_bf = 0; subR->_bf = 1; } else //(bf=0) { parent->_bf = 0; subR->_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 = 0; subL->_bf = -1; } else if (bf == -1) { parent->_bf = 1; subL->_bf = 0; } else //bf=0 { parent->_bf = 0; subL->_bf = 0; } subLR->_bf = 0; } bool _IsBlance(Node* root) { if (root == NULL) return true; int right = _Height(root->_right); int left = _Height(root->_left); if (right - left != root->_bf || abs(right - left) >= 2) { cout << "平衡因子异常" << root->_key << endl; } return _IsBlance(root->_left) && _IsBlance(root->_right); } int _Height(Node* root) { if (root == NULL) return 0; int right = _Height(root->_right); int left = _Height(root->_left); if (right > left) return (right + 1); else return (left + 1); } void _InOrder(Node* root) { if (root == NULL) { return; } else { _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } } protected: Node* _root; }; #include "AVLTree.h" void Test1() { int a[9] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; AVLTree<int, int> avl; for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { avl.Insert(a[i],i); } avl.InOrder(); cout<<avl.IsBlance()<<endl; AVLTreeNode<int, int>* ret1 = avl.Find(18); if (ret1) cout << ret1->_key << ":" << ret1->_value << endl; else cout << "不存在ret1" << endl; AVLTreeNode<int, int>* ret2 = avl.Find(1); if (ret2) cout << ret2->_key << ":" << ret2->_value << endl; else cout << "不存在ret2" << endl; avl.Remove(26); avl.Remove(18); avl.Remove(15); avl.InOrder(); avl.Remove(3); cout << avl.Remove(7) << endl; avl.Remove(7); avl.Remove(9); avl.Remove(11); avl.Remove(14); avl.Remove(15); cout << avl.Remove(100) << endl; avl.Remove(16); avl.Remove(18); avl.Remove(26); avl.InOrder(); } void Test2() { int a[10] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; AVLTree<int, int> avl; for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { avl.Insert(a[i], i); } avl.InOrder(); cout << avl.IsBlance() << endl; AVLTreeNode<int, int>* ret1 = avl.Find(5); if (ret1) cout << ret1->_key << ":" << ret1->_value << endl; else cout << "不存在ret1" << endl; AVLTreeNode<int, int>* ret2 = avl.Find(88); if (ret2) cout << ret2->_key << ":" << ret2->_value << endl; else cout << "不存在ret2" << endl; avl.Remove(14); avl.Remove(16); avl.Remove(7); avl.InOrder(); avl.Remove(15); avl.Remove(6); avl.Remove(5); cout << avl.Remove(4) << endl; avl.Remove(4); avl.Remove(3); avl.Remove(2); avl.Remove(1); cout << avl.Remove(100) << endl; avl.Remove(7); avl.Remove(16); avl.InOrder(); } int main() { Test1(); cout << endl; cout << endl; Test2(); return 0; }
实现结果:
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
文章名称:平衡二叉搜索树-创新互联
本文路径:https://www.cdcxhl.com/article14/cedide.html
成都网站建设公司_创新互联,为您提供网站设计、小程序开发、域名注册、品牌网站设计、网站策划、App设计
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联