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
分享标题:AVL树增删查找
URL地址:http://cdkjz.cn/article/gdgdso.html