超级详细的AVLTree – 高度平衡二叉树 – 底层代码实现
目录
- AVLTree 简介
- 1. 节点结构体定义
- 2. AVLTree 类定义及插入函数
- 3. 左旋转函数（RotateL）
- 4. 右旋转函数（RotateR）
- 5. 左右双旋转函数（RotateLR）
- 6. 右左双旋转函数（RotateRL）
- 7. 中序遍历函数（Inorder）
- 8. 计算树的高度（Height）
- 9. 判断树是否平衡（IsBalance）
- 10.总结
- 11.全部代码
提示：文末全部代码更详细，若不想看模块代码可直接划到文末。具体流程图在文中
AVLTree 简介
什么是AVL树？
AVL树（Adelson-Velsky and Landis Tree）是一种自平衡的二叉搜索树（Binary Search Tree, BST）。它通过每个节点的平衡因子（左右子树的高度差）来维护树的平衡，从而确保在最坏情况下的操作复杂度为 O(log n)。AVL树通过旋转操作来调整树的结构，使得插入和删除操作后树始终保持平衡。
二叉搜索树的平衡问题
普通的二叉搜索树在最坏情况下可能退化为一个链表，从而导致查找、插入和删除的时间复杂度退化为 O(n)。为了避免这种情况，AVL树在每次插入或删除节点后都会调整树的结构，确保左右子树的高度差不超过 1。这使得树的高度始终保持在 O(log n) 级别，确保了操作的高效性。
平衡因子
平衡因子是一个节点左右子树高度的差值，定义为：
- 平衡因子 =
左子树高度 - 右子树高度 - 平衡因子只能为 -1、0 或 1。若平衡因子超出此范围，则需要进行旋转操作来恢复平衡。
旋转操作
AVL树通过旋转操作来保持平衡。常见的旋转操作包括：
- 左旋转（Rotate Left）：当右子树高度过高时，进行左旋转。
- 右旋转（Rotate Right）：当左子树高度过高时，进行右旋转。
- 左右双旋（Rotate Left-Right）：当左子树的右子树高度过高时，先对左子树进行左旋转，再对父节点进行右旋转。
- 右左双旋（Rotate Right-Left）：当右子树的左子树高度过高时，先对右子树进行右旋转，再对父节点进行左旋转。
AVL树的优势
- 快速查找：AVL树通过保持平衡，其高度为 O(log n)，因此查找操作的时间复杂度为 O(log n)。
- 高效的插入和删除：每次插入或删除操作后，通过旋转操作调整树的平衡，插入和删除操作的时间复杂度也是 O(log n)。
- 适用于动态查找表：AVL树能够自我调整，特别适合频繁插入、删除和查找的场景。
1. 节点结构体定义
// 节点结构体模板
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; // 平衡因子 (balance factor)
// 构造函数，初始化键值对及指针
AVLTreeNode(const pair<K, V>& kv)
: _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0)
{}
};
详细解释：
- 键值对：每个节点存储一个键值对，表示树中保存的数据。
- 子节点指针：节点有左右子节点指针，用于形成树的结构。
- 父节点指针：指向该节点的父节点，在旋转操作中用于重新连接树。
- 平衡因子：表示左右子树的高度差，保持在 -1、0 和 1 之间。
2. AVLTree 类定义及插入函数
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node; // 使用别名简化AVLTreeNode类型的引用
private:
Node* _root = nullptr; // 根节点，初始化为空
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
{
return false; // 键值相同，不能插入重复的键
}
}
cur = new Node(kv); // 创建新的节点
if (parent->_kv.first < cur->_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++; // 右子树增高
}
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -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)
{
RotateLR(parent); // 左右情况，左右双旋
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent); // 右左情况，右左双旋
}
break;
}
}
return true;
}
};
详细解释：
- 插入操作：按照二叉搜索树的规则插入新节点，然后通过回溯更新平衡因子。
- 旋转操作：插入后，如果平衡因子变为2或-2，则通过旋转恢复平衡。
3. 左旋转函数（RotateL）
void RotateL(Node* parent)
{
Node* subR = parent->_right; // 定义parent的右子树
Node* subRL = subR->_left; // subR的左子树
Node* PPNode = parent->_parent; // parent的父节点
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
parent->_parent = subR;
subR->_left = parent;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
subR->_parent = PPNode;
if (PPNode->_left == parent)
{
PPNode->_left = subR;
}
else
{
PPNode->_right = subR;
}
}
parent->_bf = subR->_bf = 0;
}
详细解释：
- 旋转过程：将 `parent
节点的右子树subR提升到parent的位置，将parent降为subR` 的左子树。
4. 右旋转函数（RotateR）
void RotateR(Node* parent)
{
Node* subL = parent->_left; // 定义parent的左子树
Node* subLR = subL->_right; // subL的右子树
Node* PPNode = parent->_parent; // parent的父节点
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
parent->_parent = subL;
subL->_right = parent;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
subL->_parent = PPNode;
if (PPNode->_left == parent)
{
PPNode->_left = subL;
}
else
{
PPNode->_right = subL;
}
}
parent->_bf = subL->_bf = 0;
}
详细解释：
- 旋转过程：将
parent节点的左子树subL提升到parent的位置，将parent降为subL的右子树。
5. 左右双旋转函数（RotateLR）
注意这里的折线是指变化的节点的平衡因子呈现-+交替才会被画入折线区域。折线区域代表着双旋转。无论是左右还是右左旋转
void RotateLR(Node* parent)
{
RotateR(parent->_left); // 先对左子树进行右旋转
RotateL(parent); // 再对parent进行左旋转
}
详细解释：
- 旋转过程：首先对
parent的左子树subL进行右旋转，将subL的右子树上升。然后对parent进行左旋转。
6. 右左双旋转函数（RotateRL）
void RotateRL(Node* parent)
{
RotateL(parent->_right); // 先对右子树进行左旋转
RotateR(parent); // 再对parent进行右旋转
}
详细解释：
- 旋转过程：首先对
parent的右子树subR进行左旋转，将subR的左子树上升。然后对parent进行右旋转。
7. 中序遍历函数（Inorder）
void Inorder(Node* node)
{
if (node)
{
Inorder(node->_left); // 遍历左子树
cout << node->_kv.first << " "; // 访问当前节点
Inorder(node->_right); // 遍历右子树
}
}
详细解释：
- 遍历过程：首先递归遍历左子树，然后访问当前节点，最后递归遍历右子树。
8. 计算树的高度（Height）
int Height(Node* node)
{
if (node == nullptr)
return 0;
int leftHeight = Height(node->_left);
int rightHeight = Height(node->_right);
return max(leftHeight, rightHeight) + 1;
}
详细解释：
- 高度计算：计算左子树和右子树的高度，取较大者再加一作为当前节点的高度。
9. 判断树是否平衡（IsBalance）
bool IsBalance(Node* node)
{
if (node == nullptr)
return true;
int leftHeight = Height(node->_left);
int rightHeight = Height(node->_right);
return abs(leftHeight - rightHeight) <= 1 && IsBalance(node->_left) && IsBalance(node->_right);
}
详细解释：
- 平衡判断：检查左右子树的高度差是否在允许范围内，并递归检查左右子树是否平衡。
总结
AVL树是一种高度自平衡的二叉搜索树，通过旋转操作来维持树的平衡，确保树的高度保持在 O(log n) 级别，从而在最坏情况下也能保持查找、插入和删除操作的高效性。本文详细介绍了 AVL 树的节点结构、插入操作以及旋转操作，并提供了中序遍历、高度计算和树平衡性判断的函数实现。这些操作和算法为 AVL 树的实现提供了坚实的基础，使其能够在实际应用中表现出色。
全部代码
AVLTree.hpp
#pragma once
#include<iostream>
#include<map>
#include<assert.h>
#include<time.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;//balance factor
//构造函数
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
//上面这一堆是属于节点的不是属于树的
{}
};
//接着构建AVLTree
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
private:
Node* _root = nullptr;//缺省
//public:
//
// AVLTree():_root(nullptr){}
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)//循环到遇到空时break,可以插入
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
//走到这一步说明遇到重复数据，返回false
return false;
}
}
cur = new Node(kv);//new一个节点出来
//下面部分是插入节点到树中，不涉及平衡因子的修改
if (parent->_kv.first < cur->_kv.first)//键值对比大小只能用pair.first
{
parent->_right = cur;
cur->_parent = parent;
//parent->_bf++;
}
else
{
parent->_left = cur;
cur->_parent = parent;
//parent->_bf--;
}
//下面部分为循环的修改相关节点的平衡因子
while (parent)
{
if (cur == parent->_left)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -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)//-+左右：左右双旋。下层先做左单旋，最后上层做右单旋
{
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)//+-右左：右左双旋.下层先做右单旋，最后上层做左单旋
{
RotateRL(parent);
}
break;
}
else
{
assert(false);
}
}
return true;
};
//左单旋：在较高的右子树最右侧插入新节点.只能是最右侧
//只有当parent遇到2的时候才会有左单旋
void RotateL(Node* parent)
{
//首先定义parent右下层为subR，subR的左下层为subRL，parent父节点为ppnode
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* PPNode = parent->_parent;
//关键过程：subRL成为parent的右孩子。parent成为subR的左孩子。也就是说
//平衡因子为2的parent高了，我们要把它拉下一层，形成平衡状态
//具体操作：因为不清楚parent是否是根节点，所以要用ppnode存放。具体后面会提。
//parent的右孩子指向subRL，subRL的父节点指向parent。parent的父节点指向subR,subR的左孩子指向parent
//判断一下parent是否为根节点_root,或者parent的父节点是否为空，如果为空，subR的父节点指向空，subR成为新的根节点
//如果不为空，判断一下原来parent是ppnode的左孩子还是右孩子，然后用ppnode的左右指针指向subR，subR的父节点指向ppnode
//最后旋转完成的部分（parent+subR）的平衡因子都会变成0
parent->_right = subRL;
if(subRL)
subRL->_parent = parent;
parent->_parent = subR;
subR->_left = parent;
if (parent == _root)
{
subR->_parent = nullptr;
_root = subR;
}
else
{
subR->_parent = PPNode;
if (PPNode->_kv.first < parent->_kv.first)
{
PPNode->_right = subR;
}
else
{
PPNode->_left = subR;
}
}
parent->_bf = subR->_bf = 0;
}
// 右单旋：在较高的左子树最左侧插入新节点时需要右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* ppNode = parent->_parent;
// 关键过程：subLR成为parent的左孩子，parent成为subL的右孩子。
// 平衡因子为-2的parent高度过高，我们要把它拉下一层，恢复平衡。
// parent的左孩子指向subLR，subLR的父节点指向parent。subL的右孩子指向parent，subL成为新的父节点。
parent->_left = subLR;
//subLR->_parent = parent;
if (subLR)//如果subLR为空则其没有父节点
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
// 判断parent是否为根节点_root。如果parent是根节点，subL成为新的根节点。
// 如果parent有父节点ppNode，判断parent是ppNode的左孩子还是右孩子，并更新ppNode的指针指向subL。
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
subL->_parent = ppNode;
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
}
parent->_bf = subL->_bf = 0;
}
// 左右双旋：在较高的左子树的右侧插入新节点时，需要先对左子树(parent->_left)进行左旋，再对父节点(parent)进行右旋.最后以parent->_left->_right为根节点
void RotateLR( Node* parent)//右双旋
{
// subL是parent的左子树，subLR是subL的右子树
Node* subL = parent->_left;
Node* subLR = subL->_right;
//我们不清楚新节点插入到哪里，所以用bf来标注。 用于后续调整平衡因子
int bf = subLR->_bf;
RotateL(subL);// 左右双旋的第一步是先对subL进行左单旋
RotateR(parent);// 然后对parent进行右单旋
// 根据subLR的平衡因子调整旋转后子树的平衡因子
if (bf == -1)
{
subL->_bf = 0;
parent->_bf = 1;
subLR->_bf = 0;
}
else if (bf == 1)
{
subL->_bf = -1;
parent->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 0)
{
subL->_bf = 0;
parent->_bf = 0;
subLR->_bf = 0;
}
else
{
assert(false);
}
}
// 右左双旋：在较高的右子树的左侧插入新节点时，需要先对右子树进行右旋，再对父节点进行左旋
void RotateRL(Node* parent) // 右左双旋
{
// subR是parent的右子树，subRL是subR的左子树
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;// 用于后续调整平衡因子
RotateR(subR);// 右左双旋的第一步是先对subR进行右单旋
RotateL(parent); // 然后对parent进行左单旋
if (bf == -1) // subRL左子树新增
{
subR->_bf = 1;
parent->_bf = 0;
subRL->_bf = 0;
}
else if (bf == 1) // subRL右子树新增
{
subR->_bf = 0;
parent->_bf = -1;
subRL->_bf = 0;
}
else if (bf == 0) // subRL自己就是新增
{
subR->_bf = 0;
parent->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
//这里为什么要写2个中序遍历呢？
//AN：实例化对象不能够调用类私有的成员变量如果直接在类外写：tree.inorder（Node* root）这个会报错。
//我们只能够通过公有化接口去调用inorder函数，也就是实例化对象后外函数调内函数，内函数调私有变量。
//下面的求高度，是否平衡也是这个逻辑
void Inorder()
{
_Inorder(_root);
}
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_Inorder(root->_right);
}
//通过递归算法求二叉树的高度
int Height(Node* root)
{
if (root == nullptr)
return 0;
int lh = Height(root->_left);
int rh = Height(root->_right);
return lh > rh ? lh + 1 : rh + 1;
}
//通过递归算法求二叉树是否平衡
bool IsBalance()
{
return IsBalance(_root);
}
bool IsBalance(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
if (rightHeight - leftHeight != root->_bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
//abs求绝对值
return abs(rightHeight - leftHeight) < 2
&& IsBalance(root->_left)
&& IsBalance(root->_right);
}
};
AVLTree.cpp
#include"AVLTree.hpp"
void TestAVLTree1()
{
//3组数据建议全部测试一遍
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
AVLTree<int, int> t;
for (auto e : a)
{
t.insert(make_pair(e, e));
}
t.Inorder();
cout << t.IsBalance() << endl;
}
void TestAVLTree2()
{
srand(time(0));
const size_t N = 100000;
AVLTree<int, int> t;
for (size_t i = 0; i < N; ++i)
{
size_t x = rand();
t.insert(make_pair(x, x));
//cout << t.IsBalance() << endl;
}
//t.Inorder();
cout << t.IsBalance() << endl;
}
int main()
{
TestAVLTree1();
//TestAVLTree2();
return 0;
}