徐州丰县建设局网站,上海健康证查询网址,茶叶设计网站建设,厦工品牌网站设计文章目录 一、AVL树的原理AVL树的定义和特性平衡因子的概念 二、AVL树的自平衡策略a. 单旋#xff08;single rotation#xff09;1. 左单旋#xff08;Left Rotation#xff09;#xff1a;2. 右单旋#xff08;Right Rotation#xff09;#xff1a; b. 双旋#xf… 文章目录 一、AVL树的原理AVL树的定义和特性平衡因子的概念 二、AVL树的自平衡策略a. 单旋single rotation1. 左单旋Left Rotation2. 右单旋Right Rotation b. 双旋Double Rotation1. 左右双旋Left-Right Double Rotation2. 右左双旋Right-Left Double Rotation 三、AVL树的插入与验证1. 插入操作2. AVL树的验证 本文将带领读者深入探索 AVL 树的奥秘从基本概念到具体实现逐步剖析 AVL 树的平衡之道。无论您是初学者还是资深程序员相信通过本文的阅读您都能对 AVL 树有更深入的理解并能够运用它解决实际问题。 一、AVL树的原理
AVL 树Adelson-Velsky and Landis tree作为一种自平衡的二叉搜索树由 G.M. Adelson-Velsky 和 E.M. Landis 在 1962 年提出。它承载着优雅而高效的数据结构设计理念。其独特之处在于通过旋转操作保持树的高度平衡从而确保各种操作的时间复杂度始终保持在 $O(log n) $的水平。AVL 树的诞生源于对二叉搜索树的不足之处的思考和突破是计算机科学领域中的重要里程碑之一。
AVL树的定义和特性
AVL树是一种自平衡的二叉搜索树其在每个节点上维护一个平衡因子Balance Factor用于确保树的高度保持在较低水平 即保持在$O(log n) $从而提高性能。下面详细解释AVL树的定义和特性 定义AVL树是一种满足以下性质的二叉搜索树 每个节点的平衡因子Balance Factor是 -1、0 或 1。左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。左子树和右子树都是AVL树。 我们给出如下代码来定义 AVL树 templateclass K,class V
struct AVLTreeNode {AVLTreeNodeK, V* _left; // 该节点的左孩子AVLTreeNodeK, V* _right; // 该节点的右孩子AVLTreeNodeK, V* _parent; // 该节点的双亲int _bf; // 该节点的平衡因子pairK, V _kv;AVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv) {}
};
templateclass K, class V
class AVLTree {typedef AVLTreeNodeK, V Node;
public://...
private:Node* _root;
};AVLTreeNode是AVL树的节点结构包含节点的左孩子、右孩子、双亲以及数据和平衡因子。AVLTree是AVL树的类包含了根节点和其他操作方法。在AVLTree类中_root成员变量表示根节点。 特性 每个节点的平衡因子限制在AVL树中每个节点的平衡因子必须是 -1、0 或 1。这意味着任何节点的左子树高度和右子树高度之差的绝对值不超过1。左右子树的高度差不超过1AVL树的关键特点是保持树的高度平衡即任意节点的左子树和右子树高度差不超过1。这确保了树的高度近似于$ log(n) 其中 n 是节点数量从而保证了插入、查找和删除等操作的平均时间复杂度为 其中 n 是节点数量从而保证了插入、查找和删除等操作的平均时间复杂度为 其中n是节点数量从而保证了插入、查找和删除等操作的平均时间复杂度为 O(log n)$。 两个二叉搜索树只有左边的树是 AVL 树。
AVL的优势相对于普通二叉搜索树
平衡性保证AVL树通过限制每个节点的平衡因子来保持树的平衡相比普通二叉搜索树更加平衡避免了出现极端不平衡的情况提高了整体性能。高效的插入和删除操作由于AVL树具有平衡性质插入和删除操作会触发自平衡机制保持树的平衡状态使得这些操作的时间复杂度为 O ( l o g n ) O(log n) O(logn)相比普通二叉搜索树更加高效。稳定的查找性能AVL树的平衡性质确保了树的高度较低从而保证了查找操作的稳定性能使得在动态数据集合中仍能保持较快的查找速度。
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这 样可以保证查询时高效的时间复杂度即 l o g 2 ( N ) log_2 (N) log2(N)。但是如果要对AVL树做一些结构修改的操 作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时 有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
平衡因子的概念
在AVL树中平衡因子Balance Factor是指一个节点的左子树高度减去右子树高度的结果。具体而言对于任意节点N其平衡因子 BF(N) 的计算公式如下
[ BF(N) Height(leftSubtree) - Height(rightSubtree) ]
其中Height(leftSubtree)表示节点N的左子树的高度而Height(rightSubtree)表示节点N的右子树的高度。
在AVL树中每个节点的平衡因子必须是 -1、0 或 1否则就不符合AVL树的定义。如果某个节点的平衡因子绝对值大于1那么这个节点就会导致其祖先节点失衡需要通过旋转等操作来重新平衡整棵树。
我们通过控制每个节点的平衡因子AVL树能够保持良好的平衡性质确保在插入或删除节点后能够高效地进行自平衡操作使得树的整体高度保持较低水平从而提高查找、插入和删除等操作的效率。
二、AVL树的自平衡策略
AVL 树之所以被称为自平衡二叉搜索树是因为它会在每次插入或删除操作后自动调整树的结构以保持平衡。
在插入以后只有那些从插人点到根节点的路径上的节点的平衡可能被改变因为只有这些节点的子树可能发生变化。当我们沿着这条路径上行到根并更新平衡信息时我们可以找到一个节点它的新平衡破坏了AVL条件。我们将指出如何在第一个这样的节点即最深的节点重新平衡这棵树并证明这一重新平衡保证整棵树满足AVL特性。
让我们把必须重新平衡的节点叫作a。由于任意节点最多有两个儿子因此高度不平时a点的两棵子树的高度差2。容易看出这种不平衡可能出现在下面四种情况中:
对a的左儿子的左子树进行一次插入。对a的左儿子的右子树进行一次插入,对a的右儿子的左子树进行一次插入。对a的右儿子的右子树进行一次插入。
情形1和4是关于a点的镜像对称而情形2和3是关于a点的镜像对称。因此理论上只有两种情况单旋转和双旋当然从编程的角度来看还是四种情形
左旋Left Rotation右旋Right Rotation左右双旋Left-Right Double Rotation和右左旋转Right-Left Double Rotation双旋是由两次单旋转组合而成的操作用于处理更复杂的情况。下面详细介绍在AVL树如何根据节点的平衡因子进行相应的调整以及中如何通过这些旋转操作来确保AVL树的平衡性下图中括号内 1 代表在此处插入节点A B C来形容其相对位置
a. 单旋single rotation
下面我们依次介绍左单旋和右单旋
1. 左单旋Left Rotation
左旋是针对某个节点的右子树过深而导致失衡的情况。即新节点插入较高右子树的右侧—右右左单旋。具体步骤如下 假设失衡节点为AA的右子节点为BB的左子节点为C。将B提升为新的根节点A作为B的左子节点C作为A的右子节点。可以看到经过左单旋后树的高度变为插入之前了即树的高度没有发生变化所以左单旋后无需继续往上更新平衡因子。
根据上述内容我们给出如下代码
void RotateL(Node* parent) {Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL ! nullptr) {subRL-_parent parent;}subR-_left parent;Node* ppnode parent-_parent;parent-_parent subR;if (parent _root) {_root subR;subR-_parent nullptr;}else {if (ppnode-_left parent)ppnode-_left subR;elseppnode-_right subR;subR-_parent ppnode;}parent-_bf 0;subR-_bf 0;
}首先将parent节点的右子节点subR的左子节点subRL作为parent节点的新右子节点同时更新相关的指针和父节点标志位。然后根据parent节点是否为根节点进行相应的操作将subR作为新的根节点或者将subR连接到原父节点ppnode上并更新父节点指针最后更新节点的平衡因子。
下面是对代码中各部分的功能和逻辑的解释
首先保存当前节点的右子节点subR和右子节点的左子节点subRL。然后将当前节点的右子节点指向subRL如果subRL不为空则更新subRL的父节点指针为parent。接着将subR的左子节点指向当前节点parent完成左旋操作。其次更新受影响的父节点指针确保树的连接正确性
将parent的父节点指针指向subR。如果parent是根节点需要更新根节点指针为subR并将subR的父节点指针置为空。否则更新父节点ppnode的左子树或右子树指针为subR并更新subR的父节点指针为ppnode。
最后将调整后的节点的平衡因子设置为0表示平衡。
这段代码实现了AVL树中左旋操作的所有必要步骤包括旋转、节点指针的更新以及平衡因子的设置以确保树的平衡性得到维护。左旋和右旋是 AVL 树中用于保持树平衡的重要操作通过这些操作可以调整树的结构以维持平衡因子的要求。
2. 右单旋Right Rotation
右旋是针对某个节点的左子树过深而导致失衡的情况。即新节点插入较高左子树的左侧—左左右单旋。具体步骤如下 设失衡节点为AA的左子节点为BB的右子节点为C。将B提升为新的根节点A作为B的右子节点C作为A的左子节点。
根据上述内容我们给出如下代码
void RotateR(Node* parent) {Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR ! nullptr) {subLR-_parent parent;}subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root) {_root subL;subL-_parent nullptr;}else {if (ppnode-_left parent)ppnode-_left subL;elseppnode-_right subL;subL-_parent ppnode;}parent-_bf 0;subL-_bf 0;
}首先保存当前节点的左子节点subL和左子节点的右子节点subLR。然后将当前节点的左子节点指向subLR如果subLR不为空则更新subLR的父节点指针为parent。接着将subL的右子节点指向当前节点parent完成右旋操作。其次更新受影响的父节点指针确保树的连接正确性
将parent的父节点指针指向subL。如果parent是根节点需要更新根节点指针为subL并将subL的父节点指针置为空。否则更新父节点ppnode的左子树或右子树指针为subL并更新subL的父节点指针为ppnode。
最后将调整后的节点的平衡因子设置为0表示平衡。
b. 双旋Double Rotation
双旋是针对某个节点的子树同时向左或向右倾斜而导致失衡的情况。一般需要进行两次单旋操作来恢复平衡。具体步骤可以是左旋后再进行右旋或者右旋后再进行左旋。
1. 左右双旋Left-Right Double Rotation
当在某个节点的左子树中的右子树更深时需要进行右左旋转操作。这种情况下首先对当前节点的左子节点进行左旋转然后再对当前节点进行右旋转以实现树的平衡。即新节点插入较高左子树的右侧—左右先左单旋再右单旋。具体步骤如下 首先获取当前节点的左子节点 subL 和左子节点的右子节点 subLR。 然后获取 subLR 的平衡因子 bf。 接下来调用 RotateL 函数对当前节点的左子节点进行左旋转。 再次调用 RotateR 函数对当前节点进行右旋转。 Node* subL parent-_left;
Node* subLR subL-_right;
int bf subLR-_bf;
RotateL(parent-_left);
RotateR(parent);根据 subLR 的平衡因子 bf 的不同情况进行平衡因子的更新 如果 bf 为 0表示左右子树高度相等将当前节点和左子节点的平衡因子都设置为 0。 如果 bf 为 1表示左子树高度大于右子树将当前节点的平衡因子设置为 0左子节点的平衡因子设置为 -1。 如果 bf 为 -1表示右子树高度大于左子树将当前节点的平衡因子设置为 1左子节点的平衡因子设置为 0。 如果以上情况都不满足抛出异常。 if (bf 0) {parent-_bf 0;subL-_bf 0;
}
else if (bf 1) {parent-_bf 0;subL-_bf -1;
}
else if (bf -1) {parent-_bf 1;subL-_bf 0;
}
else {assert(false);
}总结上述代码如下
void RotateLR(Node* parent) {if (bf 0) {parent-_bf 0;subL-_bf 0;}else if (bf 1) {parent-_bf 0;subL-_bf -1;}else if (bf -1) {parent-_bf 1;subL-_bf 0;}else {assert(false);}
}2. 右左双旋Right-Left Double Rotation
当在某个节点的右子树中的左子树更深时需要进行左右旋转操作。这种情况下首先对当前节点的右子节点进行右旋转然后再对当前节点进行左旋转以恢复树的平衡性。即 新节点插入较高右子树的左侧—右左先右单旋再左单旋。具体步骤如下 首先获取当前节点的右子节点 subR 和右子节点的左子节点 subRL。 然后获取 subRL 的平衡因子 bf。 接下来调用 RotateR 函数对当前节点的右子节点进行右旋转。 再次调用 RotateL 函数对当前节点进行左旋转。
Node* subR parent-_right;
Node* subRL subR-_left;
int bf subRL-_bf;
RotateR(parent-_right);
RotateL(parent);根据 subLR 的平衡因子 bf 的不同情况进行平衡因子的更新 如果 bf 为 0表示右左子树高度相等将当前节点和右子节点的平衡因子都设置为 0。 如果 bf 为 1表示左子树高度大于右子树将当前节点的平衡因子设置为 -1右子节点的平衡因子设置为 0。 如果 bf 为 -1表示右子树高度大于左子树将当前节点的平衡因子设置为 0右子节点的平衡因子设置为 1。 如果以上情况都不满足抛出异常。 if (bf 0) {parent-_bf 0;subR-_bf 0;
}
else if (bf 1) {parent-_bf -1;subR-_bf 0;
}
else if (bf -1) {parent-_bf 0;subR-_bf 1;
}
else {assert(false);
}总结上述代码如下
void RotateLR(Node* parent) {Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf -1) {subL-_bf 0;parent-_bf 1;}else if (bf 1) {subL-_bf -1;parent-_bf 0;}else if (bf 0) {subL-_bf 0;parent-_bf 0;}else {assert(false);}
}在旋转过程中左右双旋的 subLR-_bf 在进行左单旋和右单旋函数调用时旋已置为0右左双旋的 subRL-_bf 在进行右单旋和左单旋函数调用时旋已置为0。观察旋转后的结果我们可以得知 subLR-_bf 和 subRL-bf 在上述各种情况里都是 0因此双旋函数不需要再对其平衡因子进行处理。 三、AVL树的插入与验证
1. 插入操作
AVL 树的插入操作主要包含两个步骤插入新节点和平衡性调整。
A. 插入新节点
从根节点开始循环比较要插入节点的键值和当前节点的键值大小关系确定插入位置。如果要插入的节点小于当前节点则继续在当前节点的左子树中插入如果大于当前节点则在右子树中插入。当找到插入位置时在对应的子树中插入新节点。
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-_left cur;}else {parent-_right cur;}cur-_parent parent;//....
}B. 平衡性调整
在插入新节点后从插入点向上回溯到根节点检查沿途节点的平衡因子是否失衡绝对值大于1。如果某个节点失衡根据其子树的情况进行相应的旋转操作单旋转或双旋转来保持树的平衡。旋转操作可能会影响祖先节点的平衡因子因此需要继续向上回溯直到整棵树恢复平衡为止。
bool Insert(const pairK, V kv) {// ... 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 cur-_parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2) {if (parent-_bf 2 cur-_bf 1) {RotateL(parent);}else if (parent-_bf -2 cur-_bf -1) {RotateR(parent);}else if (parent-_bf 2 cur-_bf -1) {RotateRL(parent);}else if (parent-_bf -2 cur-_bf 1) {RotateLR(parent);}break;}else {assert(false);//插入前就出错}}return true;
}通过以上两个步骤可以实现在 AVL 树中插入新节点并保持树的平衡性把两个代码块中内容合在一起看。 AVL 树的平衡性调整是通过旋转操作来实现的旋转操作包括左旋、右旋、左右双旋和右左双旋。使 AVL 树的每个节点的左右子树高度差不超过 1以保持树的平衡性。
2. AVL树的验证
为了证明二叉树是AVL树还需验证二叉树的平衡性在该过程中我们需要检查每个结点的平衡因子是否正确
bool _IsBalance(Node* root, int height) {// 后序if (root nullptr) {height 0;return true;}int leftHeight 0, rightHeight 0;if (!_IsBalance(root-_left, leftHeight) || !_IsBalance(root-_right, rightHeight))return false;if (abs(leftHeight - rightHeight) 2) {cout root-_kv.first height warning! endl;return false;}if (rightHeight - leftHeight ! root-_bf) {cout root-_kv.first balance factor warning! endl;return false;}height max(leftHeight, rightHeight) 1;return true;
}bool IsBalance() {int heght 0;return _IsBalance(_root, heght);
}在函数 _IsBalance 中它首先判断当前节点是否为空如果是空节点则将高度设置为 0并返回 true。然后分别递归检查左右子树并获取它们的高度。接着它会判断左右子树的高度差是否大于等于 2如果是则输出警告并返回 false。然后它会再次判断当前节点的平衡因子是否与左右子树的高度差相符如果不符则输出警告并返回 false。最后更新当前节点的高度为左右子树中较大的高度加 1并返回 true。
在 IsBalance 函数中它调用了 _IsBalance 函数并传入根节点和一个用于记录树高度的变量。最终返回 _IsBalance 函数的结果。
总的来说这段代码通过递归后序遍历的方式来检查整棵树的平衡性并在发现不平衡的情况下输出相应的警告信息。这样的实现方式是典型的检查 AVL 树平衡性的方法但需要保证树的平衡因子 _bf 在每次插入、删除后得到正确更新。
通过以上内容我们将全面探索 AVL 树的内涵与外延逐步揭示其平衡之道。希望本文能为读者提供清晰而全面的 AVL 树知识体系帮助大家更好地理解和运用 AVL 树这一重要的数据结构。 本文代码的完整实现在此处AVL树 · 比奇堡的Zyb/每日学习 - 码云 - 开源中国 (gitee.com)。
