大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
今天就跟大家聊聊有关数据结构中的AVL树是什么意思,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下内容,希望大家根据这篇文章可以有所收获。
创新互联公司长期为上千客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为玉屏企业提供专业的网站制作、成都网站设计,玉屏网站改版等技术服务。拥有十年丰富建站经验和众多成功案例,为您定制开发。
1、AVL树简介
AVL树本质上还是一棵二叉搜索树,又称高度平衡的二叉搜索树。它能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度。对于二叉搜索树的介绍和实现,可查看本人上一篇博客。
2、AVL树的特点
1)本身首先是一棵二叉搜索树。
2)带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。
3)树中的每个左子树和右子树都是AVL树。
4)每个结点都有一个平衡因子,任一结点的平衡因子是-1,0,1.
注:结点的平衡因子 = 右子树高度 - 左子树高度
3、AVL树的效率
一棵AVL树有N个结点,其高度可以保持在lgN,插入/删除/查找的时间复杂度也是lgN。
AVL树的复杂程度真是比二叉搜索树高了整整一个数量级——它的原理并不难弄懂,但要把它用代码实现出来还真的有点费脑筋。下面我们来看看AVL树实现的接口,通过三叉链进行结点的实现。
templatestruct AVLTreeNode//三叉链 { AVLTreeNode * _left; AVLTreeNode * _right; AVLTreeNode * _parent; K _key; V _value; int _bf;//右子树与左子树的高度差 AVLTreeNode(const K& key = K(), const V& value = V())//加上K()和V(),可缺省构造 :_left(NULL) , _right(NULL) , _parent(NULL) , _key(key) , _value(value) , _bf(0) {} }; template class AVLTree { typedef AVLTreeNode Node; public: AVLTree() :_root(NULL) {} void Insert(const K& key, const V& value); Node* Find(const K& key); int Height(); bool IsBalance(); void PrintAVLTree(); private: Node* _Find(Node* root, const K& key); void _RotateL(Node*& parent); void _RotateR(Node*& parent); void _RotateLR(Node*& parent); void _RotateRL(Node*& parent); int _Height(Node* root); bool _IsBalance(Node* root); void _PrintAVLTree(Node* root); protected: Node* _root; };
下面对插入进行元素的分析:
1)判断树是否为空,为空时,新建根结点。
2)查找插入的key是否存在,存在就退出函数,不存在就执行3)。
3)找到插入key的位置,然后插入结点cur。
4)更新平衡因子:从cur开始向上其父结点进行更新平衡因子,如果结点的平衡因子不满足AVL树,进行旋转调节平衡因子。
templatevoid AVLTree ::Insert(const K& key, const V& value) { if (_root == NULL) { _root = new Node(key, value); return; } if (Find(key))//存在key { return; } Node* prev = NULL; Node* cur = _root; while (cur)//插入key的位置cur { if (key < cur->_key) { prev = cur; cur = cur->_left; } else if (key > cur->_key) { prev = cur; cur = cur->_right; } } cur = new Node(key, value);//插如结点cur if (prev->_key > key) { prev->_left = cur; cur->_parent = prev; } else if (prev->_key < key) { prev->_right = cur; cur->_parent = prev; } //prev为cur的上一个结点,即为cur是prev的父亲结点 prev = cur; cur = prev->_parent; while (cur) { //更新平衡因子:从插如的cur开始向上更新平衡因子 cur->_bf = _Height(cur->_right) - _Height(cur->_left); if (cur->_bf != -1 && cur->_bf != 1 && cur->_bf != 0)//不满足AVL树的结点,进行旋转调节平衡因子 {//平衡因子为2时,一定存在右子树;平衡因子为-2时,一定存在左子树 //左单旋:2 1(平衡因子) if (cur->_bf == 2 && cur->_right->_bf == 1) { _RotateL(cur);//引用传递 } //右单旋:-2 -1 else if (cur->_bf == -2 && cur->_left->_bf == -1) { _RotateR(cur); } //左右旋转:-2 1 else if (cur->_bf == -2 && cur->_left->_bf == 1) { _RotateLR(cur); } //右左旋转:2 -1 else if (cur->_bf == 2 && cur->_right->_bf == -1) { _RotateRL(cur); } } prev = cur; cur = cur->_parent; } }
进行旋转调节平衡因子,分四种情况:
(1)左单旋:cur的平衡因子为2,cur->_right的平衡因子为1。
(2)右单旋:cur的平衡因子为-2,cur->_left的平衡因子为-1。
(3)左右旋转:cur的平衡因子为-2,cur->_left的平衡因子为1。
(4)右左旋转:cur的平衡因子为-2,cur->_right的平衡因子为-1。
左右旋转和右左旋转可通过调用左单旋和右单旋进行,注意结束后重置平衡因子。
如果不是很清楚,可以自己画图进行分析。
左单旋:
templatevoid AVLTree ::_RotateL(Node*& parent) { Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL;//1 subR->_parent = parent->_parent;//1 subR->_left = parent;//2 parent->_parent = subR;//2 if (subRL)//注意不为空,进行链接 subRL->_parent = parent; parent->_bf = subR->_bf = 0; //进行subR的父亲结点和subR的链接 if (subR->_parent == NULL)//为空时,parent为根结点,更改根结点 _root = subR; else//不为空,进行链接 { if (subR->_parent->_key > subR->_key) subR->_parent->_left = subR; else subR->_parent->_right = subR; } parent = subR; }
右单旋:
templatevoid AVLTree ::_RotateR(Node*& parent) { Node* subL = parent->_left; Node* subLR = subL->_right; //不能变换顺序 parent->_left = subL->_right;//1 subL->_parent = parent->_parent;//1 subL->_right = parent;//2 parent->_parent = subL;//2 if (subLR)//注意不为空,进行链接 subLR->_parent = parent; parent->_bf = subL->_bf = 0; //进行subL的父亲结点和subL的链接 if (subL->_parent == NULL)//为空时,parent为根结点,更改根结点 _root = subL; else//不为空,进行链接 { if (subL->_parent->_key > subL->_key) subL->_parent->_left = subL; else subL->_parent->_right = subL; } parent = subL; }
左右旋转:
templatevoid AVLTree ::_RotateLR(Node*& parent) { Node* pNode = parent;//需重新定义parent,在进行左右旋转后,parent指向发生了变化 Node* subLNode = pNode->_left; Node* subLRNode = subLNode->_right; _RotateL(parent->_left); _RotateR(parent); //在单旋时,parent和subL的平衡因子都为0,在进行左右旋转和右左旋转会出错,故重新设置平衡因子 //subLRNode的平衡因子存在三种情况:为0,为-1,为1。subLRNode的平衡因子影响parent和subL的平衡因子 if (subLRNode->_bf == 1) { pNode->_bf = 1; subLNode->_bf = 0; } else if (subLRNode->_bf == -1) { pNode->_bf = 0; subLNode->_bf = -1; } else { parent->_bf = 0; subLNode->_bf = 0; } }
右左旋转:
templatevoid AVLTree ::_RotateRL(Node*& parent) { Node* pNode = parent; Node* subRNode = pNode->_right; Node* subRLNode = subRNode->_left; _RotateR(parent->_right); _RotateL(parent); if (subRLNode->_bf == 1) { pNode->_bf = -1; subRNode->_bf = 0; } else if (subRLNode->_bf == -1) { pNode->_bf = 0; subRNode->_bf = 1; } else { pNode->_bf = 0; subRNode->_bf = 0; } }
测试用例如下:
void AVLTreeTest() { AVLTreeavlt; //int arr[10] = { 16, 3, 7, 11, 9, 26, 18, 14, 15, 23 }; int arr[10] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (int i = 0; i < 10; ++i) { avlt.Insert(arr[i], i); avlt.PrintAVLTree(); } cout << avlt.IsBalance() << endl; }
看完上述内容,你们对数据结构中的AVL树是什么意思有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注创新互联行业资讯频道,感谢大家的支持。