AVL树:又称高度平衡的二叉搜索树,它能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度。
创新互联是网站建设技术企业,为成都企业提供专业的网站设计、成都网站设计,网站设计,网站制作,网站改版等技术服务。拥有十载丰富建站经验和众多成功案例,为您定制适合企业的网站。十载品质,值得信赖!AVL树的性质
左子树和右子树的高度之差的绝对值不超过1
树中的每个左子树和右子树都是AVL树
#pragma once #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) :_left(NULL) , _right(NULL) , _parent(NULL) , _key(key) , _value(value) , _bf(0) {} }; template class AVLTree { typedef AVLTreeNode Node; public: AVLTree() :_root(NULL) {} ~AVLTree() {} 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->_right; } else if (cur->_key>key) { parent = cur; cur = cur->_left; } else { cout << "该节点已经存在" << endl; return false; } } cur = new Node(key, value); if (parent->_key < key) { parent->_right = cur; cur->_parent = parent; } else { parent->_left = cur; cur->_parent = parent; } //更新平衡因子 while (parent) { if (cur == parent->_right) ++parent->_bf; else if (cur == parent->_left) --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) { //左旋转 RotateL(parent); } else if (cur->_bf==-1) { RotateRL(parent); } } else { if (cur->_bf == -1) {//右旋转 RotateR(parent); } else if (cur->_bf == 1) { RotateLR(parent); } } break; } } return true; } Node* Find(const K& key) { if (_root == NULL) return NULL; Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key>key) { cur = cur->_left; } else { cout << "找到该数" << endl; return cur; } } return NULL; } bool Remove(const K& key) { if (_root == NULL) return false; Node* cur = _root; Node* parent = NULL; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key>key) { parent = cur; cur = cur->_left; } else { if (cur->_left == NULL && cur->_right == NULL) {//1.左右都为空 if (parent == NULL) _root = NULL;//若只有一个节点 else { if (parent->_left == cur) parent->_bf++; else parent->_bf--; } delete cur; cur = NULL; } else if (cur->_left&&cur->_right) {//2.左右都不为空 Node* RightMin = cur->_right; while (RightMin->_left) { parent = RightMin; RightMin = RightMin->_left; } cur->_key = RightMin->_key;//采用替换法删除 cur->_value = RightMin->_value; if (parent->_left == RightMin) { parent->_bf++; parent->_left = RightMin->_right; } else { parent->_bf--; parent->_right = RightMin->_right; } delete RightMin; RightMin = NULL; } else {//3.左为空或右为空 if (cur->_left) {//1).右为空 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--; } } } else {//2).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 cur; cur = NULL; } break; } } while (parent) {//平衡因子为0或1、-1对这个树的高度不会产生影响 if (parent->_parent->_left == parent) parent->_parent->_bf++; else parent->_parent->_bf--; if (parent->_parent->_bf == 0) return true; else if (parent->_parent->_bf==1 || parent->_parent->_bf==-1) { cur = parent; parent = cur->_parent; } else { if (parent->_bf == -2) { if (cur->_bf == -1) { RotateR(parent); } else { RotateLR(parent); } } else { if (cur->_bf == 1) { RotateL(parent); } else { RotateRL(parent); } } cout << "删除成功" << endl; return true; } } return false; } void RotateR(Node* parent) { Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) { subLR->_parent = parent; } Node* ppNode = parent->_parent; subL->_right = parent; parent->_parent = subL; if (ppNode == NULL)//若要调整的节点为根节点 { _root = subL; subL->_parent = NULL; } else { if (parent == ppNode->_left) { ppNode->_left=subL; } 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) { subRL->_parent = parent; } Node* ppNode = parent->_parent; subR->_left = parent; parent->_parent = subR;//*若有父节点一定要指向它的父节点 if (ppNode== NULL)//若要调整的节点为根节点 { _root = subR; subR->_parent = NULL; } else { if (parent == ppNode->_left) { ppNode->_left = subR; } 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) { parent->_bf = -1; subR->_bf = 0; } else if (bf == -1) { parent->_bf = 0; subR->_bf = 1; } else //bf=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 //bf=0; { subL->_bf = parent->_bf = 0; } //subLR->_bf = 0; } void InOrder() { _InOrder(_root); cout << endl; } bool IsBalance() { return _IsBalance(_root); } int Height() { return _Height(_root); } protected: 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 _IsBalance(Node* root) { if (root == NULL) { return true; } int left = _Height(root->_left); int right = _Height(root->_right); if ((right-left) != root->_bf) { cout << root->_key <<"平衡因子异常" << endl; return false; } return abs(right - left) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right); } void _InOrder(Node* root) { if (root == NULL) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } protected: Node* _root; }; void Test() { AVLTree avl; int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; //int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; int size = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i 另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
当前文章:AVL树增删查找-创新互联
路径分享:http://cdweb.net/article/ijohj.html