AVL树模拟实现

前言

什么叫平衡呢？

平衡因子

代码实现

基础结构

函数部分

构造部分

Insert函数

旋转情况(敲重点！！！~\(≧▽≦)/~)

1、右右情况 ——— 左单旋

左旋总步骤

拆解

为什么叫左旋呢？

代码

2、左左情况

右旋步骤

平衡因子变化：

代码

3、左右情况

情况1：subLR->_bf = 0

情况2：subLR->_bf = 1

情况3：subLR->_bf = -1

为什么叫左右双旋呢？

代码

4、右左情况

代码

Inorder中序遍历

isBalance检查是否平衡

测试代码

结语

前言

AVL树，是一种“平衡”的二叉搜索树，关于搜索树的介绍和模拟，我已经在该篇文章（二叉搜索树的模拟实现-CSDN博客）介绍过，想复习或者了解二叉搜索树的读者可以去看看哦

♪(´▽｀)

什么叫平衡呢？

AVL树在二叉搜索树的基础上，进行了平衡调整，也就是每插入一个数，就会检查是否有两棵子树的高度差超过1，若超过，就将“旋转”调整至平衡，这是为了解决二叉树在数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下的问题

而AVL树的最重要的部分，也就是调整平衡啦❀ヾ(≧▽≦*)o，平衡因子是可以用来检测是否平衡的哦，我的模拟实现也是用这种方法哦~(￣▽￣)~***

平衡因子

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

当平衡因子的绝对值大于1时，就出现了“不平衡”现象，就要分情况来进行旋转调整啦~

知道了上面这些，相信你对AVL树有了基本了解啦，现在让我们开始吧( ‵▽′)ψ

代码实现

基础结构

AVL树与普通树的节点的不同

① 它的每个节点除了有左右孩子的指针，还有父母的指针

② 存的数据是键值对，也就是key-value结构，我在二叉搜索树的模拟实现-CSDN博客中介绍过

key结构：
通常用来用于：

                查找某值是否存在
现实使用场景：
          门禁系统

key、value结构
通常用于：
        1、确定一个值是否存在
          2、通过key查找value
现实使用场景：
          字典

以下就是该部分的代码啦

template<typename K, typename V>// 类模板
struct AVLTreeNode// 类外也要使用，所以定义为struct
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;/**/pair<K, V>_kv;/*键值对*/int _bf;// 平衡因子（右子树高度 - 左子树高度）// 构造函数AVLTreeNode(const pair<K, V>& kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};

函数部分

构造部分

template<typename K, typename V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;// typedef后，方便使用
private:Node* _root = nullptr;// 初始化
};

Insert函数

	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->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}elsereturn false;}// 插入元素cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}// 调整平衡因子while (parent){// 插入在右子树，平衡因子++if (cur == parent->_left){parent->_bf--;}else// 插入在左子树，平衡因子--{parent->_bf++;}// 平衡因子 = 0，说明并未破坏平衡，不用再向上调整平衡因子if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){// 继续向上检查是否平衡cur = parent;parent = cur->_parent;}else{// 旋转}}return true;}

旋转情况(敲重点！！！~\(≧▽≦)/~)

1、右右情况

2、左左情况

3、左右情况

4、右左情况

1、右右情况 ——— 左单旋

右右情况

① 对于不平衡节点（该处是1）来说，插入元素在其右子树

② 对于不平衡节点的右孩子（这里是2）来说，插入节点也在其右子树

这种情况我们需要左旋

左旋总步骤

拆解

① 将不平衡节点(root)的右孩子（subR）的左孩子(subRL) 给不平衡节点的右孩子

② 不平衡节点(root)做 subR的左孩子

最后各点的平衡因子如下

为什么叫左旋呢？

是不是很像向左旋转了一下呢 q(≧▽≦q)

代码

	// 左单旋void RotateL(Node* root){Node* subR = root->_right;Node* subRL = subR->_left;/*可能为空*/// 更新root的右孩子root->_right = subRL;// 更新父亲// 注意subRL可能为空的情况if (subRL){subRL->_parent = root;}subR->_parent = root->_parent;root->_parent = subR;// 更新subR的左孩子subR->_left = root;        // 注意root为整棵树的根时的情况if (root == _root)_root = subR;// 将 原本指向root的父节点 改为 指向subRif (subR->_parent){if (root == subR->_parent->_left){subR->_parent->_left = subR;}elsesubR->_parent->_right = subR;}// 最后平衡因子都变为0subR->_bf = root->_bf = 0;}

2、左左情况

和右右情况相反

1、插入元素在不平衡节点(root)的左子树（subL）

2、在不平衡节点(root)的左子树(subL)的左子树

右旋步骤

右旋

