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

数据结构--AVL树

news 来源：原创 2025/8/26 14:04:48

一、二叉搜索树（Binary Search Tree, BST）

基本性质

对于树中的每个节点，其左子树中的所有节点值均小于该节点值。
其右子树中的所有节点值均大于该节点值。
左右子树也分别是二叉搜索树。

极端场景

在极端情况下，如插入节点顺序为升序或降序时，二叉搜索树会退化为链表结构。例如，依次插入 1, 2, 3, 4, 5，此时树的形状为一条从根节点开始不断向右延伸的链。这种退化导致树的高度变为 O (n)（n 为节点数），原本二叉搜索树查找、插入、删除操作平均时间复杂度为 O (log n)，此时会退化为 O (n)，效率大幅降低。

二、AVL 树（Adelson-Velsky and Landis Tree）

定义与特点

AVL 树是一种自平衡的二叉搜索树。它在向二叉搜索树中插入新节点时，通过特定的旋转操作，保证每个节点的左右子树高度之差的绝对值不超过 1。这使得 AVL 树在动态插入和删除节点过程中，始终保持较为平衡的状态，从而保证基本操作的时间复杂度稳定在 O (log n)。

平衡因子（Balance Factor）

定义：平衡因子 = 右子树高度 - 左子树高度。
AVL 树的平衡条件：对于 AVL 树中的每一个节点，其平衡因子的绝对值不超过 1。即，| 右子树高度 - 左子树高度 | ≤ 1。当插入或删除节点导致某个节点的平衡因子绝对值大于 1 时，AVL 树会进行相应的旋转操作（左单旋、右单旋、双旋（先左旋后右旋和先右旋后左旋））来重新平衡树结构，确保树始终满足 AVL 树的性质。

三、AVL 树的实现

设计结构

1.节点结构

template<class K, class V>
class AVLTreeNode {
public:pair<K, V> _kv;              // 键值对AVLTreeNode<K, V>* _left;     // 左子节点AVLTreeNode<K, V>* _right;    // 右子节点AVLTreeNode<K, V>* _parent;   // 父节点（关键，用于回溯调整平衡）int _bf;                      // 平衡因子（右子树高度 - 左子树高度）AVLTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};

2.树结构

template<class K, class V>
class AVLTree {typedef AVLTreeNode<K, V> Node;
public://增删改查操作//......
private:Node* _root = nullptr;  // 根节点
};

操作函数

插入

1.查找插入位置：

若树为空，直接创建根节点。

否则，从根节点开始遍历查找：

bool insert(const pair<K, V>& kv) {if (_root == nullptr) {      // 空树直接插入_root = new Node(kv);return true;}Node* cur = _root, *parent = nullptr;while (cur) {                // 向下搜索插入位置parent = cur;if (kv.first < cur->_kv.first) cur = cur->_left;else if (kv.first > cur->_kv.first) cur = cur->_right;else return false;       // 重复键不允许插入}

2.插入新节点：

创建新节点 cur，根据键值大小链接到父节点的左或右。

    cur = new Node(kv);cur->_parent = parent;       // 绑定父节点if (kv.first < parent->_kv.first) parent->_left = cur;     // 插入到左子树else parent->_right = cur;    // 插入到右子树

设置 cur->_parent = parent（关键，后续调整依赖父指针）。

3.更新平衡因子：

从插入点的父节点向上回溯，调整每个祖先节点的平衡因子：
- 插入在左子树：parent->_bf--
- 插入在右子树：parent->_bf++
根据平衡因子决定是否继续调整或旋转：
- _bf == 0：停止调整（子树高度未变）。
- |_bf| == 1：继续向上调整。
- |_bf| == 2：触发旋转（需判断旋转类型）。

    while (parent) {             // 从父节点向上回溯调整if (cur == parent->_left) parent->_bf--;else parent->_bf++;if (parent->_bf == 0) break;     // 高度不变，无需调整else if (abs(parent->_bf) == 1) { // 高度变化，继续向上cur = parent;parent = parent->_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) rotateRL(parent);       //右-左旋else if (parent->_bf == -2 && cur->_bf == 1) rotateLR(parent);       //左-右旋break;}}return true;
}

左单旋（rotateL）

确定关键节点
- parent：失衡节点（_bf == 2）。
- cur：parent的右子节点（_bf == 1）。
- curleft：cur的左子节点。
- grandParent：parent的父节点。
调整指针关系

1.处理curleft：

parent->_right = curleft：将parent的右子指向curleft。
若curleft存在：设置curleft->_parent = parent。

2.建立cur与parent关系：

cur->_left = parent：cur的左子指向原父节点。
parent->_parent = cur：原父节点的父指针指向cur。

3.链接到原树：

cur->_parent = grandParent：cur的父指针指向原祖父。
若grandParent为空：更新根节点为cur。
否则：根据parent在原树的位置，将grandParent的左/右子指向cur。

更新平衡因子
- parent->_bf = 0
- cur->_bf = 0

完整代码

void rotateL(Node* parent) {Node* grandParent = parent->_parent;Node* cur = parent->_right, * curleft = cur->_left;parent->_right = curleft;if (curleft) {curleft->_parent = parent;}cur->_left = parent;parent->_parent = cur;cur->_parent = grandParent;if (grandParent == nullptr) {_root = cur;}else {if (parent == grandParent->_left) {grandParent->_left = cur;}else {grandParent->_right = cur;}}parent->_bf = cur->_bf = 0;
}

右单旋（rotateR）

参考图：
- 确定关键节点，调节指针关系：
- 链接到原树：

复现代码：

void rotateR(Node* parent) {Node* grandParent = parent->_parent;Node* cur = parent->_left, * curright = cur->_right;parent->_left = curright;if (curright) {curright->_parent = parent;}cur->_right = parent;parent->_parent = cur;if (grandParent == nullptr) {_root = cur;cur->_parent = nullptr;}else {if (grandParent->_left == parent) {grandParent->_left = cur;}else {grandParent->_right = cur;}cur->_parent = grandParent;}parent->_bf = cur->_bf = 0;
}

左-右双旋（rotateLR）

适用场景
父节点平衡因子为 -2，左子节点平衡因子为 1（左子树的右子树过高）。

步骤：

1.定位关键节点：

parent：失衡节点（平衡因子 -2）。
cur：parent 的左子节点（平衡因子 1）。
curright：cur 的右子节点（需记录其原始平衡因子 tmpbf）。

2.执行双旋：

先左旋：对 cur 调用左单旋（rotateL），使 curright 成为新的左子树根。
再右旋：对 parent 调用右单旋（rotateR），使 curright 成为新的根节点。

3.调整平衡因子：

tmpbf == 1：
- parent->_bf = 0，cur->_bf = -1（左子树高度减少）。
- curright->_bf = 0。
tmpbf == -1：
- parent->_bf = 1（右子树高度增加）。
- cur->_bf = 0，curright->_bf = 0。
tmpbf == 0：所有相关节点平衡因子置 0。

完整代码

void rotateLR(Node* parent) {Node* cur = parent->_left, * curright = cur->_right;int tmpbf = curright->_bf;rotateL(parent->_left);rotateR(parent);if (tmpbf == -1) {cur->_bf = 0;curright->_bf = 0;parent->_bf = 1;}else if (tmpbf == 1) {parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}else if (tmpbf == 0) {parent->_bf = cur->_bf = curright->_bf = 0;}else {assert(false);}
}

右-左双旋（rotateRL）

适用场景：
父节点平衡因子为 2，右子节点平衡因子为 -1（右子树的左子树过高）。

步骤：