目录1. AVL树的概念2. AVL树的实现2.1 AVL树的结构2.2 插入的代码实现2.3 四种旋转操作1. 右单旋2. 左单旋3. 左右双旋4. 右左双旋5. 什么时机调用3. AVL树的查找平衡检测删除1. AVL树的概念定义一种自平衡的二叉搜索树BST。命名来源由 G.M. Adelson-Velsky 和 E.M. Landis 发明。核心特性平衡因子 Balance Factor, BFBF 右子树高度 - 左子树高度也可以左子树高度 - 右子树高度严格要求对于任意节点|BF| 1即只能是 -1, 0, 1。为何需要 AVL解决普通二叉搜索树在极端情况下如插入有序数据退化成链表的问题将查找、插入、删除的时间复杂度严格控制在O(log n)。注AVL树不是必须要平衡因子但有了平衡因子可以方便我们观察和控制树是否平衡。2. AVL树的实现2.1 AVL树的结构节点定义templateclass K, class V struct AVLTreeNode{ AVLTreeNodeK, V* _parent; // 父节点指针 AVL 树在插入/删除后必须向上回溯检查平衡因子并可能旋转 AVLTreeNodeK, V* _left; // 左孩子指针 AVLTreeNodeK, V* _right; // 右孩子指针 int _bf; // 平衡因子 pairK, V _kv; // 存储的键值对数据 AVLTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} };2.2 插入的代码实现// 约定_bf 右子树高度 - 左子树高度 // 左高则 _bf 为负右高则 _bf 为正 bool Insert(const pairK,V kv){ // 情况 0空树新节点直接当根 if (_root nullptr) { _root new Node(kv); return true; // 根节点 _bf 默认为 0 } // 1. 二叉搜索树查找插入位置 Node* parent nullptr; Node* cur _root; while (cur) { if (kv.first cur-_kv.first) { parent cur; cur cur-_left; } else if (kv.first cur-_kv.first) { parent cur; cur cur-_right; } else return false; } // 退出循环时 cur nullptrparent指向新节点应该挂靠的父节点 // 2. 插入新节点并挂到parent下面 cur new Node(kv); cur-_parent parent; if (parent-_kv.first kv.first) { parent-_left cur; } else parent-_right cur; // 3. 更新平衡因子 while (parent) { // 3.1 先计算平衡因子 if (cur parent-_left) parent-_bf - 1; else parent-_bf 1; // 3.2 根据平衡因子判断是否平衡 if (parent-_bf 0) break; else if (parent-_bf 1 || parent-_bf -1){ cur parent; parent parent-_parent; } else if (parent-_bf 2 || parent-_bf -2){ // 当平衡因子是-2/2时说明不平衡了要进行旋转 // 旋转 break; } else{ assert(false); } } return true; }步骤拆解0. 空树新节点直接当根1. 二叉搜索树查找插入位置2. 创建新节点并挂到 parent 下面3. 从新节点出发向上回溯更新平衡因子必要时旋转cur 刚刚引起子树高度变化的那个节点孩子parent cur 的父节点当前要检查 _bf 的祖先更新规则_bf 右高 - 左高新节点插在 parent 左子树 → parent-_bf 右高 - (左高 1) →parent-_bf - 1;新节点插在 parent 右子树 → parent-_bf (右高 1) - 左高 →parent-_bf 1;三种结果的处理_bf 0 左右再次等高子树高度没变 → 向上无影响停止_bf ±1 一边变高子树高度 1 → 继续向上回溯_bf ±2 失衡 → 旋转修复修复后高度回到插入前停止2.3 四种旋转操作旋转的原则保持搜索树的规则旋转之后树变平衡同时降低树的高度当插入导致某节点 _bf 变为±2时需要通过旋转恢复平衡。共有 4 种情形1. 右单旋// 右单旋 void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; Node* parentParent parent-_parent; if (parent _root) { _root subL; } else { if (parent parentParent-_left) parentParent-_left subL; else parentParent-_right subL; } subL-_parent parentParent; parent-_left subLR; if (subLR) subLR-_parent parent; subL-_right parent; parent-_parent subL; // 更新平衡因子 parent-_bf 0; subL-_bf 0; }2. 左单旋左单旋思路同上代码展示// 左单旋 void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; Node* parentParent parent-_parent; if (parent _root) { _root subR; } else { if (parent parentParent-_left) parentParent-_left subR; else parentParent-_right subR; } subR-_parent parentParent; parent-_right subRL; if(subRL) subRL-_parent parent; subR-_left parent; parent-_parent subR; // 更新平衡因子 subR-_bf 0; parent-_bf 0; }3. 左右双旋先左单旋再右单旋// 左右双旋先左单旋后右双旋 void RotateLR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; // 【最重要的一步】在旋转前把最初的平衡因子记录下来因为右单旋和左单旋都将平衡因子改为了0 int bf subLR-_bf; RotateL(parent-_left); RotateR(parent); // 更新平衡因子 if (bf -1) { subL-_bf 0; parent-_bf 1; subLR-_bf 0; } else if (bf 1) { subL-_bf -1; parent-_bf 0; subLR-_bf 0; } else if (bf 0) { subL-_bf 0; parent-_bf 0; subLR-_bf 0; } else { assert(false); } }4. 右左双旋思路同上代码void RotateRL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; int bf subRL-_bf; RotateR(parent-_right); RotateL(parent); if (bf 0) { subR-_bf 0; parent-_bf 0; subRL-_bf 0; } else if (bf -1) { subR-_bf 1; parent-_bf 0; subRL-_bf 0; } else if (bf 1) { subR-_bf 0; parent-_bf -1; subRL-_bf 0; } else { assert(false); } }5. 什么时机调用平衡因子同号的时候调用左/右单旋平衡因子异号的时候调用左右/右左双旋else if (parent-_bf 2 || parent-_bf -2) { // 旋转 if (cur-_bf -1 parent-_bf -2) { RotateR(parent); } else if (cur-_bf 1 parent-_bf 2) { RotateL(parent); } else if (cur-_bf 1 parent-_bf -2) { RotateLR(parent); } else if (cur-_bf -1 parent-_bf 2) { RotateRL(parent); } break; }3. AVL树的查找平衡检测删除查找的代码与二叉搜索树的一致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; } } return nullptr; }平衡检测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) { if (root nullptr) return true; int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff rightHeight - leftHeight; // 不要写成 leftHeight - rightHeight; 因为我的插入的代码里我的平衡因子是按 右高-左高 来的 if (abs(diff) 2) { cout root-_kv.first 高度差异常 endl; return false; } if (diff ! root-_bf) { cout root-_kv.first 平衡因子异常 endl; return false; } return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); }这里删除不做详解了解AVL树的底层逻辑即可。
目录1. AVL树的概念2. AVL树的实现2.1 AVL树的结构2.2 插入的代码实现2.3 四种旋转操作1. 右单旋2. 左单旋3. 左右双旋4. 右左双旋5. 什么时机调用3. AVL树的查找平衡检测删除1. AVL树的概念定义一种自平衡的二叉搜索树BST。命名来源由 G.M. Adelson-Velsky 和 E.M. Landis 发明。核心特性平衡因子 Balance Factor, BFBF 右子树高度 - 左子树高度也可以左子树高度 - 右子树高度严格要求对于任意节点|BF| 1即只能是 -1, 0, 1。为何需要 AVL解决普通二叉搜索树在极端情况下如插入有序数据退化成链表的问题将查找、插入、删除的时间复杂度严格控制在O(log n)。注AVL树不是必须要平衡因子但有了平衡因子可以方便我们观察和控制树是否平衡。2. AVL树的实现2.1 AVL树的结构节点定义templateclass K, class V struct AVLTreeNode{ AVLTreeNodeK, V* _parent; // 父节点指针 AVL 树在插入/删除后必须向上回溯检查平衡因子并可能旋转 AVLTreeNodeK, V* _left; // 左孩子指针 AVLTreeNodeK, V* _right; // 右孩子指针 int _bf; // 平衡因子 pairK, V _kv; // 存储的键值对数据 AVLTreeNode(const pairK, V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _bf(0) {} };2.2 插入的代码实现// 约定_bf 右子树高度 - 左子树高度 // 左高则 _bf 为负右高则 _bf 为正 bool Insert(const pairK,V kv){ // 情况 0空树新节点直接当根 if (_root nullptr) { _root new Node(kv); return true; // 根节点 _bf 默认为 0 } // 1. 二叉搜索树查找插入位置 Node* parent nullptr; Node* cur _root; while (cur) { if (kv.first cur-_kv.first) { parent cur; cur cur-_left; } else if (kv.first cur-_kv.first) { parent cur; cur cur-_right; } else return false; } // 退出循环时 cur nullptrparent指向新节点应该挂靠的父节点 // 2. 插入新节点并挂到parent下面 cur new Node(kv); cur-_parent parent; if (parent-_kv.first kv.first) { parent-_left cur; } else parent-_right cur; // 3. 更新平衡因子 while (parent) { // 3.1 先计算平衡因子 if (cur parent-_left) parent-_bf - 1; else parent-_bf 1; // 3.2 根据平衡因子判断是否平衡 if (parent-_bf 0) break; else if (parent-_bf 1 || parent-_bf -1){ cur parent; parent parent-_parent; } else if (parent-_bf 2 || parent-_bf -2){ // 当平衡因子是-2/2时说明不平衡了要进行旋转 // 旋转 break; } else{ assert(false); } } return true; }步骤拆解0. 空树新节点直接当根1. 二叉搜索树查找插入位置2. 创建新节点并挂到 parent 下面3. 从新节点出发向上回溯更新平衡因子必要时旋转cur 刚刚引起子树高度变化的那个节点孩子parent cur 的父节点当前要检查 _bf 的祖先更新规则_bf 右高 - 左高新节点插在 parent 左子树 → parent-_bf 右高 - (左高 1) →parent-_bf - 1;新节点插在 parent 右子树 → parent-_bf (右高 1) - 左高 →parent-_bf 1;三种结果的处理_bf 0 左右再次等高子树高度没变 → 向上无影响停止_bf ±1 一边变高子树高度 1 → 继续向上回溯_bf ±2 失衡 → 旋转修复修复后高度回到插入前停止2.3 四种旋转操作旋转的原则保持搜索树的规则旋转之后树变平衡同时降低树的高度当插入导致某节点 _bf 变为±2时需要通过旋转恢复平衡。共有 4 种情形1. 右单旋// 右单旋 void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; Node* parentParent parent-_parent; if (parent _root) { _root subL; } else { if (parent parentParent-_left) parentParent-_left subL; else parentParent-_right subL; } subL-_parent parentParent; parent-_left subLR; if (subLR) subLR-_parent parent; subL-_right parent; parent-_parent subL; // 更新平衡因子 parent-_bf 0; subL-_bf 0; }2. 左单旋左单旋思路同上代码展示// 左单旋 void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; Node* parentParent parent-_parent; if (parent _root) { _root subR; } else { if (parent parentParent-_left) parentParent-_left subR; else parentParent-_right subR; } subR-_parent parentParent; parent-_right subRL; if(subRL) subRL-_parent parent; subR-_left parent; parent-_parent subR; // 更新平衡因子 subR-_bf 0; parent-_bf 0; }3. 左右双旋先左单旋再右单旋// 左右双旋先左单旋后右双旋 void RotateLR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; // 【最重要的一步】在旋转前把最初的平衡因子记录下来因为右单旋和左单旋都将平衡因子改为了0 int bf subLR-_bf; RotateL(parent-_left); RotateR(parent); // 更新平衡因子 if (bf -1) { subL-_bf 0; parent-_bf 1; subLR-_bf 0; } else if (bf 1) { subL-_bf -1; parent-_bf 0; subLR-_bf 0; } else if (bf 0) { subL-_bf 0; parent-_bf 0; subLR-_bf 0; } else { assert(false); } }4. 右左双旋思路同上代码void RotateRL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; int bf subRL-_bf; RotateR(parent-_right); RotateL(parent); if (bf 0) { subR-_bf 0; parent-_bf 0; subRL-_bf 0; } else if (bf -1) { subR-_bf 1; parent-_bf 0; subRL-_bf 0; } else if (bf 1) { subR-_bf 0; parent-_bf -1; subRL-_bf 0; } else { assert(false); } }5. 什么时机调用平衡因子同号的时候调用左/右单旋平衡因子异号的时候调用左右/右左双旋else if (parent-_bf 2 || parent-_bf -2) { // 旋转 if (cur-_bf -1 parent-_bf -2) { RotateR(parent); } else if (cur-_bf 1 parent-_bf 2) { RotateL(parent); } else if (cur-_bf 1 parent-_bf -2) { RotateLR(parent); } else if (cur-_bf -1 parent-_bf 2) { RotateRL(parent); } break; }3. AVL树的查找平衡检测删除查找的代码与二叉搜索树的一致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; } } return nullptr; }平衡检测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) { if (root nullptr) return true; int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff rightHeight - leftHeight; // 不要写成 leftHeight - rightHeight; 因为我的插入的代码里我的平衡因子是按 右高-左高 来的 if (abs(diff) 2) { cout root-_kv.first 高度差异常 endl; return false; } if (diff ! root-_bf) { cout root-_kv.first 平衡因子异常 endl; return false; } return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); }这里删除不做详解了解AVL树的底层逻辑即可。
知识建站
内容驱动
阅读友好版式
SEO 精细化
线索转化