1、subL的右孩子subLR做root的左孩子

2、root做subL的右孩子

为什么叫右旋？

是不是向右旋转了呢(´▽`ʃ♡ƪ)

平衡因子变化：

root ： -2 -----> 0

subL：-1 ------> 0

subRL :不变

代码

	// 右单旋// 与左单旋代码类似void RotateR(Node* root){Node* subL = root->_left;Node* subLR = subL->_right;/*可能为空*/root->_left = subLR;if (subLR){subLR->_parent = root;}subL->_right = root;subL->_parent = root->_parent;root->_parent = subL;if (root == _root)_root = subL;if (subL->_parent){if (root == subL->_parent->_left){subL->_parent->_left = subL;}elsesubL->_parent->_right = subL;}subL->_bf = root->_bf = 0;}

3、左右情况

情况1：subLR->_bf = 0

平衡因子变化：

root: -2 -> 0

subL: 1 -> 0

subLR: 0不变

情况2：subLR->_bf = 1

平衡因子变化：

root: -2 -> 0

subL: 1不变

subLR: 1 -> 0

情况3：subLR->_bf = -1

为什么叫左右双旋呢？

无论是上面三种哪种情况，都是先左单旋（subL），再右单旋(root)

代码

// 左右双旋void RotateLR(Node* root){/*其实就是将根节点的左子树左旋，根节点再右旋*/Node* subL = root->_left;Node* subLR = subL->_right;// 记录subLR的平衡因子，方便后续分情况来更改subLR,subL,root的平衡因子int bf = subLR->_bf;// 左子树先左旋，根再右旋RotateL(root->_left);RotateR(root);if (bf == 0){// subLR就是新增root->_bf = subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1){// 在subLR的右边新增subL->_bf = -1;root->_bf = subLR->_bf = 0;}else if (bf == -1){// 在subRL的左边新增root->_bf = 1;subLR->_bf = subL->_bf = 0;}}

4、右左情况

与左右情况极其类似

① 先对右子树右单旋

② 再对根节点左单旋

大家可以自己画画图哦，看一下自己理解的怎么样哦(●ˇ∀ˇ●)

代码

// 右左双旋
void RotateRL(Node* root)
{/*其实就是将根节点的右子树右旋，根节点再左旋*/Node* subR = root->_right;Node* subRL = subR->_left;int bf = subRL->_bf;// 子树先右旋，根再左旋RotateR(root->_right);RotateL(root);if (bf == 0){// subRL就是新增root->_bf = subR->_bf = 0;subRL->_bf = 0;}else if (bf == 1){// 在subRL的右边新增root->_bf = -1;subR->_bf = subRL->_bf = 0;}else if (bf == -1){// 在subRL的左边新增subR->_bf = 1;subRL->_bf = root->_bf = 0;}
}

Inorder中序遍历

与二叉搜索树的地方一样哦

	void InOrder(){_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);}

isBalance检查是否平衡

检查平衡要有三个要求：

1、根节点的平衡因子 = 右子树高度 - 左子树高度

2、两子树高度差的绝对值 < 2

3、所有子树都满足以上要求

	bool isBalance(){/*这种对外接口内部调用另一函数的原因，我在开头提到的那篇博客讲过这样子写就可以不需要外部调用时还要知道AVL树的根了，直接调用就好*/// 检验该树是否平衡return _isBalance(_root);}bool _isBalance(Node* root){if (root == nullptr)return true;// 获取左右子树高度int leftHeight = getHeight(root->_left);int rightHeight = getHeight(root->_right);// 看根节点的平衡因子是否合理if (root->_bf != rightHeight - leftHeight){cout << "_bf错误" << endl;return false;}// 看高度差的绝对值是否小于2return abs(rightHeight - leftHeight) < 2// 继续检查子树是否合理&& _isBalance(root->_left)&& _isBalance(root->_right);}int getHeight(Node* root){if (root == nullptr)return 0;int leftHeight = getHeight(root->_left);int rightHeight = getHeight(root->_right);// 根节点高度 = 左右子树较高者的高度 + 1return max(leftHeight, rightHeight) + 1;}

测试代码

以下测试代码可以帮你测试是否所有情况你的代码都能正确解决

void test1()
{// int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };// 右左双旋int a[] = {10, 3, 7 };// 左右双旋AVLTree<int, int> t;for (auto e : a){t.Insert({e, e});}t.InOrder();if (!t.isBalance())cout << "该树不平衡" << endl;
}void test2()
{// 随机数据测试const int N = 30;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand());// cout << v.back() << endl;}AVLTree<int, int> t;for (auto e : v){if (e == 14604){int x = 0;}t.Insert(make_pair(e, e));if (!t.isBalance())cout << "该树不平衡" << endl;}
}