C++进阶——AVL树的实现

1、AVL的概念

1.1 AVL 树的发明

AVL 树由 G.M. Adelson-Velsky 和 E.M. Landis 在 1962 年的论文《An algorithm for the organization of information》中提出。他们的设计目标是解决二叉搜索树在动态操作（插入、删除）中可能退化为链表的问题。

1.2 AVL 树的定义

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

• 它是一棵空树，或者：

  • 它的左右子树都是 AVL 树。

  • 左右子树的高度差(平衡因子)的绝对值 <= 1。

1.3 平衡因子

平衡因子（Balance Factor）是 AVL 树的核心概念：

• 定义：某个节点的平衡因子 = 右子树的高度 - 左子树的高度。

• 平衡因子的取值范围：-1、0、1。

• 如果某个节点的平衡因子的绝对值超过 1，则该节点不平衡，需要通过旋转操作进行调整。

1.4 为什么高度差 <= 1 ？

高度差为 0 表示左右子树的高度相等，这种理想状态在某些情况下是无法实现的。

• 例如：

  • 当树的节点数为 2 时，高度差只能为 1。

  • 当树的节点数为 4 时，高度差也只能为 1。

• 如果强制要求高度差为 0，会导致树的结构过于严格，难以在动态操作中保持平衡。

1. 5 AVL 树的性能

AVL 树的性能优势主要体现在其高度平衡性：

• 高度控制：AVL 树的高度 始终保持在 O(log⁡N)。

• 操作效率：插入、删除、查找等操作的时间复杂度均为 O(log⁡N)。

2、AVL树的实现

