定义 && 性质

定义

二叉搜索树虽可以缩短查找的效率，但 如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

而AVL树可以较好的解决上述问题：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

性质

AVL树是一种 自平衡二叉搜索树，严格满足以下性质：

1. 对于任何一个节点，其左子树和右子树的高度差（即平衡因子）不超过1。
2. AVL树的每个节点存储的键值大于其左子树中所有节点的键值，小于其右子树中的所有节点的键值。这也是二叉搜索树的基本性质。
3. 它的左右子树都是AVL树

实现

思路

• 核心思想是通过旋转操作保持树的平衡性
• 在 AVL 树中，每个节点都有一个平衡因子，并且平衡因子的值只能是 0，1 或 -1
• 当插入或删除节点导致某个节点的平衡因子绝对值大于 1 时，就需要通过旋转操作来调整整棵树的平衡性。

当右子树高的时候，平衡因子+1，当左子树高时，平衡因子-1
对上述的树，就需要通过旋转让其平衡

架构

• 包含两个结构体，一个用来进行节点的实现，一个用于实现 AVLTree 的各项功能

#pragma oncetemplate<class K, class V>
struct AVLTreeNode //节点
{// 成员变量 和 成员函数
};template<class K, class V>
struct AVLTree
{typedef AVLTreeNode<K, V> Node; //重命名
public:// 公有成员函数
private:// 私有成员函数
private:// 成员变量Node* _root = nullptr;
};

节点

1. 将节点的实现在结构体中，节点包含 左右子树指针、父节点指针、键值对和平衡因子。
2. AVL 树的节点需要记录其左右子树指针和父节点指针，以支持 AVL 树的旋转操作。同时还需要记录键值对，以实现对键值对信息的存储。最后，需要记录平衡因子用于判断是否需要进行旋转的操作。
3. 用一个构造函数初始化成员变量

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; //平衡因子AVLTreeNode(const pair<K, V> & kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};

AVL树

框架

• 将待实现的功能放到这里
• 成员变量为_root根节点

template<class K, class V>
struct AVLTree
{typedef AVLTreeNode<K, V> Node; //重命名
public:// 插入bool Insert(const pair<K, V>& kv){}// 中序遍历/打印void InOrder(){}//判断是否平衡bool IsBalance(){}private:// 判断是否平衡bool _IsBalance(Node* root){}// 求AVL树最大高度int Height(Node* root){}// 左单旋void RotateL(Node* parent){}// 右单旋void RotateR(Node* parent){}// 左右双旋void RotateLR(Node* parent){}// 右左双旋void RotateRL(Node* parent){}void _InOrder(Node* root){}private:// 根节点Node* _root = nullptr;
};

Insert（插入）

插入过程主要分为两个步骤：

1. 搜索树的插入过程。从根节点开始，与新插入的节点的键值比较大小，向左（小于当前节点的键值）或向右（大于当前节点的键值）递归地查找插入位置；如果要插入的节点的键值已经存在，则返回 false。
2. 插入新的节点。将新节点插入到搜索树的合适位置，并更新其父节点指针。同时，从新节点开始向上检查，计算所经过节点的平衡因子并进行适当的旋转操作以调整树的平衡。

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->_right;}else if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}// 如果要插入的节点的键值大于其父节点的键值，则将其作为右子节点；// 否则将其作为左子节点。cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent; // 记录插入节点的父节点// 控制平衡// 1、更新平衡因子while (parent){// cur在右边，则平衡因子++if (cur == parent->_right)++parent->_bf;// cur在左边，则平衡因子--else--parent->_bf;// 平衡因子 == 0，已经平衡if (parent->_bf == 0) {break;}// == 1，向上找else if (abs(parent->_bf) == 1) {parent = parent->_parent;cur = cur->_parent;}// == 2，此时parent所在子树已经不平衡了，需要旋转处理else if (abs(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){// 左右双旋RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){//右左双旋RotateRL(parent);}else{// 正常情况下不会出现该种情况，如果出现直接报错assert(false);}}else {// 正常情况下不会出现该种情况，如果出现直接报错assert(false);}}return true;}

左单旋

抽象图（思路）：

1. 根据图中思路写代码：记录右侧节点和右侧节点的左子树节点。
2. 将 subR 的左子树更改为 parent，同时将 parent 的父节点指向 subR。
3. 将 parent 的右子树更改为 subRL，并更新 subRL 的父节点为 parent。
4. 如果 parent 是根节点，则将 subR 设为新的根节点，并将 subR 的父节点设为 nullptr；否则将 subR 的父节点指向 parent 的父节点，并更新 parent 的父节点的左子树或右子树为 subR。
5. 最后，将 subR 和 parent 的平衡因子都设置为 0。

