【C++进阶】AVL树实现

目录本节学习目标1 AVL 树概念平衡因子 balance factor_bfAVL 性能2 AVL 树结点结构2.2 AVL 树插入流程平衡因子更新规则更新停止三种情况Insert 插入核心代码3 AVL 四种旋转操作3.1 右单旋 RotateRLL左左3.2 左单旋 RotateLRR右右3.3 左右双旋 RotateLRLR左右3.4 右左双旋 RotateRLRL右左插入末尾旋转判断逻辑补充到 Insert 函数末尾4 AVL 查找5 AVL 树平衡校验函数调试必备6 测试示例本篇核心考点总结本节学习目标理解 AVL 树高度平衡二叉搜索树概念、平衡因子定义掌握 AVL 树结点结构parent 父指针、平衡因子_bf作用掌握 AVL 插入完整流程BST 插入、更新平衡因子、判断失衡吃透 4 种旋转右单旋、左单旋、左右双旋、右左双旋每种旋转的触发条件、指针修改、平衡因子修正看懂旋转完整 C 实现代码理解旋转不仅要改孩子还要维护_parent父指针掌握 AVL 树查找掌握平衡校验函数验证 AVL 树是否合法了解 AVL 树性能、缺点对比后续红黑树1 AVL 树概念AVL 树是最早发明的自平衡二叉搜索树由前苏联科学家 G. M. Adelson‑Velsky 和 E. M. Landis 在 1962 年发表。AVL 树定义一棵空树或者左右子树都是 AVL 树左右子树高度差的绝对值不超过 1。平衡因子 balance factor_bf平衡因子公式\(\boldsymbol{bf 右子树高度 - 左子树高度}\) 合法 AVL 结点平衡因子只能取‑1、0、1。bf 1右子树更高bf 0左右子树等高bf ‑1左子树更高思考为什么要求高度差≤1而不是强制高度差等于 0 有些结点数量无法做到左右完全等高。例如 2 个结点、4 个结点理论上做不到左右高度完全一样最多只能做到高度差 1。AVL 性能结点分布接近完全二叉树树高度 \(h \approx log_2N\)。 增、删、查时间复杂度\(\boldsymbol{O(logN)}\)解决普通 BST 有序数据插入退化成链表\(O(N)\)的问题。缺点AVL 为了严格平衡插入删除会频繁触发旋转实际工程中红黑树使用更多红黑树放松平衡条件旋转次数更少。2 AVL 树结点结构每个结点需要键值对_kv、左孩子_left、右孩子_right、父结点指针_parent、平衡因子_bf。parent 父指针非常关键更新平衡因子、旋转的时候向上回溯祖先结点。templateclass K, class V struct AVLTreeNode { 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; };2.2 AVL 树插入流程插入三大步骤按照普通二叉搜索树 BST 规则插入新结点从新结点向上回溯更新沿途祖先结点平衡因子更新平衡因子过程判断更新后 bf 为 0子树高度不再变化停止向上更新更新后 bf 为 1/-1子树高度 1继续向上更新祖先更新后 bf 为 2/-2发生失衡执行旋转旋转完成后子树高度恢复插入前高度不需要继续向上更新插入结束。平衡因子更新规则更新到10结点平衡因⼦为210所在的⼦树已经不平衡需要旋转处理更新到中间结点3为根的⼦树⾼度不变不会影响上⼀层更新结束最坏更新到根停⽌新增结点在 parent 的右子树→ parent-_bf 新增结点在 parent 的左子树→ parent-_bf --。更新停止三种情况更新后parent-_bf 0变化‑1 → 0或者1 →0 含义插入补全矮的那一侧这棵子树整体高度不变不会继续影响上层祖先循环 break 结束。更新后parent-_bf 1 || parent-_bf -1变化0 →10→‑1 含义原来左右等高插入后一侧变高子树整体高度 1继续向上更新父结点。更新后parent-_bf 2 || parent-_bf -2含义高度差超过 1树失衡执行旋转修复平衡旋转后子树高度复原不需要继续向上break 结束循环。Insert 插入核心代码bool Insert(const pairK, V kv) { if (_root nullptr) { _root new Node(kv); return true; } Node* parent nullptr; Node* cur _root; //BST查找插入位置 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 { //key已经存在插入失败 return false; } } //创建新结点挂到parent下面 cur new Node(kv); if (parent-_kv.first kv.first) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; //向上更新平衡因子 while (parent) { //判断cur是parent的左还是右孩子 if (cur parent-_left) parent-_bf--; else parent-_bf; 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) { //失衡需要旋转旋转后直接结束插入 break; } else { assert(false); //非法bf } } //【此处省略判断parent的bf调用对应旋转函数】 return true; }3 AVL 四种旋转操作旋转两个核心目标维持二叉搜索树性质中序有序修复平衡把该局部子树高度恢复为插入之前的高度不再向上传播失衡。四种旋转右单旋RotateRparent 平衡因子‑2左子树的左子树过高LL 场景左单旋RotateLparent 平衡因子2右子树的右子树过高RR 场景左右双旋RotateLRparent bf‑2左子树的右子树过高LR 场景右左双旋RotateRLparent bf2右子树的左子树过高RL 场景⚠️旋转注意点不光修改孩子指针所有结点的_parent 父指针必须同步更新还要区分旋转结点是不是整棵树的根结点需要更新_root。3.1 右单旋 RotateRLL左左触发条件parent 的 bf-2parent 的左孩子 subL 的 bf -1左子树的左分支太高。图解逻辑 parent 为旋转根subL parent-_leftsubLR subL-_right。parent-_left subLR如果 subLR 不为空subLR-_parent parentsubL 接管 parentsubL-_right parentparent-_parent subL处理 subL 的父结点如果 parent 原来是根_root subL否则把上层 parentParent 的孩子指向 subL重置平衡因子旋转之后parent-_bf 0subL-_bf 0。void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if(subLR ! nullptr) { subLR-_parent parent; } Node* parentParent parent-_parent; subL-_right parent; parent-_parent subL; //修改上层的指向 if(parentParent nullptr) { _root subL; subL-_parent nullptr; } else { if(parent parentParent-_left) { parentParent-_left subL; } else { parentParent-_right subL; } subL-_parent parentParent; } //旋转后平衡因子置0 parent-_bf 0; subL-_bf 0; }3.2 左单旋 RotateLRR右右触发条件parent 的 bf2parent 右孩子 subR 的 bf1右子树的右分支太高。void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if(subRL ! nullptr) { subRL-_parent parent; } Node* parentParent parent-_parent; subR-_left parent; parent-_parent subR; if(parentParent nullptr) { _root subR; subR-_parent nullptr; } else { if(parent parentParent-_left) { parentParent-_left subR; } else { parentParent-_right subR; } subR-_parent parentParent; } parent-_bf 0; subR-_bf 0; }3.3 左右双旋 RotateLRLR左右触发条件parent 的 bf-2parent 左孩子 subL 的 bf 1。 现象parent 左子树高但高出来的部分在左孩子的右子树单纯右单旋无法修复需要两次旋转。操作顺序先对parent-_left执行左单旋 RotateL再对 parent 执行右单旋 RotateR注意中间结点subLR旋转前的平衡因子bf会影响旋转结束之后三个结点 (parent、subL、subLR) 最终平衡因子分三种情况处理。bf 0插入的结点就是 subLR 本身旋转完三者全部 bf0。bf -1新结点插入 subLR 的左子树bf 1新结点插入 subLR 的右子树。void RotateLR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; int bf subLR-_bf; RotateL(parent-_left); RotateR(parent); if(bf 0) { subL-_bf 0; subLR-_bf 0; parent-_bf 0; } else if(bf -1) { subL-_bf 0; subLR-_bf 0; parent-_bf 1; } else if(bf 1) { subL-_bf -1; subLR-_bf 0; parent-_bf 0; } else { assert(false); } }3.4 右左双旋 RotateRLRL右左触发条件parent bf2parent 右孩子 subR 的 bf-1高的部分出现在右孩子的左子树。 操作顺序对parent-_right执行右单旋 RotateR再对 parent 执行左单旋 RotateL 同样依据中间结点subRL旋转前的 bf 分三种情况修正平衡因子。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; subRL-_bf 0; parent-_bf 0; } else if(bf 1) { subR-_bf 0; subRL-_bf 0; parent-_bf -1; } else if(bf -1) { subR-_bf 1; subRL-_bf 0; parent-_bf 0; } else { assert(false); } }插入末尾旋转判断逻辑补充到 Insert 函数末尾在 Insert 的 while 循环 break 之后根据 parent 的 bf 以及孩子的 bf判断四种旋转中哪一种if(parent ! nullptr) { if(parent-_bf -2) { Node* subL parent-_left; if(subL-_bf -1) { RotateR(parent); //LL右单旋 } else if(subL-_bf 1) { RotateLR(parent); //LR左右双旋 } } else if(parent-_bf 2) { Node* subR parent-_right; if(subR-_bf 1) { RotateL(parent); //RR左单旋 } else if(subR-_bf -1) { RotateRL(parent); //RL右左双旋 } } } return true;4 AVL 查找复用普通二叉搜索树查找逻辑\(O(logN)\)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; }5 AVL 树平衡校验函数调试必备递归计算子树高度做两件校验检查当前结点左右子树高度差绝对值不能≥2校验代码保存的_bf平衡因子是否等于真实计算出来的右高‑左高排查更新 bf 的 bug。//递归求子树高度 int _Height(Node* root) { if(root nullptr) return 0; int leftH _Height(root-_left); int rightH _Height(root-_right); return max(leftH, rightH) 1; } bool _IsBalanceTree(Node* root) { if(root nullptr) return true; int leftH _Height(root-_left); int rightH _Height(root-_right); int realBf rightH - leftH; //高度差超标 if(abs(realBf) 2) { cout root-_kv.first 高度差异常 endl; return false; } //代码记录的bf和实际计算不匹配 if(root-_bf ! realBf) { cout root-_kv.first 平衡因子错误记录bf: root-_bf 实际bf: realBf endl; return false; } //递归校验左右子树 return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); } //对外接口 bool IsBalanceTree() { return _IsBalanceTree(_root); }6 测试示例void TestAVLTree1() { AVLTreeint,int t; //双旋测试用例 int a[] {4,2,6,1,3,5,15,7,16,14}; for(auto e : a) { t.Insert({e,e}); } //中序遍历BST必须升序 t.InOrder(); //校验是否是合法AVL cout isBalance: t.IsBalanceTree() endl; }课件说明AVL 删除操作本课件不做实现删除逻辑更复杂需要多次旋转实际工程很少手写 AVLSTL 底层用红黑树。本篇核心考点总结AVL 是高度平衡 BST左右子树高度差绝对值 ≤1平衡因子\(bf 右子树高度‑左子树高度\)合法取值‑1、0、1。AVL 结点必须带_parent父指针用于插入之后向上回溯更新平衡因子。插入流程BST 插入新结点→向上更新祖先 bf根据 bf 值决定停止 / 继续向上 / 触发旋转旋转修复失衡后不再向上传播。4 种旋转LLbf-2subL-_bf-1右单旋 RotateRRRbf2subR-_bf1左单旋 RotateLLRbf-2subL-_bf1左右双旋 RotateLR先左后右RLbf2subR-_bf-1右左双旋 RotateRL先右后左⚠️旋转不仅修改孩子指针所有结点_parent 父指针必须同步维护区分是否为整棵树根结点需要修改_root双旋结束要根据中间结点原始 bf 修正三个结点平衡因子。校验函数递归计算真实子树高度校验高度差、校验保存的平衡因子和真实 bf 是否一致调试排错。AVL 严格平衡旋转频繁性能理论\(O(logN)\)工程中红黑树应用更广。面试简答QAV 平衡因子怎么计算合法取值Abf 右子树高度‑左子树高度合法只能是‑1、0、1。QLL LR RR RL 四种旋转分别什么场景触发ALL 左子树的左分支高右单旋LR 左子树的右分支高左右双旋RR 右子树的右分支高左单旋RL 右子树的左分支高右左双旋。QAVL 和红黑树对比AAVL 严格高度差≤1查找快插入删除旋转次数多开销大红黑树放宽平衡条件旋转更少综合性能更好STL map/set 底层采用红黑树。