当前位置：首页 > news >正文

map和set(二)——AVL树的简单实现

news 来源：原创 2024/5/8 13:12:45

引入

二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。简单来说就是之前二叉搜索树由于可能在某一个节点上一直深入，按照最坏情况算这的时间复杂度就高了起来，而AVL树这其中之一的平衡树

1.AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度

AVL树又称高度平衡二叉搜索树

任何AVL树都满足一下条件:

它的左右子树都是AVL树
任何树及其子树的高度差(也就是平衡因子)的绝对值不超过1

比如：

当然平衡因子不一定是必须的，它只是一种控制方式(让我们更便捷地控制这棵树)

为何是不超过1，而不是0呢？0不是更加平衡吗？

由于树的节点是一个个插入的，无法保证绝对的平衡(有些情况无法满足高度差为0)；因此高度差不超过1

2.AVL树节点的定义

和二叉搜索树类似，只不过多了个平衡因子

//AVL树的节点
template<class K,class V>
struct AVLTreeNode
{AVLTreeNode<K,V>* _left;AVLTreeNode<K,V>* _right;AVLTreeNode<K,V>* _parent;int _bf = 0;//平衡因子pair<K, V> _kv;//构造AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}};

3.AVL树的插入

3.1插入

AVL树就是在二叉搜索树的基础上引进了平衡因子(bf)，因此AVL树也可以看做二叉搜索树

AVL树的插入过程可以分为两步:

以二叉搜索树的方式插入新节点
调整节点的平衡因子

二叉搜索树的方式插入

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 (kv.first > cur->_kv.first)//插入的值比遍历的值大{parent = cur;//cur往下遍历时，父节点同时要往下走cur = cur->_right;//往右走}else if (kv.first < cur->_kv.first)//插入的值比遍历的值小{parent = cur;cur = cur->_left;//往左走}else//说明插入的值已经存在，return false{return false;}}//走到这说明已经找到可以插入的地方 //创建一个新节点cur = new Node(kv);//判断插入的节点该连接到父节点的左还是右if (cur->_kv.first > parent->_kv.first)//cur 的值大于父节点的值，连右{parent->_right = cur;}else{parent->_left = cur;}//接下来就是判断平衡因子的时候了return true;}

判断平衡因子

平衡因子 = 右子树高度-左子树高度

插入节点会影响哪些节点的平衡因子呢？新增节点的部分祖先

更新原则：

若cur是此父节点的左子树(节点)那么父节点的平衡因子-- ，是右子树(节点)那么父节点平衡因子++

是否继续更新取决于父节点的高度是否变化，是否会影响爷爷节点
一直往上走直至parent为nullptr(根节点的父节点为空)或者平衡因子为0或者平衡因子为2(需要旋转)

当cur(新增节点插入后)，有三种情况

情况1：

更新后父节点(parent)的平衡因子(bf)为 0 ，parent所在子树高度不变，不会影响爷爷；说明更新前parent的bf为1或-1，往父节点矮的那边插入节点，左右均衡，parent所在子树的高度不变

情况2：

更新后父节点的平衡因子为1或-1，parent所在子树高度改变了，会影响爷爷，继续往上更新；说明更新前parent的bf为0(本身平衡了)，往p的任意一边插入，使父节点变得不均衡，但不违反规则

情况3：

更新后父节点的平衡因子为2或-2，说明父节点所在的子树违反了平衡规则，需要旋转处理

