#pragma once #include <iostream> using namespace std; #define NEG -1 #define ZERO 0 #define POS 1 template <class K,class V> struct AVLTreeNode//树的节点 { K _key; V _value; AVLTreeNode* _left; AVLTreeNode* _right; AVLTreeNode* _parent; int _bf; AVLTreeNode(const K& key,const V& value) :_key(key) , _value(value) , _left(NULL) , _right(NULL) , _parent(NULL) , _bf(0)//平衡因子 取值 -1 0 1 (左高1 相等 右高1) {} }; template<class K,class V> class AVLTree { typedef AVLTreeNode<K, V> 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, *prev = NULL;//当前 与 之前 节点指针 while (cur){ if (cur->_key < key)//插入key 比当前节点 key大 跳到右 { if (cur->_right){//右不为空继续 prev = cur; cur = cur->_right; if (cur->_bf == ZERO)//如果节点的bf为0,说明插入(如果成功),会改变prev->bf的值 prev->_bf++; } else {//如果右为空 到达插入节点位置,插入cur->bf ++ cur->_right = new Node(key,value); cur->_right->_parent = cur; cur->_bf++; break; } } else if (cur->_key>key)//同理 向左 插入 { if (cur->_left){ prev = cur; cur = cur->_left; if (cur->_bf == ZERO) prev->_bf--; } else { cur->_left = new Node(key, value); cur->_left->_parent = cur; cur->_bf--; break; } } else//key相等,插入失败,依次将改变的平衡因子 改回来 { while (prev&&cur->_bf == ZERO) { if (prev->_left == cur) prev->_bf++; else prev->_bf--; cur = prev; prev = prev->_parent; } return false; } } //插入结束 对整棵树进行调节 使其继续平衡 //高度不变 if (cur->_bf == ZERO) return true; else//高度改变 { //找高度变为-2 或 2的节点旋转 while (prev) { if (prev->_bf < -1)//左高2 { if (cur->_bf <= -1)//右旋 { _RotateR(prev); cout << "右旋"<<endl; break; } else//左右旋 { _RotateL(cur); _RotateR(prev); cout << "左右旋" << endl; break; } } else if (prev->_bf > 1)//右高2 { if (cur->_bf >= 1)//左旋 { _RotateL(prev); cout << "左旋" << endl; break; } else//右左旋 { _RotateR(cur); _RotateL(prev); cout << "右左旋" << endl; break; } } cur = prev; prev = prev->_parent; } } return true; } bool IsBalance() { if (_root == NULL) return true; return _Isbalance(_root); } Node* Find(const K& key) { Node * cur = _root; while (cur){ if (cur->_key > key) cur = cur->_left; else if (cur->_key < key) cur = cur->_right; else return cur; } return NULL; } bool Remove(const K& key) { if (_root == NULL) { return false;//空树删除失败 } Node* cur = _root, *prev = NULL; while (cur){ if (cur->_key < key)//删除位置在cur 右 { if (cur->_right){//右非空,继续找 prev = cur; cur = cur->_right; } else//右空,未找到删除节点 返回 return false; } else if (cur->_key>key)//删除位置在左 { if (cur->_left){ prev = cur; cur = cur->_left; } else return false; } else { Node* parent = cur->_parent;//记录删除节点的 父 if (cur->_left == NULL)//删除节点 左空,直接使其右与prev相连 { if (prev == NULL){//prev为空,删除根节点,根节点改变 _root = cur->_right; delete cur; return true; } if (prev->_right == cur){//prev右为cur,cur的右连到prev右 prev->_bf--;//平衡因子 减少 prev->_right = cur->_right; if (cur->_right) cur->_right->_parent = prev; } if (prev->_left == cur){//prev左为 cur prev->_left = cur->_right; prev->_bf++; if (cur->_right) cur->_right->_parent = prev; } delete cur;//释放节点 cur = prev;//将cur prev指向有效节点 prev = cur->_parent; } else if (cur->_right == NULL)//同上 cur右为空 { if (prev == NULL){ _root = cur->_left; delete cur; return true; } if (prev->_right == cur){ prev->_bf--; prev->_right = cur->_left; if (cur->_left) cur->_left->_parent = prev; } if (prev->_left == cur){ prev->_left = cur->_left; prev->_bf++; if (cur->_left) cur->_left->_parent = prev; } delete cur; cur = prev; prev = cur->_parent; } else {//cur左右都非空,为了避免换当前root的复杂操作,替换为删除cur左孩子 最右 节点 ,或者cur右孩子的 最左 节点,将其内容拷贝给cur Node* tmp = cur; prev = cur; cur = cur->_right; while (cur->_left)//找右树最左 { prev = cur; cur = cur->_left; } tmp->_key = cur->_key; tmp->_value = cur->_value;//拷贝值 if (cur == prev->_left)//调节prev bf并将 cur右树连接到prev prev->_bf++; prev->_left = cur->_right; } if (cur == prev->_right)//同上 { prev->_bf--; prev->_right = cur->_right; } tmp = cur;//记录删除位置 cur = prev; parent = cur;//cur prev 指向有效节点 prev = cur->_parent; delete tmp;//删除tmp } while (prev &&cur->_bf == ZERO)//删除节点 父树高度可能改变,依次确认并修改 bf (cur bf为0 说明是 -1 或 1 变来 高度发生改变 需修改父节点 bf) { if (cur == prev->_left){ prev->_bf++; } if (cur == prev->_right) { prev->_bf--; } cur = prev; prev = prev->_parent; } prev = parent;//prev指向 实际删除节点的父节点 if (prev->_bf < ZERO) cur = prev->_left; if (prev->_bf > ZERO) cur = prev->_right; if (prev->_bf == ZERO){ cur = prev; prev = prev->_parent; } break; } } //找高度变为-2 或 2的节点旋转 while (prev) { if (prev->_bf < -1)//左高2 { cur = prev->_left;//因为删除一侧节点可能需要另一侧旋转,因此需要对 cur重新赋值 if (cur && (cur->_bf <= -1 || cur->_bf == ZERO))//右旋 { _RotateR(prev); if (prev->_left&&prev->_right == NULL)//判断旋转后 prev的bf prev->_bf--; cout << "右旋" << endl; } else//左右旋 { _RotateL(cur); _RotateR(prev); cout << "左右旋" << endl; } cur = prev->_parent; prev = cur->_parent; while (prev&&cur->_bf == ZERO)//依次修改旋转完毕的prev的bf { if (cur == prev->_left) prev->_bf++; else prev->_bf--; cur = prev; prev = prev->_parent; } } else if (prev->_bf > 1)//右高2 { cur = prev->_right; if (cur && (cur->_bf >= 1 || cur->_bf == ZERO))//左旋 { _RotateL(prev); cout << "左旋" << endl; if (prev->_right&&prev->_left == NULL) prev->_bf++; } else//右左旋 { _RotateR(cur); _RotateL(prev); cout << "右左旋" << endl; } cur = prev->_parent; prev = cur->_parent; while (prev&&cur->_bf == ZERO) { if (cur == prev->_left) prev->_bf++; else prev->_bf--; cur = prev; prev = prev->_parent; } } cur = prev; if (prev) prev = prev->_parent; } return true; } private: Node* _root; int _height(Node* root) { if (root == NULL) return 0; int left = 1, right =1; left += _height(root->_left); right += _height(root->_right); return left > right ? left : right; } bool _Isbalance(Node* root)//判断 数是否平衡 bf是否匹配 { if (root == NULL) return true; /*if (root ->_left==NULL&&root->_right==NULL) return true;*/ bool left = _Isbalance(root->_left); bool right = _Isbalance(root->_right); int num1 = 1; num1+=_height(root->_left); int num2 = 1; num2+=_height(root->_right); if (left == false || right == false) { cout << "not balace!" << " key: " << root->_key << "bf: " << root->_bf << endl; return false; } if (num2-num1!=root->_bf) { cout << "bf error!" << "key:" << root->_key << "bf: " << root->_bf << "a-b:" << num1-num2 << endl; return false; } if (abs(num1-num2) <= 1) return true; return false; } //旋转后 bf 调节总结:左旋 bf 减小 右旋 bf 增加;sub=2 ,parent变化 3,sub变化 2;sub=1,parent 变化2,sub变化 1; void _RotateR(Node* parent)//右旋 { Node* subL = parent->_left; Node* subLR = subL->_right; Node* ppNode=parent->_parent; subL->_right = parent; parent->_parent = subL; parent->_left = subLR; if (subLR) subLR->_parent = parent; if (ppNode) { if (ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; } else _root = subL; subL->_parent = ppNode;//旋转 //修改 bf if (subL->_bf == -2){ parent->_bf = 1; subL->_bf=0; } else { subL->_bf++; parent->_bf = 0; } } void _RotateL(Node* parent)//左旋 { Node* subR= parent->_right; Node* subRL = subR->_left; Node* ppNode = parent->_parent; subR->_left = parent; parent->_parent = subR; parent->_right = subRL; if (subRL) subRL->_parent = parent; if (ppNode) { if (ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; } else _root = subR; subR->_parent = ppNode;//以上为左旋转 //以下下修改 bf 值 if (subR->_bf == 2)//右孩子的高度为2 说明旋转前 高度差在右孩子的下方,旋转后parent 右支 没有可以连接的,高度会降3 从2变为-1 { parent->_bf = -1; subR->_bf = 0; } else{ //右孩子高度为1,旋转后高度将2 buf为 0,而右孩子 高度将1; parent->_bf = 0; subR->_bf--; } } };
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。