深入理解 AVL 树：自平衡二叉搜索树的原理与实现

二叉搜索树BST是一种经典的数据结构理想情况下查找、插入、删除操作的时间复杂度均为 O(log n)。但它有一个致命缺陷在极端插入顺序下如有序插入二叉搜索树会退化成链表时间复杂度恶化为 O(n)。为了解决这个问题1962 年两位苏联数学家 Adelson-Velsky 和 Landis 提出了一种自平衡二叉搜索树 ——AVL 树以两人姓氏首字母命名。它通过在每次插入和删除后维护树的平衡保证了所有操作的最坏时间复杂度始终为 O(log n)。一AVL树的核心定义1.1AVL树的性质AVL 树本质上是一棵满足以下条件的二叉搜索树1满足二叉搜索树的所有性质左子树所有节点值 根节点值 右子树所有节点值。2树中每个节点的平衡因子的绝对值不超过 1即 |BF| 1。3左右子树也都是 AVL 树。当插入或删除操作导致某个节点的平衡因子超出 [-1, 1] 范围时就需要通过旋转操作来重新恢复平衡。1.2AVL树的平衡因子AVL 树的核心概念是平衡因子Balance Factor, BF它定义为某节点的右子树高度减去左子树的高度。由于左右子树的高度差的绝对值不超过1所以任何节点的平衡因子等于0 / 1 / -1 AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去观察和控制树是否平衡。AVL整体节点数量和分布与完全二叉树类似高度可以控制在logN那么增删查改的效率也可以控制在O(log n)相比二叉搜索树有了很大提升。二AVL树的实现2.1AVL树的节点结构#includeiostream #includeassert.h using namespace std; templateclass k,class v class AVLTreeNode { public: 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) {} };这是AVL树的结构节点中的数据使用pairKeyValue存储键值对数据。若存在一个结点root_left代表它的左边的结点该节点的key比root的key小_right代表它的右边的结点该节点的key比root的key大_parent代表它的父结点_bf是这个结点对应的平衡因子的值。2.2AVL树的插入2.2.1AVL树插入一个值的过程1插入一个值的规则要按照二叉搜索树的规则若要插入的值比当前结点大那么要插入的值就在这个结点的右子树上反之就在这个结点的左子树上若找到了一个结点它的值与要插入的值相等就不允许插入这个值了直接返回false插入该值失败。2若新增一个结点只会影响它的祖先结点的高度也就会影响部分祖先结点的平衡因子所以就要更新从该结点到根结点路径上的平衡因子但有些情况只更新部分祖先结点的平衡因子更新到中间就停止了具体是什么情况后面慢慢分析。3在更新平衡因子的过程中若出现了不平衡就要对不平衡的子树旋转旋转之后本质是为了降低子树的高度不会影响上一层所以插入结束。2.2.2平衡因子的更新1更新规则平衡因子右子树高度-左子树高度。只有子树高度变化才会影响当前结点的平衡因子。当我们插入了一个比10小的值5就会插入到它的左子树上10的平衡因子由0变成了-1在插入一个比10大的值1510的平衡因子就变成了0。所以得出一个结论若10结点为parent新增节点在它的左子树上parent平衡因子减一新增结点在它的右子树上parent平衡因子加一。2更新后parent的平衡因子等于0说明更新前parent的平衡因子为-1或者1则更新前parent子树一边高一边低新增结点在低的那边插入后parent子树高度不变不会影响parent的父结点的平衡因子更新结束。3更新后parent的平衡因子等于1或者-1说明更新前parent的平衡因子为0则更新前parent子树两边一样高新增结点后parent所在子树一边高一边低parent所在的子树符合平衡要求但是高度增加了1会影响parent的父结点的平衡因子所以要继续向上更新。4更新后parent的平衡因子等于2 或 -2更新前更新中parent的平衡因子变化为1-2 或者 -1--2说明更新前parent子树⼀边高⼀边低新增的插⼊结点在高的那边parent所在的子树高的那边更高了破坏了平衡parent所在的子树不符合平衡要求需要旋转处理旋转的目标有两个1、把 parent子树旋转平衡。2、降低parent子树的高度恢复到插⼊结点以前的高度。所以旋转后也不需要继续往上更新插入结束。插入结点及更新平衡因子代码实现bool insert(const pairk, v p) { Node* root _root; Node* parent nullptr; while (root) { if (root-_key_value.first p.first) { parent root; root root-_left; } else if (root-_key_value.first p.first) { parent root; root root-_right; } else { return false; } } Node* newnode new Node(p); newnode-_parent parent; if (parent nullptr) { _root newnode; } else { if (parent-_key_value.first p.first) { parent-_left newnode; } else if (parent-_key_value.first p.first) { parent-_right newnode; } } //更新平衡因子 Node* cur newnode; while (parent) { if (parent-_left cur) { --parent-_bf; } else { //if (parent-_right cur) 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) { //旋转 if (parent-_bf -2 cur-_bf -1) { //右单旋 RotateR(parent); } else if (parent-_bf 2 cur-_bf 1) { //左单旋 RotateL(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 { assert(false); } } return true; }2.3AVL树插入结点的旋转操作及代码实现旋转之后也要保持搜索树的规则让旋转的树从不平衡变平衡其次降低旋转树的高度。旋转分为四种左单旋 / 右单旋 / 左右双旋 / 右左双旋。2.3.1左单旋此时再新增80结点它所在路径上的祖先结点依次向上更新这颗子树的根节点parent它的平衡因子就变成了2不符合AVL树的规则了。下面的图可以看到这颗子树的右边高就要将parent结点左旋降低树的高度。那怎么判断出是需要左旋的呢若parent的平衡因子为2cur的平衡因子为1parent就需要左旋了。具体怎么左旋下图所示。步骤1先将parent的_right指向cur的左子树若cur的左子树不为空就将cur的左子树的_parent结点指向parent。步骤2将cur的_left指向parent注意要提前保存好parent的_parent结点parentParent因为parent可能只是当前这颗子树的根将parent的_parent指向cur。再判断出parent结点是parentParent结点的_left还是_right判断好了parentParent结点的_left或者_right(具体根据前面的判断)指向curcur的_parent指向parentParent。代码实现void RotateL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; parent-_right subRL; if (subRL) { subRL-_parent parent; } subR-_left parent; Node* parentParent parent-_parent; parent-_parent subR; if (parentParent) { if (parentParent-_left parent) { parentParent-_left subR; } else { parentParent-_right subR; } subR-_parent parentParent; } else { subR-_parent nullptr; _root subR; } parent-_bf subR-_bf 0; }2.3.2右单旋右单旋与左单旋类似旋转步骤示意图及代码如下右旋代码实现void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; subL-_right parent; if (subLR) { subLR-_parent parent; } Node* parentParent parent-_parent; parent-_parent subL; if (parentParent) { if (parentParent-_left parent) { parentParent-_left subL; } else { parentParent-_right subL; } subL-_parent parentParent; } else { _root subL; subL-_parent nullptr; } subL-_bf parent-_bf 0; }2.3.3右左双旋更新到25这个结点平衡因子变成了228的平衡因子是-1。要对28右旋再对25左旋降低树的高度。旋转之前必须提前保存28结点的平衡因子int bf cur-_bf (-1) 。另外还有两种情况1subRL1则bf subRL-_bf1。2subRL-1则bf subRL-_bf-1。右左双旋代码实现//右左双旋 void RotateRL(Node* parent) { Node* subR parent-_right; Node* subRL subR-_left; //先保存subRL的平衡因子 int bf subRL-_bf; RotateR(subR); RotateL(parent); if (bf -1) { subRL-_bf 0; parent-_bf 0; subR-_bf 1; } else if (bf 1) { subRL-_bf 0; parent-_bf -1; subR-_bf 0; } else if (bf 0) { subRL-_bf 0; parent-_bf 0; subR-_bf 0; } else { assert(false); } }2.3.4左右双旋1bf0;2bf1;3bf-1;左右双旋代码实现//左右双旋 void RotateLR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; //先保存subLR的平衡因子 int bf subLR-_bf; RotateL(subL); RotateR(parent); if (bf 1) { subLR-_bf 0; subL-_bf -1; parent-_bf 0; } else if (bf -1) { subLR-_bf 0; subL-_bf 0; parent-_bf 1; } else if (bf 0) { subLR-_bf 0; subL-_bf 0; parent-_bf 0; } else { assert(false); } }以上就是AVL树插入一个结点的相关旋转操作。删除一个结点操作后续更新