2.1 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 factorAVLTreeNode(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:// ……private:Node* _root = nullptr;}

2.2 AVL树的插入

2.2.1 AVL树插入一个值的大概过程

1. 按二叉搜索树规则进行插入一个值。

2. 新增结点，只会影响祖先(或部分祖先)结点的高度，也就是会影响祖先(或部分祖先)结点的平衡因子，所以更新 从新增结点->根结点路径上的平衡因子。实际中最坏情况下要更新到根，有些情况更新到中间就可以结束了。

3. 更新平衡因子过程中出现不平衡(平衡因子的绝对值超过 1)，对不平衡子树 旋转，旋转后本质调平衡的同时，降低了子树的高度，不会再影响上一层，所以插入结束。

2.2.2 平衡因子的更新

更新原则：

1. 平衡因子的定义

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

2. 影响平衡因子的条件

只有子树高度变化 才会影响当前节点的平衡因子。

3. 插入节点对平衡因子的影响

• 如果新增节点在parent的右子树，parent的平衡因子++。

• 如果新增节点在parent的左子树，parent的平衡因子--。

更新情况：

1. 更新后parent的平衡因子 等于 0

因为插入前，就是平衡搜索树，平衡因子只能是-1，0，1，所以一定是从-1或1变成0，子树整体的

高度不变，结束更新。

2. 更新后parent的平衡因子 等于 1 或 -1

一定是从0变成-1或1，子树整体的高度变化，继续更新。

3. 更新后parent的平衡因子等于 2 或 -2

一定是从-1变成-2或1变成2，parent高的子树更高了，不平衡了。

通过旋转，平衡(即降低树的高度)，并使子树的根的平衡因子为0。

即-1->-2(旋转)->0，或1->2(旋转)->0，相当于子树的高度没变，结束更新。

4. 更新到根节点

如果更新到根节点，且根节点的平衡因子为 1 或 -1，结束更新。因为根的parent为nullptr，不用更

新了。

2.2.3 插入的代码实现

		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 (kv.first > parent->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 更新平衡因子while (parent) // parent = nullptr,为根节点的父亲,结束更新{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 = cur->_parent;}else if (parent->_bf == -2 || parent->_bf == 2){// 旋转break;}else{assert(false);}}return true;}

2.3 旋转

2.3.1 旋转的原则

1. 保持搜索树的规则。

2. 让旋转的树从不平衡变平衡，其次降低旋转树的高度。

旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。

2.3.2 右单旋

即左侧高，右侧的parent旋下来。平衡因子同号。

a,b,c子树为抽象表示，实际上有非常多种情况。

a子树自己不旋转，高度+1，将subLR给parent的左，再将parent给subL的右。

注意：

当h = 0时，subLR为nullptr。

parent如果是局部子树的根，就改变连接关系，如果是根，就改变根。

2.3.3 右单旋的代码实现

		void RotateR(Node* parent){Node* pParent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;subL->_parent = pParent;if (pParent == nullptr) // 当pParent == nullptr时,_root == parent{_root = subL;}else{if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;}subL->_bf = 0;parent->_bf = 0;}

2.3.4 左单旋

即右侧高，左侧的parent旋下来。平衡因子同号。

a子树自己不旋转，高度+1，将subRL给parent的右，再将parent给subR的左。

注意：

当h = 0时，subRL为nullptr。

parent如果是局部子树的根，就改变连接关系，如果是根，就改变根。

2.3.5 左单旋的代码实现

		void RotateL(Node* parent){Node* pParent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;subR->_parent = pParent;if (pParent == nullptr)_root = subR;else{if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;}subR->_bf = 0;parent->_bf = 0;}

2.3.6 左右双旋

即中间高，右侧的parent旋下来。平衡因子异号。

从过程上，是对subL进行左旋，parent进行右旋。

从结果上，subLR的左给subL的右，subLR的右给parent的左，subLR自己做根。

subLR的左为subL，右为parent。

平衡后分三种情况，即有三种情况的平衡因子。

2.3.7 左右双旋的代码实现

		void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int _bf = subLR->_bf;RotateL(subL);RotateR(parent);if (_bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (_bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (_bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}

2.3.8 右左双旋

即中间高，左侧的parent旋下来。平衡因子异号。

从过程上，是对subR进行右旋，parent进行左旋。

从结果上，subRL的左给parent的右，subRL的右给subR的左，subRL自己做根。

subRL的左为parent，右为subR。

平衡后分三种情况，即有三种情况的平衡因子。

2.3.9 右左双旋的代码实现

		void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int _bf = subRL->_bf;RotateR(subR);RotateL(parent);if (_bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else if (_bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (_bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else{assert(false);}}

2.4 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;elsereturn cur;}return nullptr;}

2.5 AVL树的平衡检测

		bool _IsBalanceTree(Node* root, int& height) { // 后序// 空树是 AVL 树if (nullptr == root) {height = 0;return true;}// 递归检查左子树int leftHeight = 0;bool isLeftBalanced = _IsBalanceTree(root->_left, leftHeight);// 递归检查右子树int rightHeight = 0;bool isRightBalanced = _IsBalanceTree(root->_right, rightHeight);// 当前节点的高度height = max(leftHeight, rightHeight) + 1;// 计算平衡因子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;}// 如果左右子树都是 AVL 树，且当前节点也平衡，则整棵树是 AVL 树return isLeftBalanced && isRightBalanced;}

2.6 AVL树的删除

2.7 AVL的代码实现

2.7.1 AVLTree.h

#pragma once#include <iostream>
#include <assert.h>using namespace std;namespace Lzc
{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 factorAVLTreeNode(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 (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 (kv.first > parent->_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 = cur->_parent;}else if (parent->_bf == -2 || parent->_bf == 2){if (parent->_bf == -2 && cur->_bf == -1)RotateR(parent);else if (parent->_bf == 2 && cur->_bf == 1)RotateL(parent);else if (parent->_bf == -2 && cur->_bf == 1)RotateLR(parent);else if (parent->_bf == 2 && cur->_bf == -1)RotateRL(parent);elseassert(false);break;}else{assert(false);}}return true;}void RotateR(Node* parent){Node* pParent = parent->_parent;Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;subL->_parent = pParent;if (pParent == nullptr) // 当pParent == nullptr时,_root == parent{_root = subL;}else{if (pParent->_left == parent)pParent->_left = subL;elsepParent->_right = subL;}subL->_bf = 0;parent->_bf = 0;}void RotateL(Node* parent){Node* pParent = parent->_parent;Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;subR->_parent = pParent;if (pParent == nullptr)_root = subR;else{if (pParent->_left == parent)pParent->_left = subR;elsepParent->_right = subR;}subR->_bf = 0;parent->_bf = 0;}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int _bf = subLR->_bf;RotateL(subL);RotateR(parent);if (_bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (_bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (_bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int _bf = subRL->_bf;RotateR(subR);RotateL(parent);if (_bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else if (_bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (_bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else{assert(false);}}void InOrder(){_InOrder(_root);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}bool IsBalanceTree(){int height = 0;return _IsBalanceTree(_root, height);}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;elsereturn 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;}int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}bool _IsBalanceTree(Node* root, int& height) { // 后序// 空树是 AVL 树if (nullptr == root) {height = 0;return true;}// 递归检查左子树int leftHeight = 0;bool isLeftBalanced = _IsBalanceTree(root->_left, leftHeight);// 递归检查右子树int rightHeight = 0;bool isRightBalanced = _IsBalanceTree(root->_right, rightHeight);// 当前节点的高度height = max(leftHeight, rightHeight) + 1;// 计算平衡因子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;}// 如果左右子树都是 AVL 树，且当前节点也平衡，则整棵树是 AVL 树return isLeftBalanced && isRightBalanced;}Node* _root = nullptr;};
}

2.7.2 Test.cpp

#include "AVLTree.h"
#include <vector    >namespace Lzc
{void TestAVLTree1() {AVLTree<int, int> t;// 常规的测试用例int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例// int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a) {t.Insert({ e, e });}t.InOrder();cout << t.IsBalanceTree() << endl;}// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等void TestAVLTree2() {const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++) {v.push_back(rand() + i);}// 测试插入性能size_t begin2 = clock();AVLTree<int, int> t;for (auto e : v) {t.Insert(make_pair(e, e));}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;// 测试平衡性、高度和大小cout << "IsBalanceTree:" << t.IsBalanceTree() << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.Size() << endl;// 测试查找性能size_t begin1 = clock();// 查找已存在的值/*for (auto e : v) {t.Find(e);}*/// 查找随机值for (size_t i = 0; i < N; i++) {t.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;}
}int main()
{Lzc::TestAVLTree1();// Lzc::TestAVLTree2();return 0;
}