AVLTree模拟实现
- 1 前言
- 2 AVL树的插入
- 2.1 平衡因子不继续向上更新的情况
- 2.2 平衡因子变为2或者-2,发生旋转
- 2.2.1 左单旋
- 2.2.2 右单旋
- 2.2.3 左右双旋
- 2.2.4 右左双旋
- 3 代码
1 前言
二叉搜索树的不足:如果出现极端情况,效率会变得很低。
AVL:二叉平衡搜索树
平衡因子:右子树的高度 - 左子树的高度 平衡因子绝对值不超过1(-1, 0, 1)
1.平衡因子为什么不是0?而是 -1, 0 ,1??
做不到,两个节点的时候不能相等,四个节点也做不到
AVL树的效率:
增删查改:高度次 O(log N)
满二叉树:2^h - 1 = N
AVL树:2^h - x = N
x的范围:[1, 2^(h - 1) - 1]
2 AVL树的插入
2.1 平衡因子不继续向上更新的情况
插入的原则:
新增在左:parent的平衡因子–
新增在右:parent的平衡因子++
从这里可以看出,当平衡因子的值为 -1 或者 1 的时候,并不会停止向上更新。
只有当平衡因子更新为0的时候,才不会继续往上更新了。
2.2 平衡因子变为2或者-2,发生旋转
当平衡因子的值更新为 -2或者2的时候,就代表这棵树不平衡了,就需要进行旋转。这时候更新也停止了(因为要进行旋转了)
2.什么情况要继续往上更新?(更新结束的条件)
更新后的parent平衡因子==0,说明parent所在的子树的高度不变,不会再影响祖先,不用再继续往上更新
更新后的parent平衡因子 ==1 或者 -1,说明parent所在的子树的高度发生改变,会影响祖先,要继续往上更新
更新后的parent平衡因子 ==2 或者 -2,说明parent所在的子树的高度发生改变且不平衡,想办法调整平衡(对parent所在子树进行旋转,让他平衡)
更新到根节点 --> 更新结束
2.2.1 左单旋
发生左单旋的情况:(具体图,某一种情况)
发生左单旋的抽象图(有很多种情况):
什么情况会发生左单旋?
在右边高的情况下往右边插入。
转化成代码就是:在插入之后,
parent->_bf = 2 && cur->_bf = 1
.这里parent->_bf = 2
说明是右边高,如果parent->_bf = -2
,说明是左边高。
总结:
cur->left 比 parent大,所以,cur->left做parent的右没有问题
cur->left比cur小,所以,cur->left做cur的左没有问题
核心操作:
parent->right = cur->left
cur->left = parent;
2.2.2 右单旋
发生右单旋的情况(具体图):
发生右单旋的抽象图(有很多种情况):
旋转:
右边高 --> 往左边旋转
左边高 --> 往右边旋转
旋转的时候要注意的问题:
- 保持他是搜索树
- 变成平衡树且降低这个子树的高度
2.2.3 左右双旋
左右双旋的情况:
当父节点左边高并且当前节点的右边高时,就会发生左右双旋。
双旋平衡因子的更新:
区分的关键,看插入节点的父节点的平衡因子
平衡因子的三种情况:h == 0, h > 0。h > 0又分为两种情况:插入节点是父节点的左子树或者插入节点是父节点的右子树
2.2.4 右左双旋
右左双旋:
当父节点的右边高并且当前节点的左边高时,就会发生右左双旋
如何分清是单旋还是双旋?
单旋:单纯的一边高,左边高或者右边高
双旋:有折现的产生。
3 代码
AVLTree.h
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;template <class K, class V>
struct AVLTreeNode
{pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;//new一个AVLTreeNode节点的时候就会调用这个构造函数// 如果传入参数,就是kvAVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template <class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public: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{assert("插入相同的节点");}}//走到这里,找到了要插入的位置 --> 将cur插入进去cur = new Node(kv);if (cur->_kv.first < parent->_kv.first)parent->_left = cur;elseparent->_right = cur;//因为是三叉链,所以cur的_parent指针还要指回去cur->_parent = parent;//走到这里,插入完成了。需要检查平衡因子,判断是否平衡,不平衡要进行旋转while (parent){//插入的位置是左孩子,bf--;插入的位置是右孩子,bf++if (cur == parent->_left)parent->_bf--;elseparent->_bf++;//接下来要判断根据不同的平衡因子进行不同的更新的情况if (parent->_bf == 0){break; //如果是0, 就不用更新了}else if (parent->_bf == -1 || parent->_bf == 1) //如果插入之后parent的平衡因子等于-1或者1,说明还要向上调整{cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -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){//父节点右边高,当前节点左边高 --> 右左双旋RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){//父节点左边高,当前节点右边高 --> 左右双旋RotateLR(parent);}else{assert("平衡因子出错");}break;}else{assert("平衡因子出错");}}return true;}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;//1.把curleft给parent的right --> parent的_right指向curleftparent->_right = curleft;//判断curleft是否为空,如果不为空,就curleft的父节点指回去if (curleft){curleft->_parent = parent;}//2.parent的right给cur的left --> cur的_left指向parentcur->_left = parent;//3.判断parent是不是当前的根节点,如果是,cur的_parent就为空。如果不是,cur的_parent还要指向ppnodeNode* ppnode = parent->_parent;//4.parent还要往回指,因为是三叉链parent->_parent = cur;if (parent == _root) //如果是根节点{_root = cur;cur->_parent = nullptr;}else{//如果不是根节点,就要判断是ppnode的左孩子还是右孩子if (ppnode->_left == parent)ppnode->_left = cur;elseppnode->_right = cur;//往回指cur->_parent = ppnode;}//更新平衡因子parent->_bf = cur->_bf = 0;}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;//1.让parent的左指向cur的右parent->_left = curright;if (curright){//第一次往回指curright->_parent = parent;}//找到parent的父节点Node* ppnode = parent->_parent;//2.cur的右指向parentcur->_right = parent;//第二次往回指parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{parent->_parent = cur;if (ppnode->_left == parent)ppnode->_left = cur;elseppnode->_right = cur;//第三次往回指cur->_parent = ppnode;}//更新平衡因子cur->_bf = parent->_bf = 0;}//左右双旋void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(cur);RotateR(parent);//根据不同的情况修改平衡因子if (bf == 0){cur->_bf = 0;parent->_bf = 0;curright->_bf = 0;}else if (bf == 1) //说明左边低,右边高{parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}else{assert("RotateLR false");}}void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf; //提前保存下来RotateR(cur);RotateL(parent);if (bf == 0){cur->_bf = 0;parent->_bf = 0;curleft->_bf = 0;}else if (bf == 1) //说明插入的位置是curleft的右边{parent->_bf = -1;cur->_bf = 0;curleft->_bf = 0;}else if (bf == -1) //插入的位置是curleft的左边{parent->_bf = 0;cur->_bf = 1;curleft->_bf = 0;}else{assert("RotateRL false");}}//bool Erase(const pair<K, V>& key)//{//}int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;int leftHight = Height(root->_left);int rightHight = Height(root->_right);if (rightHight - leftHight != root->_bf){cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;return false;}return abs(rightHight - leftHight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}void Inorder(){_Inorder(_root);}private:void _Inorder(Node* cur){if (cur == nullptr)return;_Inorder(cur->_left);cout << cur->_kv.first << " : " << cur->_kv.second << " : " << cur->_bf << endl;_Inorder(cur->_right);}
private:Node* _root = nullptr;
};
Test_AVLTree.cpp
#include "AVLTree.h"void testAVL1()
{int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.IsBalance();t.Inorder();
}int main()
{testAVL1();return 0;
}