void RotateL(Node* parent){// 此时右子树的高度比左子树高2，记录右侧节点Node* subR = parent->_right;Node* subRL = subR->_left;// 目的需要将subR变为新的父节点（根节点）// 将SubRL变为parent的子节点parent->_right = subRL;if (subRL)subRL->_parent = parent;// 创建此时父节点的头节点Node* ppNode = parent->_parent;subR->_left = parent;parent->_parent = subR; //此时subR到父节点的位置// 如果本来父节点为根if (_root == parent){//将subR变为根_root = subR;subR->_parent = nullptr;}// 本来parent不为根节点else{// 将subR的_parent指向ppNodeif (ppNode->_left == parent)ppNode->_left = subR;elseppNode->_right = subR;subR->_parent = ppNode;}// 此时平衡，更新平衡因子subR->_bf = parent->_bf = 0;}

右单旋

1. 根据图片思路写代码：定义 subL 和 subLR 分别为 parent 节点的左孩子和 subL 节点的右孩子。
2. 将 subLR 节点移动到 parent 节点的位置上，即 parent 的左孩子变成 subLR，subLR 的父节点变成 parent。
3. 将 subL 节点移动到 subLR 节点的右边，subL 的右孩子变成 parent，parent 的父节点变成 subL。
4. 如果原先 parent 节点是根节点，将 subL 节点设为新的根节点并将其父节点设置为空；如果不是根节点，则将 subL 节点移动到 parent 节点原来的父节点的位置上，并更新子节点的父节点。
5. 更新 subL 和 parent 节点的平衡因子，均设为 0。

void RotateR(Node* parent){// 获取左子树和左子树的右子树Node* subL = parent->_left;Node* subLR = subL->_right;// 旋转操作：将左子树的右子树变为 parent 的左子树parent->_left = subLR;if (subLR)subLR->_parent = parent;// 将 parent 变为左子树的右子树subL->_right = parent;parent->_parent = subL;// 如果 parent 原本是根节点，则设置新的根节点为 subL，否则需要调整 parent 的父节点Node* ppNode = parent->_parent;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (ppNode->_left == parent)ppNode->_left = subL;elseppNode->_right = subL;subL->_parent = ppNode;}// 更新平衡因子：旋转后，parent 和 subL 的平衡因子都变为 0subL->_bf = parent->_bf = 0;}

左右双旋

1. 根据图片步骤写代码：定义 subL 和 subLR 分别为 parent 节点的左孩子和右孩子的左孩子。
2. 对 subL 进行一次左旋操作，此时 subL 变成了 parent 节点的父节点，subLR 成为了 subL 的右孩子。
3. 对 parent 节点进行一次右旋操作，此时 subLR 节点被转移到 parent 的位置上，并成为 parent 的父节点。同时，subLR 的右子树成为 parent 的左子树，subLR 的左子树成为 subL 的右子树。
4. 根据新树结构和子树的高度差，调整各个节点的平衡因子。其中，subLR 节点的平衡因子设为 0。如果 subLR 原来的平衡因子为 1，则 parent 的平衡因子、subL 的平衡因子和 subLR 的平衡因子分别设为 0，-1 和 0；如果 subLR 原来的平衡因子为 -1，则三者分别设为 1，0 和 0；如果 subLR 原来的平衡因子为 0，则三者均设为 0。

void RotateLR(Node* parent){// 定义subL，subLRNode* subL = parent->_left;Node* subLR = subL->_right;// 保存subLR节点的平衡因子int bf = subLR->_bf;// 左旋操作，将subLR上移到subL的位置RotateL(parent->_left);// 右旋操作，将subLR上移到parent的位置RotateR(parent);// 根据新树结构和子树高度调整各个节点平衡因子subLR->_bf = 0; // subLR的平衡因子设为0if (bf == 1) // 如果subLR原来的平衡因子为1{parent->_bf = 1;subL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subL->_bf = 1;}else if (bf == 0){parent->_bf = 0;subL->_bf = 0;}// subLR的平衡因子取值范围应该是-1，0，1三个值，如果不在这个范围内则代表程序出现了错误else{assert(false); // 断言，程序错误}}

右左双旋

1. 根据图步骤来实现代码：定义 subR 和 subRL 分别为 parent 节点的右孩子和左孩子的右孩子。
2. 对 subR 进行一次右旋操作，此时 subR 变成了 parent 节点的父节点，subRL 成为了 subR 的左孩子。
3. 对 parent 节点进行一次左旋操作，此时 subRL 节点被转移到 parent 的位置上，并成为 parent 的父节点。同时，subRL 的左子树成为 parent 的右子树，subRL 的右子树成为 subR 的左子树。
4. 根据新树结构和子树的高度差，调整各个节点的平衡因子。

void RotateRL(Node* parent){// 定义subR，subRLNode* subR = parent->_right;Node* subRL = parent->_left;// 保存subRL节点的平衡因子int bf = subRL->_bf;// 右旋操作，将subR上移到parent的位置RotateR(parent->_right);// 左旋操作，将subRL上移到parent的位置RotateL(parent);// 根据新树结构和子树高度调整各个节点平衡因子subRL->_bf = 0; // subRL的平衡因子设为0if (bf == 1) // 如果subRL原来的平衡因子为1{subR->_bf = 0; parent->_bf = -1; }else if (bf == -1) {subR->_bf = 1; parent->_bf = 0; }else if (bf == 0) {subR->_bf = 0; parent->_bf = 0;}// subRL的平衡因子取值范围应该是-1，0，1三个值，如果不在这个范围内则代表程序出现了错误else{assert(false);}}