【数据结构】AVL树
·
目录
1. 基本定义
AVL 树（Adelson-Velsky and Landis Tree）是最早被发明的自平衡二叉搜索树，由苏联数学家 G.M. Adelson-Velsky 和 E.M. Landis 于 1962 年提出。
由于普通二叉搜索树在最坏情况下（如顺序插入）会退化为链表，导致查找、插入删除操作的时间复杂度会从O（log n）退化为O（n）。AVL树通过严格控制树高，确保所有操作的时间复杂度稳定在O（log n）。
2. 核心特性
- 是二叉搜索树 (BST)，满足 BST 性质：左子树所有节点值 < 根节点值 < 右子树所有节点值。
- 严格平衡条件：每个节点的左右子树高度差 (平衡因子) 的绝对值不超过 1（即平衡因子只能为 - 1、0 或 1）。
- 左右子树本身也必须是 AVL 树。
平衡因子 (BF) = 节点右子树高度 - 节点左子树高度
3. AVL树节点的定义
在二叉搜索树的基础上，新增两个关键字段：
- 平衡因子（_bf）：直接存储当前节点的平衡状态，无需动态计算，取值范围为-1, 0 ,1（平衡状态），若为+2/-1则表示节点失衡，需触发旋转操作。
- 父节点指针（parent）：用于插入或删除节点后，从该节点向上回溯祖先节点，逐个检查并更新它们的平衡因子。
定义AVL树节点（key/value 模型的AVL树）
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) //新节点为叶子，平衡因子初始为0
{}
};关于pair的使用
在C++中，std::pair是标准模版库（STL）提供的一个轻量级模版类，用于存储一对关联的数据（两个元素），它的核心作用是将两个值“捆绑”成一个单一的对象，方便在函数返回、容器存储等场景中使用。
std::pair定义在<utility>头文件中，其模版声明如下：
template <class T1, class T2>
struct pair {
T1 first; // 第一个元素
T2 second; // 第二个元素
// 构造函数等成员（编译器自动生成）
};pair的使用
int main()
{
// 初始化一个 (int, string) 类型的pair
pair<int, string> p1(10, "hello"); //直接构造
// 自动推导为 pair<int, string>
auto p2 = make_pair(10, "world"); //make_pair是一个辅助函数，可自动推导类型，简化初始化
pair<string, int> p3{ "age", 25 }; //列表初始化（C++11）
pair<int, int> p4(1, 2);
p4.first = 100; // 访问并修改第一个元素
p4.second = 200; // 访问并修改第二个元素
// 此时p4为 (100, 200)
pair<int, int> p5;
p5 = p4; // 整体赋值，p5 变为 (100, 200)
//std::pair重载了常见的比较运算符（==、!=、<、>、<=、>=），比较规则为字典序：
//1. 先比较first元素，若不相等，则结果由first决定;
//2. 若first相等，再比较second元素;
if (p1 < p2) //true（first相等，second "hello" < "world"）
{
cout << "p1 < p2" << endl;
}
if (p4 < p5)//false
{
cout << "p4 < p5" << endl;
}
if (p4 == p5)//true
{
cout << "p4 = p5" << endl;
}
return 0;
}4. 自平衡机制（旋转操作）
4.1 左单旋（LeftRotate）
左旋解决了右子树过高导致的失衡问题。它通过调整节点间的父子关系，降低右子树高度，使树重新满足平衡条件（所有节点的平衡因子绝对值≤1）。
左旋的本质是将失衡节点的右子节点“提升”为新根节点，原失衡节点成为新父节点的左子节点，同时新父节点原来的左子树成为原失衡节点的右子树。
插入操作左旋的触发条件：
- 该节点的平衡因子为2（失衡节点）。
- 该节点右孩子的平衡因子为1。
//左单旋
void LeftRotate(Node* parent)
{
Node* subR = parent->_right; //失衡节点的右孩子(9)
Node* subRL = subR->_left; //失衡节点的右孩子的左孩子(6)
parent->_right = subRL; //6成为5的右子树
if (subRL)//判断subRL是否为空，防止对空指针解引用，6有可能不存在
subRL->_parent = parent;//更改6的父指针为5
Node* parentparent = parent->_parent;//5可能还有父亲节点，记录5的父节点
subR->_left = parent; //5成为9的左子树
parent->_parent = subR;//更改5的父指针
if (parentparent == nullptr)//如果5没有父节点，那么9直接成为新根，再将9的父指针置空
{
_root = subR;
subR->_parent = nullptr;
}
else //如果5存在父节点
{
if (parentparent->_left == parent) //5原来是pp的左子节点
{
parentparent->_left = subR;
}
else
{
parentparent->_right = subR; //5原来是pp的右子节点
}
subR->_parent = parentparent; //更新9的父指针
}
//更新平衡因子，旋转后5和9的平衡因子均变为0
parent->_bf = 0;
subR->_bf = 0;
}4.2 右单旋（RightRotate）
右旋用于解决左子树过高导致的失衡问题。通过调整节点间的父子关系，降低左子树高度，使树重新满足平衡条件（所有节点的平衡因子绝对值≤1）。
右旋的本质是将失衡节点的左子节点 “提升” 为新的父节点，原失衡节点则成为新父节点的右子节点，同时新父节点原来的右子树将作为原失衡节点的左子树。
插入操作右旋的触发条件：
- 该节点的平衡因子为-2（失衡节点）。
- 该节点左孩子的平衡因子为-1。
//右单旋
void RightRotate(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == parentparent->_left)
{
parentparent->_left = subL;
}
else
{
parentparent->_right = subL;
}
subL->_parent = parentparent;
}
//更新平衡因子
subL->_bf = 0;
parent->_bf = 0;
}4.3 左右双旋（LRRotate）
左右双旋是一种复合旋转操作，用于处理左子树的右子树过高导致的特殊失衡场景。当单旋（右旋）无法直接修复失衡时，需通过 “先左旋、后右旋” 的组合操作，使树恢复平衡。
左右双旋的触发条件：
- 该节点的平衡因子为-2（失衡节点）。
- 失衡节点的左孩子平衡因子为1。
左右双旋通过两步旋转将失衡调整为平衡状态：
- 第一步：对失衡节点的左子节点进行左旋，将“左—右”偏斜修正为“左—左”偏斜（即一边高）；
- 第二步：对原失衡节点执行右旋，修复“左—左”偏斜导致的失衡。
情况1中由于对失衡节点的左孩子左旋操作将节点5和节点8的平衡因子都更新为0，对失衡节点右旋操作将节点10和节点8的平衡因子更新为0，通过图示我们发现，计算出节点10的平衡因子并不为0，而是1，所以parent节点需要单独处理一下，对于情况2需要单独处理subL节点，情况3不需要单独处理，不过为了保险起见，可以在左右双旋代码中再次更新一边平衡因子。
//左右双旋
void LRRotate(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;//记录subLR的平衡因子，然后分三种情况讨论
LeftRotate(parent->_left);//左旋操作
RightRotate(parent);//右旋操作
//更新平衡因子
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1; //需要单独处理parent节点的平衡因子
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1; //需要单独处理subL节点的平衡因子
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false); //防御式编程
}
}4.4 右左双旋（RLRotate）
右左双旋复合旋转操作，用于处理右子树的左子树过高导致的特殊失衡场景。当单旋（左旋）无法直接修复失衡时，需通过 “先右旋、后左旋” 的组合操作，使树恢复平衡。
右左双旋的触发条件：
- 该节点的平衡因子为2（失衡节点）。
- 失衡节点的右孩子平衡因子为-1。
右左双旋通过两步旋转将失衡调整为平衡状态：
- 第一步：对失衡节点的右子节点进行右旋，将“右—左”偏斜修正为“右—右”偏斜（即一边高）；
- 第二步：对原失衡节点执行左旋，修复“右—右”偏斜导致的失衡。
情况1中由于对失衡节点的右孩子右旋操作将节点9和节点6的平衡因子都更新为0，对失衡节点左旋操作将节点4和节点6的平衡因子更新为0，通过图示我们发现，计算出节点9的平衡因子并不为0，而是1，所以subR节点需要单独处理一下，对于情况2需要单独处理parent节点，情况3不需要单独处理，不过为了保险起见，可以在左右双旋代码中再次更新一边平衡因子。
//右左双旋
void RLRotate(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf; //记录subRL的平衡因子，然后分三种情况讨论
RightRotate(parent->_right);//右旋操作
LeftRotate(parent);//左旋操作
//更新平衡因子
if (bf == -1)
{
subRL->_bf = 0;
subR->_bf = 1; //需要单独处理subR节点的平衡因子
parent->_bf = 0;
}
else if (bf == 1)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1; //需要单独处理parent节点的平衡因子
}
else if (bf == 0)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}5. 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 (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 < kv.first)
{
parent->_right = cur;
}
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)
{
RightRotate(parent); //右旋
}
else if (parent->_bf == 2 && cur->_bf == 1)
{
LeftRotate(parent); //左旋
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
LRRotate(parent); //左右双旋
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RLRotate(parent); //右左双旋
}
else
{
assert(false);
}
break;
}
else
{
assert(false);
}
}
return true;
}6. AVL树的删除（了解）
AVL树的插入操作最多只需一次失衡调整即可恢复整体平衡，而删除操作与插入操作不同的是，删除操作可能引发连锁的失衡传播，可能不止调整一次失衡，删除节点后需要依次对每个祖先节点进行检查。
7. AVL树的查找
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_kv.first)
cur = cur->_right;
else if (key < cur->_kv.first)
cur = cur->_left;
else
return cur;
}
return nullptr;
}8. 获取树的高度
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;
}9. AVL树的验证
AVL 树的验证是确保其同时满足二叉搜索树（BST）性质和AVL 平衡条件的过程。只有同时满足这两个条件，才能称为合法的 AVL 树。
9.1 BST 性质验证
中序遍历有序
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}9.2 AVL 平衡条件验证
bool _IsBalanceTree(Node* root)
{
if (root == nullptr)
return true;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = rightHeight - leftHeight;
if (abs(diff) >= 2)
{
cout << root->_kv.first << "高度差异常" << endl;
return false;
}
if (root->_bf != diff)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}优化方案：在一次递归中同时计算高度和检查平衡，通过返回值（如pair<bool,int>）同时携带 “是否平衡” 和 “子树高度”，避免重复计算。优化后时间复杂度可降为 O(n)，示例如下：
// 返回值：first为是否平衡，second为子树高度
pair<bool, int> _IsBalanceTreeOptimized(Node* root)
{
if (root == nullptr)
{
return {true, 0}; // 空树：平衡，高度0
}
// 递归检查左子树
auto leftRes = _IsBalanceTreeOptimized(root->_left);
if (!leftRes.first) return {false, 0}; // 左子树失衡，直接返回
// 递归检查右子树
auto rightRes = _IsBalanceTreeOptimized(root->_right);
if (!rightRes.first) return {false, 0}; // 右子树失衡，直接返回
// 计算实际平衡因子
int diff = rightRes.second - leftRes.first;
// 检查结构平衡
if (abs(diff) >= 2)
{
cout << root->_kv.first << "高度差异常" << endl;
return {false, 0};
}
// 检查平衡因子一致性
if (root->_bf != diff)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return {false, 0};
}
// 返回当前子树高度（1 + 左右子树最大高度）
return {true, 1 + max(leftRes.second, rightRes.second)};
}10. 总结
总结：AVL 树是一种自平衡二叉搜索树，通过控制树高在 log₂n 级别，使查找、插入、删除操作的时间复杂度稳定在 O (log n)。
AVL树的实现（删除操作这里不做研究）
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) // 新节点为叶子，平衡因子初始为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
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
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)
{
RightRotate(parent); //右旋
}
else if (parent->_bf == 2 && cur->_bf == 1)
{
LeftRotate(parent); //左旋
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
LRRotate(parent); //左右双旋
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RLRotate(parent); //右左双旋
}
else
{
assert(false);
}
break;
}
else
{
assert(false);
}
}
return true;
}
//右单旋
void RightRotate(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == parentparent->_left)
{
parentparent->_left = subL;
}
else
{
parentparent->_right = subL;
}
subL->_parent = parentparent;
}
//更新平衡因子
subL->_bf = 0;
parent->_bf = 0;
}
//左单旋
void LeftRotate(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* parentparent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parentparent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentparent->_left == parent)
{
parentparent->_left = subR;
}
else
{
parentparent->_right = subR;
}
subR->_parent = parentparent;
}
//更新平衡因子
parent->_bf = 0;
subR->_bf = 0;
}
//左右双旋
void LRRotate(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;//记录subLR的平衡因子，然后分三种情况讨论
LeftRotate(parent->_left);//左旋操作
RightRotate(parent);//右旋操作
//更新平衡因子
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1; //需要单独处理parent节点的平衡因子
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1; //需要单独处理subL节点的平衡因子
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false); //防御式编程
}
}
//右左双旋
void RLRotate(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf; //记录subRL的平衡因子，然后分三种情况讨论
RightRotate(parent->_right);//右旋操作
LeftRotate(parent);//左旋操作
//更新平衡因子
if (bf == -1)
{
subRL->_bf = 0;
subR->_bf = 1; //需要单独处理subR节点的平衡因子
parent->_bf = 0;
}
else if (bf == 1)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1; //需要单独处理parent节点的平衡因子
}
else if (bf == 0)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
//AVL树平衡检测
bool IsBalanceTree()
{
return _IsBalanceTree(_root);
}
//求树的高度
int Height()
{
return _Height(_root);
}
size_t Size()
{
return _Size(_root);
}
//查找
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_kv.first)
cur = cur->_right;
else if (key < cur->_kv.first)
cur = cur->_left;
else
return cur;
}
return nullptr;
}
private:
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 leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool _IsBalanceTree(Node* root)
{
if (root == nullptr)
return true;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = rightHeight - leftHeight;
if (abs(diff) >= 2)
{
cout << root->_kv.first << "高度差异常" << endl;
return false;
}
if (root->_bf != diff)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
size_t _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
private:
Node* _root = nullptr;
};
更多推荐
26
0- 0
已为社区贡献1条内容
所有评论(0)