一、 什么是AVL树AVL树是最先发明的自平衡二叉查找树Self-balancing Binary Search Tree。它由前苏联科学家 G.M. Adelson-Velsky 和 E.M. Landis 在1962年的论文中提出。AVL树的定义它是一棵空树或者具备以下性质的二叉搜索树它的左右子树都是AVL树。左右子树的高度差的绝对值不超过1。为什么需要AVL树普通的二叉搜索树在极端情况下如插入有序序列会退化成链表导致增删查改效率降为 O(N)。AVL树通过控制高度差将树的高度严格控制在 logN 级别从而保证了所有操作的时间复杂度均为 O(logN)。平衡因子Balance Factor为了更方便地观察和控制树的平衡AVL树引入了平衡因子bf的概念平衡因子 右子树高度 - 左子树高度任何结点的平衡因子只能是0、1 或 -1。思考为什么高度差不超过1而不是0因为有些情况无法做到高度差为0例如只有2个结点或4个结点的树高度差最好就是1因此绝对值不超过1是理论上的最优解。二、 AVL树的结构设计在实现AVL树时我们需要在二叉搜索树结点的基础上增加两个成员_bf平衡因子。_parent指向父结点的指针用于插入后向上回溯更新平衡因子。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) {} };三、 AVL树的插入核心难点3.1 插入的大概过程AVL树的插入主要分为以下四个步骤按二叉搜索树的规则插入新结点。新增结点后只会影响祖先结点的高度因此需要从新增结点到根结点路径上更新平衡因子。最坏情况下要更新到根有些情况更新到中间就可以停止。更新平衡因子过程中没有出现问题则插入结束。更新平衡因子过程中出现不平衡对不平衡子树进行旋转。旋转在调平衡的同时本质降低了子树的高度不会再影响上一层所以插入结束。3.2 平衡因子的更新更新原则平衡因子 右子树高度 - 左子树高度。只有子树高度变化才会影响当前结点平衡因子。插入结点会增加高度新增结点在 parent 的右子树parent 的平衡因子新增结点在 parent 的左子树parent 平衡因子--。parent 所在子树的高度是否变化决定了是否会继续往上更新。更新停止条件更新后 parent 的平衡因子等于 0变化为 -1-0 或 1-0说明更新前 parent 子树一边高一边低新增结点插在低的那边插入后 parent 所在子树高度不变不影响父结点更新结束。更新后 parent 的平衡因子等于 1 或 -1变化为 0-1 或 0--1说明更新前 parent 子树两边一样高插入后一边高一边低parent 子树符合平衡要求但高度增加了 1会影响父结点需要继续向上更新。更新后 parent 的平衡因子等于 2 或 -2变化为 1-2 或 -1--2说明更新前 parent 子树一边高一边低新增结点插在高的一边破坏了平衡需要旋转处理。旋转的目标有两个把 parent 子树旋转平衡降低 parent 子树的高度恢复到插入以前的高度。旋转后不需要继续往上更新插入结束。不断更新到根根的平衡因子是 1 或 -1 也停止。3.3 插入结点及更新平衡因子的代码实现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-_right; } else if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } 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; }四、 旋转4.1 旋转的原则保持搜索树的规则。让旋转的树从不满⾜变平衡其次降低旋转树的高度。旋转总共分为四种左单旋、右单旋、左右双旋、右左双旋。4.2 右单旋以 10 为根的树a/b/c 抽象为三棵高度为 h 的子树h0a/b/c 均符合 AVL 树的要求。在 a 子树中插入一个新结点导致 a 子树的高度从 h 变成 h1不断向上更新平衡因子导致 10 的平衡因子从 -1 变成 -210 为根的树左边太高了需要往右边旋转。旋转核心步骤因为 5 b 子树的值 10将 b 变成 10 的左子树10 变成 5 的右子树5 变成这棵树新的根。这样既符合搜索树的规则又控制了平衡同时这棵树的高度恢复到了插入之前的 h2。4.3 右单旋代码实现void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; // 需要注意除了要修改孩子指针指向还要修改父亲 parent-_left subLR; if (subLR) subLR-_parent parent; Node* parentParent parent-_parent; subL-_right parent; parent-_parent subL; // parent 有可能是整棵树的根也可能是局部的子树 // 如果是整棵树的根要修改 _root // 如果是局部的指针要跟上一层链接 if (parentParent nullptr) { _root subL; subL-_parent nullptr; } else { if (parent parentParent-_left) { parentParent-_left subL; } else { parentParent-_right subL; } subL-_parent parentParent; } parent-_bf subL-_bf 0; }4.4 左单旋以 10 为根的树在 a 子树中插入一个新结点导致 10 的平衡因子从 1 变成 210 为根的树右边太高了需要往左边旋转。旋转核心步骤因为 10 b 子树的值 15将 b 变成 10 的右子树10 变成 15 的左子树15 变成这棵树新的根。4.5 左单旋代码实现void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) 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 subR-_bf 0; }4.6 左右双旋左边高时如果插入位置不是在 a 子树而是插入在 b 子树b 子树高度从 h 变成 h1引发旋转此时右单旋无法解决问题。因为对于 10 是左边高但对于 5 是右边高需要用两次旋转才能解决以 5 为旋转点进行一次左单旋以 10 为旋转点进行一次右单旋这棵树就平衡了。根据新增结点插入位置的不同平衡因子更新的细节也不同需要分三个场景讨论场景1h 1新增结点插入在 e 子树8 的平衡因子为 -1旋转后 8 和 5 平衡因子为 010 平衡因子为 1。场景2h 1新增结点插入在 f 子树8 的平衡因子为 1旋转后 8 和 10 平衡因子为 05 平衡因子为 -1。场景3h 0b 自己就是新增结点8 的平衡因子为 0旋转后 8、10 和 5 平衡因子均为 0。4.7 左右双旋代码实现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); } }4.8 右左双旋跟左右双旋类似右边高时如果插入位置在 b 子树需要用两次旋转解决以 15 为旋转点进行一次右单旋以 10 为旋转点进行一次左单旋。同样分三个场景讨论场景1h 1新增结点插入在 e 子树12 的平衡因子为 -1旋转后 10 和 12 平衡因子为 015 平衡因子为 1。场景2h 1新增结点插入在 f 子树12 的平衡因子为 1旋转后 15 和 12 平衡因子为 010 平衡因子为 -1。场景3h 0b 自己就是新增结点12 的平衡因子为 0旋转后 10、12 和 15 平衡因子均为 0。4.9 右左双旋代码实现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); } }五、 AVL树的查找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; } 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 nullptr; int leftHeight _Height(root-_left); int rightHeight _Height(root-_right); int diff leftHeight - rightHeight; if (abs(diff) 2) { cout root-_kv.first 高度差异常 endl; return false; } if (root-_bf ! diff) { cout root-_kv.first 平衡因子异常 endl; return false; } return IsBalanceTree(root-_left) IsBalanceTree(root-_right); }