		//接下来就是判断平衡因子的时候了cur->_parent = parent;while (parent){if (cur == parent->_left)//cur在父左 父bf--{parent->_bf--;}else//cur在父右 父bf++{parent->_bf++;}if (parent->_bf == 0)//父bf==0 break{break;}else if (parent->_bf == 1 || parent->_bf == -1)//父bf为1 or -1继续往上{cur = cur->_parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//平衡因子为2 只能旋转了//右高左低 左单旋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)//两边都高左右双旋{RotateLR(parent);}else//右左双旋{RotateRL(parent);}}else{assert(false);}}

合起来

	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 (kv.first > cur->_kv.first)//插入的值比遍历的值大{parent = cur;//cur往下遍历时，父节点同时要往下走cur = cur->_right;//往右走}else if (kv.first < cur->_kv.first)//插入的值比遍历的值小{parent = cur;cur = cur->_left;//往左走}else//说明插入的值已经存在，return false{return false;}}//走到这说明已经找到可以插入的地方 //创建一个新节点cur = new Node(kv);//判断插入的节点该连接到父节点的左还是右if (cur->_kv.first > parent->_kv.first)//cur 的值大于父节点的值，连右{parent->_right = cur;}else{parent->_left = cur;}//接下来就是判断平衡因子的时候了cur->_parent = parent;//若cur是此父节点的左子树(节点)那么父节点的平衡因子-- ，是右子树(节点)那么父节点平衡因子++//一直往上走直至parent为nullptr(根节点的父节点为空)或者平衡因子为0或者平衡因子为2(需要旋转)while (parent){if (cur == parent->_left)//cur在父左 父bf--{parent->_bf--;}else//cur在父右 父bf++{parent->_bf++;}if (parent->_bf == 0)//父bf==0 break{break;}else if (parent->_bf == 1 || parent->_bf == -1)//父bf为1 or -1继续往上{cur = cur->_parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//平衡因子为2 只能旋转了//右高左低 左单旋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)//两边都高左右双旋{RotateLR(parent);}else//右左双旋{RotateRL(parent);}}else{assert(false);}}return true;}

3.2旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：左单旋、右单旋、左右双旋以及右左双旋

左单旋——新节点插入较高右子树的右侧---右右

void RotateL(Node* parent)//左单旋{//sub是parent ，subR是parent的右节点，subRL是subR的左节点Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;//父节点的右节点指向subRL//subRL可能为空节点，也就是这颗树(子树)只有sub(parent节点)、subR、以及新增节点这三个节点 如果subRL为空，就不用将其父节点指向sub了if (subRL){subRL->_parent = parent;}Node* ppnode = parent->_parent;parent->_parent = subR;//把父节点的父节点指向subR//父节点(sub)有可能是一颗树(子树)的根节点 //如果(sub)是一颗树的根节点的话 subR直接为根节点，subR的parent直接是空if (parent = _root){subR = _root;subR->_parent = nullptr;}else//sub是一颗子树的根节点 {//得看sub是其父节点的左节点还是右节点//然后subR连接sub的父节点if (parent == ppnode->_left){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}//sub和subR平衡因子置为0subR->_bf = 0;parent->_bf = 0;}

右单旋——新节点插入较高左子树的左侧---左左

//右单旋思路和左单旋差不多void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){subL = _root;subL->_parent = nullptr;}else{if (parent == ppnode->_left){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}subL->_bf = 0;parent->_bf = 0;}

左右双旋—— 新节点插入较高左子树的右侧---左右(先左单旋再右单旋)

左右两边都高单旋解决不了问题

//左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//subLR的平衡因子不同时对其它节点的平衡因子的改变也不同int bf = subLR->_bf;RotateL(parent->_left);//先走左单旋RotateR(parent);//再走右单旋if (bf == -1)//若subLR的bf为-1，则新增节点是subLR的左子树{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1)//若subLR的bf为1，则新增节点是subLR的右子树{subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == 0) //若subLR的bf为0,那么subLR其本身就是新增节点{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}

右左双旋——新节点插入较高右子树的左侧---右左(先右单旋再左单旋)

void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == -1){subRL->_bf = 0;subR->_bf = 1;parent->_bf = 0;}else if (bf == 1){subRL->_bf = 0;subR->_bf = 0;parent->_bf = -1;}else if (bf == 0){subRL->_bf = 0;subR->_bf = 0;parent->_bf = 0;}else{assert(false);}}

4.判断是否为AVL树

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1. 验证其为二叉搜索树如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

	void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_kv.first << "[" << root->_bf << "]" << endl;_Inorder(root->_right);}void Inorder(){_Inorder(_root);}

2. 验证其为平衡树每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子) 节点的平衡因子是否计算正确

	int _Height(Node* root){if (root == nullptr)return;int leftHight = Height(root->_left);int rightHight = Height(root->_right);return leftHight > rightHight ? leftHight + 1 : rightHight + 1;}int Height(){return _Height(_root);}bool _IsAVLTree(Node* root)
{if (root == nullptr){return true;}int leftHeight = Height(root->_left);int	rightHeight = Height(root->_right);if (abs(leftHeight - rightHeight) >= 2){cout << "不平衡" << endl;return false;}if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return _IsAVLTree(root->_left)&&_IsAVLTree(root->_right);
}bool IsAVLTree(){return _IsAVLTree(_root);}

如果走前序递归的话计算高度和前序递归会存在大量重复，所以还是走后序的同时求高度

后序先走左子树判断平衡返回高度；再走右子树判断平衡返回高度

bool _IsAVLTree(Node* root, int& height){if (root == nullptr){height = 0;return true;}//走个后序int leftHeight, rightHeight = 0;if (!_IsAVLTree(root->_left, leftHeight) || !_IsAVLTree(root->_right, rightHeight)){return false;}if (abs(leftHeight - rightHeight) >= 2){cout << "不平衡" << endl;return false;}if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;}bool IsAVLTree(){int height = 0;return _IsAVLTree(_root, height);}