赞
踩
目录
搜索二叉树虽然可以缩短查找效率,但是数据如果有序或接近有序搜索二叉树将退化为单只树,查找元素相当于在顺序表中搜索元素,效率低下。所以有了平衡二叉树,当向二叉树中插入新节点后,如果能保证每个节点的左右子树高度差的绝对值不超过1,即可降低树的高度,从而减少平均搜索长度。
一颗AVL树或者是空树,或者是具有以下性质的搜索二叉树:
·它的左右子树都是AVL树
·左右子树高度差的绝对值不超过1
如果一颗搜索二叉树是平衡的,他就是AVL树。如果它有n个节点,其高度可保持在O(log2n),搜索时间复杂度O(log2n)。
- template<class K, class V>
- struct AVLTreeNode
- {
- AVLTreeNode<K, V>* _left;
- AVLTreeNode<K, V>* _right;
- AVLTreeNode<K, V>* _parent;
-
- pair<K, V> _kv;
- int _bf; // balance factor
-
- AVLTreeNode(const pair<K, V>& kv)
- :_left(nullptr)
- , _right(nullptr)
- , _parent(nullptr)
- , _kv(kv)
- , _bf(0)
- {}
- };
- bool Insert(const pair<K, V>& kv)
- {
- if (_root == nullptr)
- {
- _root = new Node(kv);
- return true;
- }
-
- Node* parent = nullptr;
- Node* cur = _root;
- //找到要插入的节点
- while (cur)
- {
- if (cur->_kv.first < kv.first)
- {
- parent = cur;
- cur = cur->_right;
- }
- else if (cur->_kv.first > kv.first)
- {
- parent = cur;
- cur = cur->_left;
- }
- else
- {
- return false;
- }
- }
-
- cur = new Node(kv);
- if (parent->_kv.first > kv.first)
- {
- parent->_left = cur;
- }
- else
- {
- parent->_right = cur;
- }
- cur->_parent = parent;
-
- //更新平衡因子
- while (parent)
- {
- if (cur == parent->_right)
- {
- parent->_bf++;
- }
- else
- {
- parent->_bf--;
- }
-
- if (parent->_bf == 1 || parent->_bf == -1)
- {
- //继续想上更新
- parent = parent->_parent;
- cur = cur->_parent;
- }
- else if (parent->_bf == 0)
- {
- break;
- }
- else if (parent->_bf == 2 || parent->_bf == -1)
- {
- //进行旋转处理
- if (parent->_bf == 2 && cur->_bf == 1)
- {
- RotateL(parent); //右边引起的高度变高进行左旋
- }
- else if (parent->_bf == -2 && cur->_bf == -1)
- {
- RotateR(parent); //左边引起的高度变高进行右旋
- }
- else if (parent->_bf == 2 && cur->_bf == -1)
- {
- RotateRL(parent); //插入在右子树的左子树引起的高度变高先右旋在左旋
- }
- else if (parent->_bf == -2 && cur->_bf == 1)
- {
- RotateLR(parent); //插入在左子树的右子树引起的高度变高先左旋再右旋
- }
- else
- {
- assert(false);
- }
- break;
- }
- else
- {
- assert(false);
- }
- }
- return true;
- }
上图插入前,AVL树是平衡的,新节点插入到30的左子树中,30的左子树高度增加,导致60为根的二叉树不平衡,要让60平衡,只能将60左子树的高度减少一层,右子树增加一层,即将左子树上提,60转下来60变为30的右子树,如果30有右子树,右子树根的值一定大于30,小于60,所以放在60的左子树,旋转完成后更新平衡因子。
旋转过程中有以下几种情况需要考虑
·30节点的右孩子可能存在,也可能不存在
·60可能是根节点,也可能是子树,如果是根节点,旋转完成后要更新根节点,如果是子树,可能是某个节点的左子树也可能是右子树
- void RotateR(Node* parent)
- {
- Node* subL = parent->_left;
- Node* subLR = subL->_right;
-
- parent->_left = subLR;
- if (subLR)
- subLR->_parent = parent;
-
- Node* ppnode = parent->_parent;
-
- subL->_right = parent;
- parent->_parent = subL;
-
- if (parent == _root)
- {
- _root = subL;
- _root->_parent = nullptr;
- }
- else
- {
- if (ppnode->_left == parent)
- {
- ppnode->_left = subL;
- }
- 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)
- subRL->_parent = parent;
-
- Node* ppnode = parent->_parent;
-
- subR->_left = parent;
- parent->_parent = subR;
-
- if (ppnode == nullptr)
- {
- _root = subR;
- _root->_parent = nullptr;
- }
- else
- {
- if (ppnode->_left == parent)
- {
- ppnode->_left = subR;
- }
- else
- {
- ppnode->_right = subR;
- }
- subR->_parent = ppnode;
- }
-
- parent->_bf = subR->_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;
- subLR->_bf = 0;
- subL->_bf = -1;
- }
- else if (bf == -1)
- {
- parent->_bf = 1;
- subLR->_bf = 0;
- subL->_bf = 0;
- }
- else if (bf == 0)
- {
- parent->_bf = 0;
- subLR->_bf = 0;
- subL->_bf = 0;
- }
- else
- {
- assert(false);
- }
- }
- void RotateRL(Node* parent)
- {
- Node* subR = parent->_right;
- Node* subRL = subR->_left;
- int bf = subRL->_bf;
-
- RotateR(parent->_right);
- RotateL(parent);
-
- if (bf == 1)
- {
- subR->_bf = 0;
- parent->_bf = -1;
- subRL->_bf = 0;
- }
- else if (bf == -1)
- {
- subR->_bf = 1;
- parent->_bf = 0;
- subRL->_bf = 0;
- }
- else if (bf == 0)
- {
- subR->_bf = 0;
- parent->_bf = 0;
- subRL->_bf = 0;
- }
- else
- {
- assert(false);
- }
- }
1、验证其为搜索二叉树
如果中序遍历可得到一个有序的序列,就说明为搜索二叉树
2、验证其为平衡树
- bool _IsBalance(Node* root)
- {
- if (root == nullptr)
- {
- return true;
- }
- int leftH = _Height(root->_left);
- int rightH = _Height(root->_right);
-
- if (rightH - leftH != root->_bf)
- {
- cout << root->_kv.first << "节点平衡因子异常" << endl;
- return false;
- }
-
- return abs(leftH - rightH) < 2
- && _IsBalance(root->_left)
- && _IsBalance(root->_right);
- }
AVL树是一颗绝对平衡的搜索二叉树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度,即O(log2n)。但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的,可以考虑AVL树,但一个结构经常修改,就不太合适了。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。