您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
AVL树
AVL树又称为高度平衡的二叉搜索树,它能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度;
AVL树的性质
左子树和右子树的高度之差的绝对值不超过1
树中的每个左子树和右子树都是AVL树
下面实现一棵AVL树,主要实现其插入部分:
#pragma once template <class K, class V> struct AVLTreeNode { K _key; V _val; AVLTreeNode<K, V>* _left; AVLTreeNode<K, V>* _right; AVLTreeNode<K, V>* _parent; int _bf;//平衡因子 AVLTreeNode(const K& key, const K& val) :_key(key) ,_val(val) ,_left(NULL) ,_right(NULL) ,_parent(NULL) ,_bf(0) {} }; template <class K, class V> class AVLTree { typedef AVLTreeNode<K, V> Node; public: AVLTree() :_root(NULL) {} ~AVLTree() { _Clear(_root); } bool Insert(const K& key, const V& val) { if(_root == NULL)//如果根结点为NULL,则创建一个结点,返回真 { _root = new Node(key, val); return true; } Node* cur = _root; Node* prev = NULL; while(cur != NULL)//查找合适的位置插入 { if(cur->_key == key)//如果结点已存在,则返回假 return false; else if(cur->_key > key)//如果要插入值小于当前结点,则去左子树查找 { prev = cur; cur = cur->_left; } else//如果插入值大于当前结点,则去右子树查找 { prev = cur; cur = cur->_right; } } //循环结束,则表明找到了合适的位置,判断应插入左边还是右边 Node* tmp = new Node(key, val); if(key < prev->_key) prev->_left = tmp; else prev->_right = tmp; tmp->_parent = prev; //插入结点之后,需要判断当前树是否满足AVL树的规则,若不满足,进行相应的调整 while(prev != NULL) { //平衡因子为右边高度减去左边高度 if(prev->_left == tmp) --(prev->_bf); else ++(prev->_bf); if(prev->_bf == 0)//如果平衡因子为0,则一定平衡,因为可以看做是在同一层插入了一个结点,对高度并无影响 break; else if(prev->_bf == 1 || prev->_bf == -1)//如果平衡因子为1/-1,则表明高度有所变化,需要继续向上调整 { tmp = prev; prev = prev->_parent; } else//说明平衡因子的绝对值大于1,则这个时候不满足AVL树的性质,需要进行调整 { if(prev->_bf == 2) { if(tmp->_bf == 1) _RotateL(prev); else { _RotateR(tmp); _RotateL(prev); } } else { if(tmp->_bf == -1) _RotateR(prev); else { _RotateL(tmp); _RotateR(prev); } } break; } } return true; } void InOrder() { _InOrder(_root); cout<<endl; } protected: void _Clear(Node* root) { if(root != NULL) { _Clear(root->_left); _Clear(root->_right); delete root; root = NULL; } } //左单旋 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; else { if(ppNode->_left == parent) ppNode->_left = subR; else ppNode->_right = subR; } subR->_parent = ppNode; parent->_bf = subR->_bf = 0; } //右单旋 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; else { if(ppNode->_left == parent) ppNode->_left = subL; else ppNode->_right = subL; } subL->_parent = ppNode; parent->_bf = subL->_bf = 0; } void _InOrder(Node* root) { if(root != NULL) { _InOrder(root->_left); cout<<root->_key<<" "; _InOrder(root->_right); } } protected: Node* _root; }; void Test() { int arr[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14}; //int arr[] = {16, 3, 7, 11, 9, 26, 18, 14, 15}; AVLTree<int, int> t; for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i) t.Insert(arr[i], i); t.InOrder(); }
其中的左右单旋如下图所示:
运行程序:
《完》
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。