数据结构中的AVL树是什么意思

今天就跟大家聊聊有关数据结构中的AVL树是什么意思，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

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) {}};templateclass 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(){ AVLTree avlt; //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树是什么意思有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注行业资讯频道，感谢大家的支持。