我们学习了二叉搜索树但它存在一个致命缺陷 —— 极端情况下会退化为单支树导致增删查效率从 O(logN) 退化到 O(N)。今天我们就来学习解决这个问题的方案 ——AVL 树它是最早的自平衡二叉搜索树通过自动调整结构保持平衡确保高效操作。一、AVL 树的概念AVL 树是一种自平衡二叉搜索树得名于发明者 G. M. Adelson-Velsky 和 E. M. Landis1962 年提出。它的核心定义的是要么是一棵空树要么左右子树都是 AVL 树且左右子树的高度差的绝对值不超过 1。关键概念平衡因子Balance Factor, BF为了方便判断树的平衡状态我们给每个节点引入平衡因子平衡因子 右子树高度 - 左子树高度一般情况下是这个也可以左-右合法的 AVL 树节点平衡因子只能是-1、0、1对应左子树高、左右等长、右子树高。AVL 树的核心价值AVL 树的高度能稳定控制在 logN 级别与完全二叉树类似因此增删查改的时间复杂度始终保持 O(logN)从根本上解决了普通二叉搜索树的退化问题。二、AVL树的实现AVL树的结构templateclass K, class V struct AVLTreeNode { pairK, V _kv; AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; AVLTreeNodeK, V* _parent;// 需要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* _rootnullptr; };AVL树的插⼊AVL树插⼊⼀个值的⼤概过程1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。2. 新增结点以后只会影响祖先结点的⾼度也就是可能会影响部分祖先结点的平衡因⼦所以更新 从新增结点-根结点路径上的平衡因⼦实际中最坏情况下要更新到根有些情况更新到中间就可 以停⽌了具体情况我们下⾯再详细分析。3. 更新平衡因⼦过程中没有出现问题则插⼊结束。4. 更新平衡因⼦过程中出现不平衡对不平衡⼦树旋转旋转后本质调平衡的同时本质降低了⼦树 的⾼度不会再影响上⼀层所以插⼊结束。平衡因⼦更新1.平衡因⼦右⼦树⾼度-左⼦树⾼度2.只有⼦树⾼度变化才会影响当前结点平衡因⼦。3. 插⼊结点会增加⾼度所以新增结点在parent的右⼦树parent的平衡因⼦新增结点在 parent的左⼦树parent平衡因⼦--。4. parent所在⼦树的⾼度是否变化决定了是否会继续往上更新。更新停⽌条件1.更新后的parent的平衡因子为0说明它的高度不变。2.更新后的parent的平衡因子为1或-1就要继续往上更新。3.更新后的parent的平衡因子为-2或2说明破坏了平衡parent所在的⼦树不符合平衡要求需要旋转处理旋转的⽬标有两个1、把 parent⼦树旋转平衡。2、降低parent⼦树的⾼度恢复到插⼊结点以前的⾼度。所以旋转后也不 需要继续往上更新插⼊结束。4.不断更新更新到根跟的平衡因⼦是1或-1也停⽌了。示例1.更新到中间结点3为根的⼦树⾼度不变不会影响上⼀层更新结束。2.最坏情况更新到根节点为止。3.更新到10结点平衡因⼦为210所在的⼦树已经不平衡需要旋转处理。插入及平衡因子更新的代码实现#includeiostream #includeassert.h using namespace std; templateclass K,class V struct AVLTreeNode { pairK, V _kv; AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right; AVLTreeNodeK, V* _parent; int _bf;//平衡因子 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: bool insert(const pairK, V kv) { if (_root nullptr) { _root new Node(kv); return true; } Node* parent nullptr; Node* cur _root; while (cur) { if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_right; } else { return false; } } cur new Node(kv); if (parent-_kv.first kv.first) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent;//链接父亲 //控制平衡更新平衡因子 while (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); } } return true; } private: Node* _root nullptr; };旋转1.保持搜索树的规则。2.让旋转的树从不满⾜变平衡其次降低旋转树的⾼度。旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋。右单旋情况1情况2插入一个-2节点在左子树并更新平衡因子以10为旋转点进行右旋8成为10的左子树10变成5的右子树5成为这棵树新的根。代码实现void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; //记录父亲的父亲节点 Node* Pparent parent-_parent; subL-_right parent; parent-_parentsubL; if (parent _root) { _root subL; subL-_parent nullptr; } else { if (Pparent-_left parent) { Pparent-_left subL; } else { Pparent-_right subL; } subL-_parent Pparent; } //更新平衡因子 parent-_bf subL-_bf 0; }左单旋情况1插入一个10节点在右子树并更新平衡因子以节点6为旋转节点向左旋转将3设为6的左子树。情况2插入一个14节点在右子树并更新平衡因子以6为旋转点进行左旋8成为6的右子树6变成10的右子树10成为这棵树新的根。代码实现void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) subRL-_parent parent; Node* Pparent parent-_parent; subR-_left parent; parent-_parent subR; if (Pparent nullptr) { _rootsubR; subR-_parent nullptr; } else { if (Pparent-_left parent) { Pparent-_left subR; } else { Pparent-_right subR; } subR-_parent Pparent; } parent-_bf subR-_bf 0; }左右双旋下面两个例子可以看到左边⾼时如果插⼊位置不是在a⼦树⽽是插⼊在b⼦树b⼦树⾼度从h变 成h1引发旋转右单旋⽆法解决问题右单旋后我们的树依旧不平衡。右单旋解决的纯粹的左边 ⾼但是插⼊在b⼦树中10为跟的⼦树不再是单纯的左边⾼对于10是左边⾼但是对于5是右边 ⾼需要⽤两次旋转才能解决以5为旋转点进⾏⼀个左单旋以10为旋转点进⾏⼀个右单旋这棵树 这棵树就平衡了。上面两张图分别为左右双旋中h0和h1具体场景分析下⾯我们将a/b/c⼦树抽象为⾼度h的AVL ⼦树进⾏分析另外我们需要把b⼦树的细节进⼀步展开为8和左⼦树⾼度为h-1的e和f⼦树因为 我们要对b的⽗亲5为旋转点进⾏左单旋左单旋需要动b树中的左⼦树。b⼦树中新增结点的位置 不同平衡因⼦更新的细节也不同通过观察8的平衡因⼦不同这⾥我们要分三个场景讨论。• 场景1h1时新增结点插⼊在e⼦树e⼦树⾼度从h-1并为h并不断更新8-5-10平衡因⼦ 引发旋转其中8的平衡因⼦为-1旋转后8和5平衡因⼦为010平衡因⼦为1。• 场景2h1时新增结点插⼊在f⼦树f⼦树⾼度从h-1变为h并不断更新8-5-10平衡因⼦引 发旋转其中8的平衡因⼦为1旋转后8和10平衡因⼦为05平衡因⼦为-1。• 场景3h0时a/b/c都是空树b⾃⼰就是⼀个新增结点不断更新5-10平衡因⼦引发旋 转其中8的平衡因⼦为0旋转后8和10和5平衡因⼦均为0。代码实现void RotateLR(Node* parent) { //提前记录平衡因子 Node* subL parent-_left; Node* subLR subL-_right; int bf subLR-_bf; RotateL(parent-_left); RotateR(parent); if (bf -1) { subLR-_bf 0; subL-_bf 0; parent-_bf 1; } else if (bf 1) { subLR-_bf 0; subL-_bf -1; parent-_bf 0; } else if (bf 0) { subLR-_bf 0; subL-_bf 0; parent-_bf 0; } else { assert(false); } }右左双旋右左双旋逻辑跟左右双旋一样只不过方向不同就不再演示。代码实现void RotateRL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; int bf subRL-_bf; RotateR(parent-_right); RotateL(parent); if (bf -1) { subRL-_bf 0; subR-_bf 1; parent-_bf 0; } else if (bf 1) { subRL-_bf 0; subR-_bf 0; parent-_bf -1; } else if (bf 0) { subRL-_bf 0; subR-_bf 0; parent-_bf 0; } else { assert(false); } }三、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; }四、AVL树的平衡检测我们实现的AVL树是否合格我们通过检查左右⼦树⾼度差的的程序进⾏反向验证同时检查⼀下结点 的平衡因⼦更新是否出现了问题。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; } bool _IsBalanceTree(Node* root) { if (root nullptr) return true; int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff rightHeight - leftHeight; if (abs(diff) 2) { cout 高度差异常 endl; return false; } if (root-_bf ! diff) { cout 平衡因子异常 endl; return false; } return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right); }五、AVL 树特点总结严格平衡任何节点左右高度差 ≤ 1查询极快O(log n)插入删除代价稍高需要频繁旋转适合读多写少的场景如数据库索引、内存缓存