平衡二叉搜索树
AVL树又称高度平衡的二叉搜索树,是1962年俄罗斯的数学家提出来的。它能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度。
成都创新互联专注于章丘企业网站建设,自适应网站建设,商城网站开发。章丘网站建设公司,为章丘等地区提供建站服务。全流程按需网站制作,专业设计,全程项目跟踪,成都创新互联专业和态度为您提供的服务
AVL的性质:
(1)左子树和右子树的高度之差的绝对值不超过1。
(2)树中的每个左子树和右子树都是AVL树。
(3)每个节点都有一个平衡因子,任一节点的平衡因子是-1,0,1(每个节点的平衡因子等于右子树的高度减去左子树的高度)。
代码实现如下:
#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) :_key(key) , _value(value) , _left(NULL) , _right(NULL) , _parent(NULL) , _bf(0) {} }; template class AVLTree{ typedef AVLTreeNode 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 avl; for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { avl.Insert(a[i],i); } avl.InOrder(); cout< * ret1 = avl.Find(18); if (ret1) cout << ret1->_key << ":" << ret1->_value << endl; else cout << "不存在ret1" << endl; AVLTreeNode * 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 avl; for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { avl.Insert(a[i], i); } avl.InOrder(); cout << avl.IsBlance() << endl; AVLTreeNode * ret1 = avl.Find(5); if (ret1) cout << ret1->_key << ":" << ret1->_value << endl; else cout << "不存在ret1" << endl; AVLTreeNode * 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; }
实现结果:
分享名称:平衡二叉搜索树
当前URL:http://scyanting.com/article/iigeio.html