一、概念AVL树是最先发明的自平衡二叉查找树它可以是一棵空树或者具备以下性质的二叉搜索树对于该树的每一个节点其左右子树高度差的绝对值不超过1。AVL树是一棵高度平衡搜索二叉树核心是通过控制节点左右子树的高度差来维持平衡。在AVL树实现过程中引入了平衡因子的概念即某个节点的右子树高度减去左子树高度。需要注意的是平衡因子并非实现AVL树的必需条件只是为了更方便地判断和控制树的平衡而引入的辅助工具。AVL树的整体节点数量和分布与完全二叉树类似其树的高度可以严格控制在logNN为节点总数因此AVL树的增、删、查、改等基本操作的时间复杂度都能稳定在O(logN)保证了高效的操作性能。二、实现一结构定义AVL树的节点需要包含键值对、左右孩子指针、父节点指针用于后续平衡因子的更新以及平衡因子具体结构定义如下templateclass K, class V struct AVLTreeNode { // 需要parent指针后续更新平衡因子时可通过父指针向上追溯 pairK, V _kv; AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; AVLTreeNodeK, V* _parent; int _bf; // balance factor平衡因子 // 构造函数 AVLTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) ,_bf(0) {} }; templateclass K, class V class AVLTree { typedef AVLTreeNodeK, V Node; public: // 后续实现插入、删除、查找等成员函数 //... private: Node* _root nullptr; // 根节点初始化为空 };二插入操作1. 插入总述AVL树的插入过程与普通二叉搜索树的插入过程完全相同都是先找到合适的插入位置创建新节点并完成链接。不同之处在于AVL树插入新节点后需要从插入节点的父节点开始依次递归向上检查每个节点的平衡因子判断插入操作是否破坏了AVL树的平衡特性并同步更新平衡因子若平衡被破坏则需进行旋转调整。2. 平衡因子的更新与平衡判断平衡因子的更新从插入节点的父节点开始更新规则如下如果新节点插入在父节点的右子树则父节点的平衡因子加1如果插入在左子树则父节点的平衡因子减1。更新后父节点的平衡因子会出现以下几种变化情况对应不同的处理逻辑平衡因子从1或-1变为0说明该父节点所在子树的高度没有发生变化插入前子树高度差为1插入后高度差变为0整体高度不变。因此更上层父节点的左右子树高度均未改变平衡因子也不会受到影响平衡因子的更新过程在此停止。平衡因子从0变为1或-1说明该父节点所在子树的高度增加了1插入前子树高度平衡插入后高度差变为1。由于子树高度发生变化更上层父节点的左右子树高度差可能受到影响因此平衡因子需要继续向上更新。平衡因子从1或-1变为2或-2此时该父节点所在的子树已经失去平衡左右子树高度差的绝对值超过1需要通过旋转操作来恢复平衡。旋转的核心目的有两个① 使当前父节点的平衡因子恢复正常回到-1、0、1中的一种② 恢复当前子树的高度到插入前的状态。正因为旋转能恢复子树高度所以旋转后平衡因子的更新过程可以在此停止无需继续向上追溯。总结来说平衡因子的更新过程有三种停止情况更新到某个节点时其平衡因子的绝对值大于1通过旋转处理后更新过程结束更新到某个节点时其平衡因子变为0不会影响更上层节点更新过程结束最坏情况是更新到根节点只要根节点的平衡因子绝对值小于2更新过程即可结束。补充说明更上层父节点的平衡因子是否需要更新核心取决于当前插入节点所在子树的高度是否发生变化——子树高度不变则无需更新子树高度变化则需要继续更新。3. 插入代码实现bool Insert(const T data) { typedef AVLTreeNodeT Node; // 情况1树为空直接创建根节点 if (_root nullptr) { _root new Node(data); return true; } // 情况2树非空找到插入位置 Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_data data) { parent cur; cur cur-_right; } else if (cur-_data data) { parent cur; cur cur-_left; } else { // 插入的键值已存在插入失败 return false; } } // 创建新节点并与父节点建立链接 cur new Node(data); if (parent-_data data) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; // 链接父节点方便后续向上更新平衡因子 // 向上更新平衡因子并判断是否需要旋转 while (parent) { // 根据插入位置更新父节点的平衡因子 if (cur parent-_left) parent-_bf--; else parent-_bf; // 判断当前父节点所在子树是否失衡 if (parent-_bf 2 || 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) RotateLR(parent); // 左右双旋 else if (parent-_bf 2 cur-_bf -1) RotateRL(parent); // 右左双旋 else assert(false); // 异常情况断言报错 break; // 旋转后子树高度恢复停止更新 } else if (parent-_bf 0) { // 子树高度未变停止更新 break; } else if (parent-_bf 1 || parent-_bf -1) { // 子树高度变化继续向上更新 cur parent; parent parent-_parent; } } return true; }三旋转操作1. 旋转原则旋转是AVL树恢复平衡的核心操作其基本原则是在严格保证二叉搜索树规则左子树所有节点值小于根节点右子树所有节点值大于根节点的前提下使失衡的子树恢复平衡同时降低子树的高度确保后续操作的时间复杂度稳定在O(logN)。2. 右单旋RotateR1使用场景适用于父节点的平衡因子为-2且其左子树根节点的平衡因子为-1的情况即左子树过高且左子树的左子树也过高属于“左左”失衡。2操作步骤设当前失衡子树的根节点为P父节点P的左子树根节点为subLsubL的右子树为subLR。具体操作如下1. 让P成为subL的右子树根节点2. 让subLR成为P的左子树根节点3. 调整P、subL以及它们父节点的指针链接确保树的结构完整。3可行性分析从二叉搜索树的规则来看P以及P的右子树所有节点的值都大于subLsubLR所在子树的所有节点的值都小于P、大于subL。因此上述操作不会破坏二叉搜索树的规则是可行的。从平衡恢复和高度降低来看我们可以通过抽象场景理解假设以P此处抽象为10为根的子树中subL抽象为5的左子树a、subL的右子树b、P的右子树c均为高度为hh≥0的AVL树满足右单旋场景的前提是a、b、c高度均为h。P可能是整棵树的根也可能是某棵局部子树的根。当在a子树中插入一个新节点时a子树的高度从h变为h1向上更新平衡因子后P的平衡因子从-1变为-2此时P为根的子树左右高度差超过1出现失衡左边过高需要通过右单旋恢复平衡。旋转的核心逻辑的是由于5 b子树的值 10将b子树变为P10的左子树P10变为subL5的右子树subL5成为该子树新的根。这样的操作既符合二叉搜索树规则又能使子树恢复平衡同时子树的高度恢复到插入前的h2满足旋转原则。如果P原本是局部子树的根旋转后子树高度恢复不会影响更上层节点插入操作即可结束。4平衡因子更新右单旋操作后原父节点P和原左子树根节点subL的平衡因子都会恢复为0因为旋转后两者的左右子树高度差均为0。5代码实现void RotateR(Node* pParent) { Node* subL pParent-_left; Node* subLR subL-_right; // 第一步调整pParent和subLR的链接 pParent-_left subLR; // 若subLR不为空更新其parent指针指向pParent if (subLR) subLR-_parent pParent; // 第二步调整subL和pParent的链接 subL-_right pParent; Node* subP pParent-_parent; // 保存pParent的父节点 pParent-_parent subL; // 第三步调整subL与原pParent父节点的链接 if (pParent _root) { // 若pParent是根节点旋转后subL成为新根 _root subL; subL-_parent nullptr; } else { // 若pParent是局部子树的根根据其在父节点的左右位置链接subL if (subP-_left pParent) subP-_left subL; else subP-_right subL; subL-_parent subP; } // 更新平衡因子 subL-_bf 0; pParent-_bf 0; }3. 左单旋RotateL1使用场景适用于父节点的平衡因子为2且其右子树根节点的平衡因子为1的情况即右子树过高且右子树的右子树也过高属于“右右”失衡。2操作步骤设当前失衡子树的根节点为P父节点P的右子树根节点为subRsubR的左子树为subRL。具体操作如下1. 让P成为subR的左子树根节点2. 让subRL成为P的右子树根节点3. 调整P、subR以及它们父节点的指针链接确保树的结构完整。注左单旋的可行性、平衡因子更新逻辑与右单旋对称此处不再重复赘述核心是恢复右右失衡的子树平衡降低子树高度。4. 左右双旋RotateLR1使用场景适用于父节点的平衡因子为-2且其左子树根节点的平衡因子为1的情况即左子树过高但左子树的右子树过高属于“左右”失衡。此时单旋无法解决失衡问题需要先通过一次左单旋调整左子树结构再通过一次右单旋恢复整体平衡。2操作步骤设当前失衡子树的根节点为P父节点P的左子树根节点为subLsubL的右子树为subLR。具体操作分为两步1. 先对subL所在的子树进行左单旋将subLR提升为subL所在子树的根使P所在的子树变为“左左”失衡状态满足右单旋的适用场景2. 再对P所在的子树进行右单旋恢复整个子树的平衡。3平衡因子更新分场景讨论左右双旋的平衡因子更新取决于插入节点所在的位置即subLR的平衡因子具体分为3种场景场景1h ≥ 1时新增节点插入在subLR的左子树抽象为e子树e子树的高度从h-1变为h向上更新平衡因子8→5→10引发失衡。此时subLR的平衡因子为-1旋转后subL的平衡因子变为0subLR的平衡因子变为0P的平衡因子变为1。场景2h ≥ 1时新增节点插入在subLR的右子树抽象为f子树f子树的高度从h-1变为h向上更新平衡因子8→5→10引发失衡。此时subLR的平衡因子为1旋转后subL的平衡因子变为-1subLR的平衡因子变为0P的平衡因子变为0。场景3h 0时subL的左子树、subLR的左右子树、P的右子树抽象为a、b、c均为空树subLR本身就是新增节点向上更新平衡因子5→10引发失衡。此时subLR的平衡因子为0旋转后subL、subLR、P的平衡因子均变为0。4代码实现void RotateLR(Node* pParent) { Node* subL pParent-_left; Node* subLR subL-_right; int bf subLR-_bf; // 保存subLR的平衡因子用于后续更新 // 第一步对subL进行左单旋 RotateL(pParent-_left); // 第二步对pParent进行右单旋 RotateR(pParent); // 根据subLR的平衡因子更新三个节点的平衡因子 if (bf 0) { subL-_bf 0; subLR-_bf 0; pParent-_bf 0; } else if (bf 1) { subL-_bf -1; subLR-_bf 0; pParent-_bf 0; } else if (bf -1) { subL-_bf 0; subLR-_bf 0; pParent-_bf 1; } else { assert(false); // 异常情况断言报错 } }5. 右左双旋RotateRL1使用场景适用于父节点的平衡因子为2且其右子树根节点的平衡因子为-1的情况即右子树过高但右子树的左子树过高属于“右左”失衡。此时单旋无法解决失衡问题需要先通过一次右单旋调整右子树结构再通过一次左单旋恢复整体平衡。2操作步骤设当前失衡子树的根节点为P父节点P的右子树根节点为subRsubR的左子树为subRL。具体操作分为两步1. 先对subR所在的子树进行右单旋将subRL提升为subR所在子树的根使P所在的子树变为“右右”失衡状态满足左单旋的适用场景2. 再对P所在的子树进行左单旋恢复整个子树的平衡。注右左双旋的可行性、平衡因子更新逻辑与左右双旋对称核心是恢复右左失衡的子树平衡降低子树高度此处不再重复赘述。
AVL树实现
发布时间：2026/5/22 13:06:50
一、概念AVL树是最先发明的自平衡二叉查找树它可以是一棵空树或者具备以下性质的二叉搜索树对于该树的每一个节点其左右子树高度差的绝对值不超过1。AVL树是一棵高度平衡搜索二叉树核心是通过控制节点左右子树的高度差来维持平衡。在AVL树实现过程中引入了平衡因子的概念即某个节点的右子树高度减去左子树高度。需要注意的是平衡因子并非实现AVL树的必需条件只是为了更方便地判断和控制树的平衡而引入的辅助工具。AVL树的整体节点数量和分布与完全二叉树类似其树的高度可以严格控制在logNN为节点总数因此AVL树的增、删、查、改等基本操作的时间复杂度都能稳定在O(logN)保证了高效的操作性能。二、实现一结构定义AVL树的节点需要包含键值对、左右孩子指针、父节点指针用于后续平衡因子的更新以及平衡因子具体结构定义如下templateclass K, class V struct AVLTreeNode { // 需要parent指针后续更新平衡因子时可通过父指针向上追溯 pairK, V _kv; AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; AVLTreeNodeK, V* _parent; int _bf; // balance factor平衡因子 // 构造函数 AVLTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) ,_bf(0) {} }; templateclass K, class V class AVLTree { typedef AVLTreeNodeK, V Node; public: // 后续实现插入、删除、查找等成员函数 //... private: Node* _root nullptr; // 根节点初始化为空 };二插入操作1. 插入总述AVL树的插入过程与普通二叉搜索树的插入过程完全相同都是先找到合适的插入位置创建新节点并完成链接。不同之处在于AVL树插入新节点后需要从插入节点的父节点开始依次递归向上检查每个节点的平衡因子判断插入操作是否破坏了AVL树的平衡特性并同步更新平衡因子若平衡被破坏则需进行旋转调整。2. 平衡因子的更新与平衡判断平衡因子的更新从插入节点的父节点开始更新规则如下如果新节点插入在父节点的右子树则父节点的平衡因子加1如果插入在左子树则父节点的平衡因子减1。更新后父节点的平衡因子会出现以下几种变化情况对应不同的处理逻辑平衡因子从1或-1变为0说明该父节点所在子树的高度没有发生变化插入前子树高度差为1插入后高度差变为0整体高度不变。因此更上层父节点的左右子树高度均未改变平衡因子也不会受到影响平衡因子的更新过程在此停止。平衡因子从0变为1或-1说明该父节点所在子树的高度增加了1插入前子树高度平衡插入后高度差变为1。由于子树高度发生变化更上层父节点的左右子树高度差可能受到影响因此平衡因子需要继续向上更新。平衡因子从1或-1变为2或-2此时该父节点所在的子树已经失去平衡左右子树高度差的绝对值超过1需要通过旋转操作来恢复平衡。旋转的核心目的有两个① 使当前父节点的平衡因子恢复正常回到-1、0、1中的一种② 恢复当前子树的高度到插入前的状态。正因为旋转能恢复子树高度所以旋转后平衡因子的更新过程可以在此停止无需继续向上追溯。总结来说平衡因子的更新过程有三种停止情况更新到某个节点时其平衡因子的绝对值大于1通过旋转处理后更新过程结束更新到某个节点时其平衡因子变为0不会影响更上层节点更新过程结束最坏情况是更新到根节点只要根节点的平衡因子绝对值小于2更新过程即可结束。补充说明更上层父节点的平衡因子是否需要更新核心取决于当前插入节点所在子树的高度是否发生变化——子树高度不变则无需更新子树高度变化则需要继续更新。3. 插入代码实现bool Insert(const T data) { typedef AVLTreeNodeT Node; // 情况1树为空直接创建根节点 if (_root nullptr) { _root new Node(data); return true; } // 情况2树非空找到插入位置 Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_data data) { parent cur; cur cur-_right; } else if (cur-_data data) { parent cur; cur cur-_left; } else { // 插入的键值已存在插入失败 return false; } } // 创建新节点并与父节点建立链接 cur new Node(data); if (parent-_data data) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; // 链接父节点方便后续向上更新平衡因子 // 向上更新平衡因子并判断是否需要旋转 while (parent) { // 根据插入位置更新父节点的平衡因子 if (cur parent-_left) parent-_bf--; else parent-_bf; // 判断当前父节点所在子树是否失衡 if (parent-_bf 2 || 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) RotateLR(parent); // 左右双旋 else if (parent-_bf 2 cur-_bf -1) RotateRL(parent); // 右左双旋 else assert(false); // 异常情况断言报错 break; // 旋转后子树高度恢复停止更新 } else if (parent-_bf 0) { // 子树高度未变停止更新 break; } else if (parent-_bf 1 || parent-_bf -1) { // 子树高度变化继续向上更新 cur parent; parent parent-_parent; } } return true; }三旋转操作1. 旋转原则旋转是AVL树恢复平衡的核心操作其基本原则是在严格保证二叉搜索树规则左子树所有节点值小于根节点右子树所有节点值大于根节点的前提下使失衡的子树恢复平衡同时降低子树的高度确保后续操作的时间复杂度稳定在O(logN)。2. 右单旋RotateR1使用场景适用于父节点的平衡因子为-2且其左子树根节点的平衡因子为-1的情况即左子树过高且左子树的左子树也过高属于“左左”失衡。2操作步骤设当前失衡子树的根节点为P父节点P的左子树根节点为subLsubL的右子树为subLR。具体操作如下1. 让P成为subL的右子树根节点2. 让subLR成为P的左子树根节点3. 调整P、subL以及它们父节点的指针链接确保树的结构完整。3可行性分析从二叉搜索树的规则来看P以及P的右子树所有节点的值都大于subLsubLR所在子树的所有节点的值都小于P、大于subL。因此上述操作不会破坏二叉搜索树的规则是可行的。从平衡恢复和高度降低来看我们可以通过抽象场景理解假设以P此处抽象为10为根的子树中subL抽象为5的左子树a、subL的右子树b、P的右子树c均为高度为hh≥0的AVL树满足右单旋场景的前提是a、b、c高度均为h。P可能是整棵树的根也可能是某棵局部子树的根。当在a子树中插入一个新节点时a子树的高度从h变为h1向上更新平衡因子后P的平衡因子从-1变为-2此时P为根的子树左右高度差超过1出现失衡左边过高需要通过右单旋恢复平衡。旋转的核心逻辑的是由于5 b子树的值 10将b子树变为P10的左子树P10变为subL5的右子树subL5成为该子树新的根。这样的操作既符合二叉搜索树规则又能使子树恢复平衡同时子树的高度恢复到插入前的h2满足旋转原则。如果P原本是局部子树的根旋转后子树高度恢复不会影响更上层节点插入操作即可结束。4平衡因子更新右单旋操作后原父节点P和原左子树根节点subL的平衡因子都会恢复为0因为旋转后两者的左右子树高度差均为0。5代码实现void RotateR(Node* pParent) { Node* subL pParent-_left; Node* subLR subL-_right; // 第一步调整pParent和subLR的链接 pParent-_left subLR; // 若subLR不为空更新其parent指针指向pParent if (subLR) subLR-_parent pParent; // 第二步调整subL和pParent的链接 subL-_right pParent; Node* subP pParent-_parent; // 保存pParent的父节点 pParent-_parent subL; // 第三步调整subL与原pParent父节点的链接 if (pParent _root) { // 若pParent是根节点旋转后subL成为新根 _root subL; subL-_parent nullptr; } else { // 若pParent是局部子树的根根据其在父节点的左右位置链接subL if (subP-_left pParent) subP-_left subL; else subP-_right subL; subL-_parent subP; } // 更新平衡因子 subL-_bf 0; pParent-_bf 0; }3. 左单旋RotateL1使用场景适用于父节点的平衡因子为2且其右子树根节点的平衡因子为1的情况即右子树过高且右子树的右子树也过高属于“右右”失衡。2操作步骤设当前失衡子树的根节点为P父节点P的右子树根节点为subRsubR的左子树为subRL。具体操作如下1. 让P成为subR的左子树根节点2. 让subRL成为P的右子树根节点3. 调整P、subR以及它们父节点的指针链接确保树的结构完整。注左单旋的可行性、平衡因子更新逻辑与右单旋对称此处不再重复赘述核心是恢复右右失衡的子树平衡降低子树高度。4. 左右双旋RotateLR1使用场景适用于父节点的平衡因子为-2且其左子树根节点的平衡因子为1的情况即左子树过高但左子树的右子树过高属于“左右”失衡。此时单旋无法解决失衡问题需要先通过一次左单旋调整左子树结构再通过一次右单旋恢复整体平衡。2操作步骤设当前失衡子树的根节点为P父节点P的左子树根节点为subLsubL的右子树为subLR。具体操作分为两步1. 先对subL所在的子树进行左单旋将subLR提升为subL所在子树的根使P所在的子树变为“左左”失衡状态满足右单旋的适用场景2. 再对P所在的子树进行右单旋恢复整个子树的平衡。3平衡因子更新分场景讨论左右双旋的平衡因子更新取决于插入节点所在的位置即subLR的平衡因子具体分为3种场景场景1h ≥ 1时新增节点插入在subLR的左子树抽象为e子树e子树的高度从h-1变为h向上更新平衡因子8→5→10引发失衡。此时subLR的平衡因子为-1旋转后subL的平衡因子变为0subLR的平衡因子变为0P的平衡因子变为1。场景2h ≥ 1时新增节点插入在subLR的右子树抽象为f子树f子树的高度从h-1变为h向上更新平衡因子8→5→10引发失衡。此时subLR的平衡因子为1旋转后subL的平衡因子变为-1subLR的平衡因子变为0P的平衡因子变为0。场景3h 0时subL的左子树、subLR的左右子树、P的右子树抽象为a、b、c均为空树subLR本身就是新增节点向上更新平衡因子5→10引发失衡。此时subLR的平衡因子为0旋转后subL、subLR、P的平衡因子均变为0。4代码实现void RotateLR(Node* pParent) { Node* subL pParent-_left; Node* subLR subL-_right; int bf subLR-_bf; // 保存subLR的平衡因子用于后续更新 // 第一步对subL进行左单旋 RotateL(pParent-_left); // 第二步对pParent进行右单旋 RotateR(pParent); // 根据subLR的平衡因子更新三个节点的平衡因子 if (bf 0) { subL-_bf 0; subLR-_bf 0; pParent-_bf 0; } else if (bf 1) { subL-_bf -1; subLR-_bf 0; pParent-_bf 0; } else if (bf -1) { subL-_bf 0; subLR-_bf 0; pParent-_bf 1; } else { assert(false); // 异常情况断言报错 } }5. 右左双旋RotateRL1使用场景适用于父节点的平衡因子为2且其右子树根节点的平衡因子为-1的情况即右子树过高但右子树的左子树过高属于“右左”失衡。此时单旋无法解决失衡问题需要先通过一次右单旋调整右子树结构再通过一次左单旋恢复整体平衡。2操作步骤设当前失衡子树的根节点为P父节点P的右子树根节点为subRsubR的左子树为subRL。具体操作分为两步1. 先对subR所在的子树进行右单旋将subRL提升为subR所在子树的根使P所在的子树变为“右右”失衡状态满足左单旋的适用场景2. 再对P所在的子树进行左单旋恢复整个子树的平衡。注右左双旋的可行性、平衡因子更新逻辑与左右双旋对称核心是恢复右左失衡的子树平衡降低子树高度此处不再重复赘述。
)
