『 C++ 入门到放弃 』- AVL树

1. AVL树介绍

AVL 树 也称为平衡二叉搜索树，其在一般二叉搜索树基础上加入了平衡因子，平衡因子的有效范围在 [ -1, 1 ] 之间，假如超过这段区间，则此树即不平衡，就必须借由旋转来调整，使其恢复平衡

2. AVL树实现

2.1 AVL树基本结构

// 每个节点包含：左子节点指针、右子节点指针、父节点指针、键值对数据、平衡因子
template <class K, class V> struct AVLNode {// 构造函数：初始化节点的所有成员变量AVLNode(const pair<K, V> &kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0) {}AVLNode<K, V> *_left;   // 左子节点指针，指向左子树的根节点AVLNode<K, V> *_right;  // 右子节点指针，指向右子树的根节点AVLNode<K, V> *_parent; // 父节点指针，指向父节点（根节点的父节点为nullptr）pair<K, V> _kv;         // 键值对数据，存储实际的键和值int _bf; // 平衡因子 = 右子树高度 - 左子树高度，用于判断是否平衡};

// AVL树类模板定义
// K: 键的类型，V: 值的类型
template <class K, class V> class AVLTree {typedef AVLNode<K, V> Node; // 类型别名，简化代码书写private:Node *_root = nullptr; };

2.2 AVL树旋转逻辑

//右旋逻辑
void RotateR(Node *parent) {/*右旋的目标：1. 将parent的左子节点subL提升为新的根节点2. 将subL的右子节点subLR接到parent的左子节点位置3. 将parent接到subL的右子节点位置4. 更新所有相关的父节点指针，维护树的完整性*/Node *subL = parent->_left; // 获取左子节点（将成为新的根节点）Node *subLR = subL->_right; // 获取左子节点的右子节点（需要重新接）// 步骤1：将subLR接到parent的左子节点位置parent->_left = subLR;if (subLR) {subLR->_parent = parent; // 更新subLR的父节点指针}// 步骤2：将parent接到subL的右子节点位置subL->_right = parent;// 步骤3：更新祖父节点的指向关系Node *parentParent = parent->_parent; // 获取祖父节点parent->_parent = subL;               // 更新parent的父节点指针if (parentParent == nullptr) {// 情况A：parent是根节点，subL成为新的根节点_root = subL;subL->_parent = nullptr; // 根节点没有父节点} else {// 情况B：parent不是根节点，需要更新祖父节点的指向if (parent == parentParent->_left) {parentParent->_left = subL; // parent原本是左子节点，subL也成为左子节点} else {parentParent->_right = subL; // parent原本是右子节点，subL也成为右子节点}subL->_parent = parentParent; // 更新subL的父节点指针}// 步骤4：更新平衡因子// 右旋后，原来的parent和subL都变为平衡状态（平衡因子为0）parent->_bf = 0;subL->_bf = 0;
}

// 左旋逻辑
void RotateL(Node *parent) {/*左旋的目标：1. 将parent的右子节点subR提升为新的根节点2. 将subR的左子节点subRL接到parent的右子节点位置3. 将parent接到subR的左子节点位置4. 更新所有相关的父节点指针，维护树的完整性*/Node *subR = parent->_right; // 获取右子节点（将成为新的根节点）Node *subRL = subR->_left;   // 获取右子节点的左子节点（需要重新接）// 步骤1：将subRL接到parent的右子节点位置parent->_right = subRL;if (subRL) {subRL->_parent = parent; // 更新subRL的父节点指针}// 步骤2：将parent接到subR的左子节点位置subR->_left = parent;// 步骤3：更新祖父节点的指向关系Node *parentParent = parent->_parent; // 获取祖父节点parent->_parent = subR;               // 更新parent的父节点指针if (parentParent == nullptr) {// 情况A：parent是根节点，subR成为新的根节点_root = subR;subR->_parent = nullptr; // 根节点没有父节点} else {// 情况B：parent不是根节点，需要更新祖父节点的指向if (parent == parentParent->_right) {parentParent->_right =subR; // parent原本是右子节点，旋转后subR成为新的右子节点} else {parentParent->_left =subR; // parent原本是左子节点，旋转后subR成为新的左子节点}subR->_parent = parentParent; // 更新subR的父节点指针}// 步骤4：更新平衡因子// 左旋后，原来的parent和subR都变为平衡状态（平衡因子为0）parent->_bf = 0;subR->_bf = 0;
}

// 先左旋再右旋逻辑
void RotateLR(Node *parent) {/*思考的情景：顺序插入 20 10 15左右旋的目标：1. 先对parent的左子节点subL进行左旋，将左右情况转换为左左情况2. 再对parent进行右旋，恢复平衡3. 根据旋转前subLR的平衡因子，正确调整最终的平衡因子*/Node *subL = parent->_left; // 获取左子节点Node *subLR = subL->_right; // 获取左子节点的右子节点（关键节点）int bf = subLR->_bf;        // 记录旋转前subLR的平衡因子，用于后续调整// 步骤1：对subL进行左旋，将左右情况转换为左左情况RotateL(subL);// 步骤2：对parent进行右旋，恢复平衡RotateR(parent);// 步骤3：根据旋转前subLR的平衡因子调整最终的平衡因子// 注意：旋转后，subLR成为新的根节点，subL和parent成为其子节点if (bf == 0) {// 情况A：subLR原本平衡（平衡因子为0）// 旋转后所有相关节点都变为平衡状态parent->_bf = 0;subL->_bf = 0;} else if (bf == 1) { // 情况B：subLR原本右子树较高（平衡因子为1）// 旋转后parent平衡，subL平衡parent->_bf = 0;subL->_bf = -1;} else if (bf == -1) { // 情况C：subLR原本左子树较高（平衡因子为-1）// 旋转后parent右子树较高，subL平衡parent->_bf = 1;subL->_bf = 0;} else {// 理论上不应该出现其他情况，平衡因子只能是-1, 0, 1assert(false);}
}

void RotateRL(Node *parent) {/*右左旋的目标：1. 先对parent的右子节点subR进行右旋，将右左情况转换为右右情况2. 再对parent进行左旋，恢复平衡3. 根据旋转前subRL的平衡因子，正确调整最终的平衡因子*/Node *subR = parent->_right; // 获取右子节点Node *subRL = subR->_left;   // 获取右子节点的左子节点（关键节点）int bf = subRL->_bf;         // 记录旋转前subRL的平衡因子，用于后续调整// 步骤1：对subR进行右旋，将右左情况转换为右右情况RotateR(subR);// 步骤2：对parent进行左旋，恢复平衡RotateL(parent);// 步骤3：根据旋转前subRL的平衡因子调整最终的平衡因子// 注意：旋转后，subRL成为新的根节点，parent和subR成为其子节点if (bf == 0) { // 情况A：subRL原本平衡（平衡因子为0）// 旋转后所有相关节点都变为平衡状态parent->_bf = 0;subR->_bf = 0;} else if (bf == 1) { // 情况B：subRL原本右子树较高（平衡因子为1）// 旋转后parent左子树较高，subR平衡parent->_bf = -1;subR->_bf = 0;} else if (bf == -1) { // 情况C：subRL原本左子树较高（平衡因子为-1）// 旋转后parent平衡，subR平衡parent->_bf = 0;subR->_bf = 1;} else {// 理论上不应该出现其他情况，平衡因子只能是-1, 0, 1assert(false);}
}

2.3 插入

bool insert(const pair<K, V> &kv) {// 情况1：空树处理// 如果树为空，直接创建根节点并返回成功if (_root == nullptr) {_root = new Node(kv);return true;}// 情况2：非空树的插入逻辑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 {// 找到相同键值，AVL树不允许重复键，返回插入失败return false;}}// 找到合适的插入位置，创建新节点并建立父子关系cur = new Node(kv); // 创建新节点，平衡因子初始化为0if (parent->_kv.first < kv.first) {parent->_right = cur; // 新节点作为右子节点插入} else {parent->_left = cur; // 新节点作为左子节点插入}cur->_parent = parent; // 设置新节点的父节点指针// ========== AVL树平衡调整阶段 ==========// 从插入位置的父节点开始，向上更新平衡因子并进行必要的旋转调整// 这是AVL树区别于普通二叉搜索树的关键部分while (parent) {// 更新平衡因子：根据新节点插入的位置调整父节点的平衡因子if (parent->_left == cur) {parent->_bf--; // 插入到左子树，左子树高度+1，平衡因子-1} else {parent->_bf++; // 插入到右子树，右子树高度+1，平衡因子+1}// 情况1：平衡因子为0，表示该节点已达到平衡状态// 这种情况下，插入操作不会影响该节点的高度，因此不需要进一步调整if (parent->_bf == 0) {break; // 退出循环，插入操作完成}// 情况2：平衡因子为1或-1，表示该节点暂时平衡，但高度发生变化// 需要继续向上更新祖先节点的平衡因子，因为高度的变化会影响上层节点else if (parent->_bf == 1 || parent->_bf == -1) {cur = parent;             // 当前节点向上移动到父节点parent = parent->_parent; // 父节点向上移动到祖父节点}// 情况3：平衡因子为2或-2，表示该节点不平衡，需要进行旋转调整// 这是AVL树维护平衡的核心操作else if (parent->_bf == 2 || parent->_bf == -2) {// 根据平衡因子和插入位置决定具体的旋转类型if (parent->_bf == 2) {// 右子树过高（平衡因子为2），需要左旋或右左旋if (cur->_bf == 1) {// 右右情况：cur的平衡因子为1，表示右子树更高// 这种情况只需要一次左旋就能恢复平衡RotateL(parent);} else {// 右左情况：cur的平衡因子为-1，表示左子树更高// 这种情况需要先右旋再左旋（右左旋）RotateRL(parent);}} else { // parent->_bf == -2// 左子树过高（平衡因子为-2），需要右旋或左右旋if (cur->_bf == -1) {// 左左情况：cur的平衡因子为-1，表示左子树更高// 这种情况只需要一次右旋就能恢复平衡RotateR(parent);} else {// 左右情况：cur的平衡因子为1，表示右子树更高// 这种情况需要先左旋再右旋（左右旋）RotateLR(parent);}}break; // 旋转完成后，整棵树已恢复平衡，退出循环} else {// 理论上不应该出现其他情况，如果出现说明逻辑有问题// 平衡因子只能是-2, -1, 0, 1, 2这五种情况assert(false);}}return true; // 插入操作成功完成
}

2.4 查找

Node *find(const K &key) {Node *cur = _root; // 从根节点开始搜索while (cur) {if (cur->_kv.first < key) {// 当前节点的键值小于目标键值，往右子树搜索cur = cur->_right;} else if (cur->_kv.first > key) {// 当前节点的键值大于目标键值，往左子树搜索cur = cur->_left;} else {// 找到目标键值，返回对应节点return cur;}}// 搜索完毕未找到目标键值，返回nullptrreturn nullptr;
}

2.5 判断是否为AVL树

bool _IsAVLTree(Node *root) {// 空树是合法的AVL树if (root == nullptr) {return true;}// 计算左右子树的高度int leftHeight = _Height(root->_left);   // 左子树高度int rightHeight = _Height(root->_right); // 右子树高度// 验证平衡因子的正确性// 平衡因子应该等于右子树高度减去左子树高度if (rightHeight - leftHeight != root->_bf) {// 平衡因子异常，输出错误信息cout << "平衡因子异常:" << root->_kv.first << "平衡因子:" << root->_bf<< "高度差:" << rightHeight - leftHeight << endl;return false;}// 验证AVL树的平衡性质// 1. 左右子树高度差不能超过1（即平衡因子在[-1,1]范围内）// 2. 递归验证左右子树是否也是合法的AVL树return abs(rightHeight - leftHeight) < 2 && _IsAVLTree(root->_left) &&_IsAVLTree(root->_right);
}

2.6 判断树的高度

int _Height(Node *root) {// 空树高度为0if (root == nullptr) {return 0;}// 递归计算左右子树的高度int leftHeight = _Height(root->_left);   // 左子树高度int rightHeight = _Height(root->_right); // 右子树高度// 返回较高的子树高度加1（根节点贡献1个高度）return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}