当前位置：首页 > news >正文

【C++】AVL树

news 2025/6/9 17:26:46

一、AVL树的引入

二、AVL树

🍔AVL树的概念

🍟AVL树节点的定义

🌮AVL树的插入

🥪AVL树的旋转

三、AVL树的验证

四、结语

一、AVL树的引入

🌟我们知道 map/multimap/set/multiset 这几个容器的共同点是：其底层都是按照二叉搜索树来实现

不过二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现

💧接下来我们就一起看看如何实现平衡二叉树的改造：

二、AVL树

🍔AVL树的概念

🌟针对效率降低的问题，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决的方法：

👉当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1，即可降低树的高度，从而减少平均搜索长度。

AVL树是具有以下性质的二叉搜索树：

1️⃣它的左右子树都是AVL树

2️⃣左右子树高度之差(简称平衡因子)的绝对值不超过1（需要通过调整系欸但

🍟AVL树节点的定义

🌟AVL树节点的定义：

🌮AVL树的插入

AVL树的插入分为两步：

1️⃣按照二叉搜索树的方式插入新节点

2️⃣调整节点的平衡因子

针对平衡因子的调整：

设平衡因子的计算：右子树高度-左子树高度，所以对于一个节点来说：

1️⃣新节点插入到左边，平衡因子 -1

2️⃣新节点插入到右边，平衡因子 +1

插入后，节点的平衡因子可能的情况 0，正负1，正负2

0：插入之前为正负1，插入后变为0

正负1：插入之前为0，插入后整体的高度变高一层，需要向上更新

正负2：插入之前为正负1，插入后违反了平衡树的性质，需要进行节点位置的调制
bool insert(const T& data)
{//按照二叉搜索树的插入规则插入//判断_root是否为空if (!_root)_root = new Node(data);pNode cur = _root;pNode parent = nullptr;while (cur){if (cur->_data > data)cur = cur->_pleft;else if (cur->_data < data)cur = cur->_pright;elsereturn false;}pNode newNode = new Node(data);if (data > parent->_data){parent->_pright = newNode;newNode->_parent = parent;}else{parent->_pleft = newNode;newNode->_parent = parent;}//调整平衡因子while (parent){// 更新双亲的平衡因子if (newNode == parent->_pleft)parent->_bf--;elseparent->_bf++;// 更新后检测双亲的平衡因子if (0 == parent->_bf){break;}else if (1 == parent->_bf || -1 == parent->_bf){newNode = parent;parent = newNode->_parent;}else{if (2 == parent->_bf){// ...}else{// ...}}}return true;
}

🥪AVL树的旋转

❗针对平衡因子出现正负2的情况，我们需要进行旋转处理

🌟下面分别讨论不同情况下的旋转：

1️⃣新节点插入较高左子树的左侧---左左 : 右单旋

2️⃣新节点插入较高右子树的右侧--右右：左单旋

3️⃣新节点插入较高左子树的右侧---左右：先左单旋再右单旋

4️⃣新节点插入较高右子树的左侧---右左：先右单旋再左单旋

🔥总结：

假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑

1️⃣parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR

当subR的平衡因子为1时，执行左单旋

当subR的平衡因子为-1时，执行右左双旋

2️⃣parent的平衡因子为-2，说明pParent的左子树高，设parent的左子树的根为subL

当subL的平衡因子为-1时，执行右单旋

当subL的平衡因子为1时，执行左右双旋

旋转完成后，原parent为根的子树已经平衡，不需要再向上更新

三、AVL树的验证

🌟AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1️⃣验证其为二叉搜索树，如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

2️⃣验证其为平衡树，每个节点子树高度差的绝对值不超过1

提供两个代码供大家验证：
void test1()
{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> t;for (auto e : v){if (e == 14604){int x = 0;}t.insert(e);cout << "Insert:" << e << "->" << t.IsBalance() << endl;}cout << t.IsBalance() << endl;t.InOrder();
}
void test2()
{//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> t;for (auto e : a){t.insert(e);}int i = 0;t.InOrder();cout << t.IsBalance() << endl;return 0;
}