徐州网站建设商城制作网站推广seo,专做母婴的网站,做网站买过域名之后,wordpress api下载文章目录 前言Ⅰ. AVL树的定义Ⅱ. AVL树节点的定义Ⅲ. AVL树的插入Insert一、节点的插入二、插入的旋转① 新节点插入较高左子树的左侧#xff08;左左#xff09;#xff1a;右单旋② 新节点插入较高右子树的右侧#xff08;右右#xff09;#xff1a;左单旋③ 新节点插… 文章目录 前言Ⅰ. AVL树的定义Ⅱ. AVL树节点的定义Ⅲ. AVL树的插入Insert一、节点的插入二、插入的旋转① 新节点插入较高左子树的左侧左左右单旋② 新节点插入较高右子树的右侧右右左单旋③ 新节点插入较高左子树的右侧左右先左单旋再右单旋④ 新节点插入较高右子树的左侧右左先右单旋再左单旋插入后旋转的总结 Ⅳ. AVL树的验证验证用例 Ⅴ. AVL树的删除Erase一、节点的删除二、删除的旋转 Ⅵ. AVL树的性能Ⅶ. AVL树的整体框架 前言
之前对 map / multimap / set / multiset 进行了简单的介绍在其文档介绍中发现这几个容器有个共同点是其底层都是按照二叉搜索树来实现的但是二叉搜索树有其自身的缺陷假如往树中插入的元素有序或者接近有序二叉搜索树就会退化成单支树时间复杂度会退化成 O(N)因此 map、set 等关联式容器的底层结构是对二叉树进行了平衡处理即采用平衡树来实现。
注意因为 map 和 set 主要是用红黑树进行封装所以这里的 AVL 树我们主要是实现它的 插入 和 删除 和 operator[] 因为 insert 就是为了 operator[] 而存在的还记得我们在二叉树进阶讲的吗所以我们这里不会去是实现 AVL 树的拷贝构造和赋值重载这方面涉及到深拷贝我们一并到红黑树才讲
Ⅰ. AVL树的定义
二叉搜索树虽可以缩短查找的效率但 如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过 1( 需要对树中的结点进行调整 )即可降低树的高度从而减少平均搜索长度。
一棵 AVL 树或者是空树或者是具有以下性质的二叉搜索树 左右子树都是 AVL 树 左右子树高度之差 ( 简称 平衡因子) 的绝对值不超过 1 如果一棵二叉搜索树是高度平衡的它就是 AVL 树。如果它有 n 个结点其高度可保持在 l o g 2 n log_2 n log2n搜索时间复杂度 O( l o g 2 n log_2 n log2n)。
Ⅱ. AVL树节点的定义
对于 AVL 树节点的定义其实有很多个版本各有优势这里用的是三叉链的结构这是为了方便后面的一些操作但是也是有弊端的比如说在链接的时候要把三条链都考虑进去但是三叉链的优势是利大于弊所以这里采用三叉链
而至于 AVL 树的一些特点比如说调整树的高度那么我们就得知道该节点的 平衡因子(balance factor)所以这里我们给节点里面增加一个 bf用于存放该节点的平衡因子。
注意这里 平衡因子bf的值 等于右子树高度 - 左子树高度 根据AVL树的定义每个节点的bf值理论上只可能有三种情况10-1。所以当bf出现其他值的时候就代表树不平衡了需要调整了。 template class K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv; // _kv是一个键值对int _bf; // 该点的平衡因子 -- balance factorAVLTreeNode(const pairK, V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};Ⅲ. AVL树的插入Insert
一、节点的插入
AVL 树的插入和之前搜索树的插入是一样的只不过在插入之后我们需要做出调整因为有可能我们插入节点后会导致二叉树的不平衡所以我们得重新调整高度这里就涉及到 左单旋、右单旋、左右双旋和右左双旋 四个操作。
AVL 树的插入过程可以分为两步 按照二叉搜索树的方式插入新节点 调整节点的平衡因子 新增的节点如果在 parent 的左边则 parent-bf--新增的节点如果在 parent 的右边则 parent-bf 如果 parent 的平衡因子为 0说明高度是平衡的停止更新如果 parent 的平衡因子为 1 或者 -1说明 parent 所在子树的高度变了继续往上更新如果 parent 的平衡因子为 2 或者 -2说明已经出现不平衡了需要进行旋转调整后面会讲如何旋转
pairNode*, bool Insert(const pairK, V kv)
{// 若树为空则直接开辟新节点if (_root nullptr){_root new Node(kv);return make_pair(_root, true);}// 先找到要插入的位置用cur标记而parent标记cur的上一个位置Node* cur _root;Node* parent _root;while (cur ! nullptr){if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{return make_pair(cur, false);}}// 接着插入节点cur new Node(kv);Node* newnode cur; // 这一步是为了后面返回值返回的if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}// 调整高度while (parent ! nullptr) // 这里也可写出while(cur ! _root){// 1、先调节平衡因子if (parent-_left cur){parent-_bf--;}else{parent-_bf;}// 2、判断是否需要旋转if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1){// 插入前双亲的平衡因子是0插入后双亲的平衡因为为1 或者 -1 说明以双亲为根的二叉树的高度增加了一层因此需要继续向上调整cur parent;parent parent-_parent;}else if(parent-_bf 2 || parent-_bf -2){// 需要调整高度if (parent-_bf -2){if (cur-_bf -1){RotateR(parent); //右单旋}else if(cur-_bf 1){RotateLR(parent); //左右双旋}}else if (parent-_bf 2){if (cur-_bf 1){RotateL(parent); //左单旋}else if (cur-_bf -1){RotateRL(parent); //右左双旋 }}// 注意这里的break很关键因为我们调整了子树的平衡因子后它的父亲以上的树其实就已经不会受影响了break;}else{// 插入节点之前树已经不平衡了或者bf出错。需要检查其他逻辑assert(false);}}return make_pair(newnode, true);
} 问题这里要注意的是 Insert 的返回值为什么是 pair
还记得我们在实现二叉搜索树的时候说到Insert 的实现其实是为了 operator[] 而产生的而 operator[] 需要接收到是一个键值对里面的 value所以我们的 Insert 需要返回一个 pair且 pair 里面第一个键值放的是迭代器第二个值放的是 bool 值这是为了和 STL 里面的实现保持一致详情可查看官方文档。
二、插入的旋转
如果在一棵原本是平衡的 AVL 树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。根据节点插入位置的不同AVL 树的旋转分为四种
① 新节点插入较高左子树的左侧左左右单旋
如下图我们在 a 树下插入新节点此时 30 节点和 60 节点的平衡因子就变了则需要调整。 上图在插入前AVL 树是平衡的新节点插入到 30 的左子树注意此处不是左孩子中30 的左子树增加了一层导致以 60 为根的二叉树不平衡要让 60 平衡只能将 60 左子树的高度减少一层右子树增加一层即将 60 的左子树往上提这样 60 转下来因为 60 比 30 大只能将其放在 30 的右子树而如果 30 有右子树右子树根的值一定大于 30小于 60只能将其放在 60 的左子树旋转完成后更新节点的平衡因子即可。在旋转过程中有以下几种情况需要考虑 30 节点的右孩子可能存在也可能不存在 60 节点可能是根节点也可能是子树 如果是根节点旋转完成后要更新根节点 如果是子树可能是某个节点的左子树也可能是右子树 最后记得将 30 和 60 节点的平衡因子调为 0
void RotateR(Node* parent)
{// SubL: Parent的左孩子// SubLR: Parent左孩子的右孩子Node* subL parent-_left;Node* subLR subL-_right;// 先将parent的左子树连上subLR注意要双向链接parent-_left subLR;if (subLR ! nullptr) // 注意要判断subLR是否为空为空则不需要链接subLR-_parent parent;// 让parent作为subL的右子树subL-_right parent;Node* parent_parent parent-_parent; // 先将parent的parent记录下来后面链接要用到parent-_parent subL;// 判断一下parent是否为二叉树的根节点if (parent _root){_root subL;_root-_parent nullptr;}else{// 如果60是子树可能是parent_parent的左子树也可能是右子树if (parent_parent-_left parent){parent_parent-_left subL;}else{parent_parent-_right subL;}subL-_parent parent_parent;}// 最后记得要将平衡因子置零subL-_bf parent-_bf 0;
}② 新节点插入较高右子树的右侧右右左单旋 实现及情况考虑可参考右单旋与右单旋基本一致只不过要旋转的节点不同而已
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;// 先将parent的左子树连上subRL注意要双向链接parent-_right subRL;if (subRL ! nullptr)subRL-_parent parent;// 让parent作为subR的右子树subR-_left parent;Node* parent_parent parent-_parent;parent-_parent subR;// 判断一下parent是否为二叉树的根节点if (parent _root){_root subR;_root-_parent nullptr;}else{if (parent_parent-_left parent){parent_parent-_left subR;}else{parent_parent-_right subR;}subR-_parent parent_parent;}// 最后记得要将平衡因子置零subR-_bf parent-_bf 0;
}③ 新节点插入较高左子树的右侧左右先左单旋再右单旋
将双旋变成单旋后再旋转即先对 30 进行左单旋然后再对 90 进行右单旋旋转完成后再考虑平衡因子的更新。
而这里双旋后平衡因子更新的情况比较多我们一一列举出来 可以看出来三种情况可以根据 60 这个节点来进行区分
当 60 这个节点的 bf 为 0旋转后该子树的节点的平衡因子都为 0当 60 这个节点的 bf 为 1也就是在右子树插入了新节点则最后 subL-bf -1其他都为 0当 60 这个节点的 bf 为 -1也就是在左子树插入了新节点则最后 parent-bf 1其他都为 0
void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;// 旋转之前保存subLR的平衡因子旋转完成之后需要根据该平衡因子来调整其他节点的平衡因子int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 1){subL-_bf -1;subLR-_bf 0;parent-_bf 0;}else if (bf -1){subL-_bf 0;subLR-_bf 0;parent-_bf 1;}else if (bf 0){subL-_bf 0;subLR-_bf 0;parent-_bf 0;}else{assert(false);}
}④ 新节点插入较高右子树的左侧右左先右单旋再左单旋
大体与左右双旋一致具体参考左右双旋。这里只画出其中一种情况剩下的两种自主分析。 void RotateRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;// 旋转之前保存subRL的平衡因子旋转完成之后需要根据该平衡因子来调整其他节点的平衡因子int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);// 平衡因子的调节与左右双旋不太一样具体自己分析if (bf 1){parent-_bf -1;subRL-_bf 0;subR-_bf 0;}else if (bf -1){parent-_bf 0;subRL-_bf 0;subR-_bf 1;}else if (bf 0){parent-_bf 0;subRL-_bf 0;subR-_bf 0;}else{assert(false);}
}插入后旋转的总结
假如以 parent 为根的子树不平衡即 parent 的平衡因子为 2 或者 -2分以下情况考虑 parent 的平衡因子为 2说明 parent 的右子树高设 parent 的右子树的根为 subR 当 subR 的平衡因子为 1 时执行左单旋 当 subR 的平衡因子为 -1 时执行右左双旋 parent 的平衡因子为 -2说明 parent 的左子树高设 parent 的左子树的根为 subL 当 subL 的平衡因子为 -1 是执行右单旋 当 subL 的平衡因子为 1 时执行左右双旋
旋转完成后原 parent 为根的子树个高度降低已经平衡不需要再向上更新。
Ⅳ. AVL树的验证
AVL 树是在二叉搜索树的基础上加入了平衡性的限制因此要验证 AVL 树可以分两步 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树 验证其为平衡树 每个节点子树高度差的绝对值不超过 1注意节点中如果没有平衡因子节点的平衡因子是否计算正确
int Height(Node* root)
{if (root nullptr)return 0;int leftH Height(root-_left);int rightH Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;
}bool IsBalanceTree(Node* root)
{if (root nullptr)return true;int leftH Height(root-_left);int rightH Height(root-_right);// 检查一下平衡因子是否正确 (右平衡因子 - 左平衡因子)if (rightH - leftH ! root-_bf){cout 平衡因子异常: root-_kv.first endl;return false;}if (abs(rightH - leftH) 2)return false;return IsBalanceTree(root-_left) IsBalanceTree(root-_right);
}// 这个是调用验证AVL树的主函数
bool IsAVLTree()
{return IsBalanceTree(_root);
}验证用例
结合上述代码按照以下的数据次序自己动手画 AVL 树的创建过程验证代码是否有漏洞。
常规场景1{16, 3, 7, 11, 9, 26, 18, 14, 15}
特殊场景2{4, 2, 6, 1, 3, 5, 15, 7, 16, 14} Ⅴ. AVL树的删除Erase
一、节点的删除
因为 AVL 树也是二叉搜索树可按照二叉搜索树的方式将节点删除然后再更新平衡因子只不过与插入不同的是删除节点后的平衡因子更新最差情况下一直要调整到根节点的位置。
AVL 树删除节点的过程是先找到该节点然后进行删除。由于删除节点的位置不同导致删除后节点进行移动的方式不同。删除节点的位置分为以下 4 类 删除叶子结点。操作直接删除然后依次向上调整为 AVL 树。 这里叶子节点还有两种比较特殊的情况 删除非叶子节点该节点只有左孩子。操作该节点的值替换为左孩子节点的值然后删除左孩子节点。 为什么左孩子节点为叶子节点因为删除节点前该树是 AVL 树由 AVL 树的定义知每个节点的左右子树的高度差的绝对值 1由于该节点只有左孩子没有右孩子如果左孩子还有子节点那么将不满足每个节点的左右子树的高度差的绝对值 1所以左孩子节点为叶子结点。 删除非叶子节点该节点只有右孩子。操作该节点的值替换为右孩子节点的值然后删除右孩子节点。 【右孩子节点为叶子结点所以删除右孩子节点的情况为第1种情况。】 【为什么右孩子节点为叶子节点答案和第二种情况一样】 删除非叶子节点该节点既有左孩子又有右孩子。操作该节点的值替换为该节点的前驱节点或者后继节点然后删除前驱节点或者后继节点。 前驱结点在中序遍历中一个节点的前驱结点先找到该节点的左孩子节点再找左孩子节点的最后一个右孩子节点。向左走一步然后向右走到头。最后一个右孩子节点即为前驱节点 后继节点 在中序遍历中一个节点的后继结点先找到该节点的右孩子节点再找右孩子节点的最后一个左孩子节点。向右走一步然后向左走到头。最后一个左孩子节点即为前驱节点
这里我们选择的是后继节点说的简单一点就是右子树的最小节点 总结对于非叶子节点的删除最终都将转化为对叶子节点的删除。 // 删除的情况
// 1.删除的节点为叶子节点直接删除修改父节点的bf并从该节点的父节点向上调整
// 下面两种情况由于删除之前就是AVL树又因为有一个子树为空所以另一个子树非空一定只包含一个节点搞清楚这点很重要这种节点一定是叶子节点的上一层这里虽然是删除该节点实际上删除的是他的唯一一个非空节点
// 2.删除的节点左子树为空右子树非空 相当于删除左子树修改该节点的bf并向上调整
// 3.删除的节点右子树为空左子树非空 相当于删除右子树修改该节点的bf并向上调整
// 4.左右子树都不为空用替换删除法找右子树的最小节点最左边节点这个节点左子树一定为空实际上就转化成了上面三种情况// bf调整原则
// 1. 删左节点父节点的bf
// 2. 删右节点父节点的bf--
// 3. bf为0继续向上调整bf为1或-1停止向上调整
// 4. cur-bf为2的时候情况就与插入不同了插入的时候调整的是插入的节点所在cur的半边子树而删除要调整的是删除节点对面那一半进行旋转这点很重要我在这上面卡了半天旋转的操作与插入相同
bool Erase(const K key)
{// 开头检查一下是否是空树if (_root nullptr)return false;Node* cur _root;Node* parent nullptr;while (cur ! nullptr){if (cur-_kv.first key){parent cur;cur cur-_left;}else if (cur-_kv.first key){parent cur;cur cur-_right;}else{// 找到了该节点准备删除// 1、左右都为空或者其中一个为空if (cur-_left nullptr || cur-_right nullptr){// 删除的节点就是根节点话则先判断是否有左右子树然后在deleteif (_root cur){if (cur-_left nullptr)_root _root-_right;else_root _root-_left;delete cur;// 平衡因子调节注意要加这个判断否则当左右子树不存在的时候_root是nullptr修改bf会报错if(_root ! nullptr)_root-_bf 0;}else if (cur-_left nullptr cur-_right nullptr) // 左右子树均为空{if (parent-_left cur){parent-_left nullptr;parent-_bf;}else{parent-_right nullptr;parent-_bf--;}delete cur;// 调节高度Erase_rotate(parent);}else if (cur-_left nullptr cur-_right ! nullptr) // 左为空右不为空{// 用右节点来代替作为删除的节点cur-_kv cur-_right-_kv;delete cur-_right;cur-_right nullptr;// 调节高度cur-_bf--;Erase_rotate(cur);}else if (cur-_left ! nullptr cur-_right nullptr) // 右为空左为空{// 用左节点来代替作为删除的节点cur-_kv cur-_left-_kv;delete cur-_left;cur-_left nullptr;// 调节高度cur-_bf;Erase_rotate(cur);}}else // 2、左右都不为空{// 找到右子树中的最小值与cur节点的值进行替换// 找右子树最小节点,也就是右子树的最左边的节点这个节点左子树一定为nullptr右子树未知Node* minRight cur-_right;Node* minParent cur;while (minRight-_left ! nullptr){minParent minRight;minRight minRight-_left;}cur-_kv minRight-_kv;// 现在要搞清楚等效删除的是哪个节点以及从哪个节点开始向上检查// 将删除节点转化为上面左右都为空或者其中一个为空的情况解决if (cur minParent){// 相当于删除的是minRight-_right改变minRight的bf并从minRight节点向上检查if (minRight-_right ! nullptr) {minRight-_kv minRight-_right-_kv;delete minRight-_right;minRight-_right nullptr;minRight-_bf;Erase_rotate(minRight);}// 相当于删除的是minRight节点改变minParent的bf并从minParent向上检查else{minParent-_right nullptr;delete minRight;minParent-_bf--;Erase_rotate(minParent);}}else{// 相当于删除的是minRight-_right改变minRight的bf并从minRight节点向上检查if (minRight-_right ! nullptr){// 左子树为空右子树不为空minRight-_kv minRight-_right-_kv;delete minRight-_right;minRight-_right nullptr;minRight-_bf;Erase_rotate(minRight);}//相当于删除的是minRight改变minParent的bf并从minParent向上检查else{// 左右子树 均为空的删除情况minParent-_left nullptr;delete minRight;minParent-_bf;Erase_rotate(minParent);}}}return true;}}return false;
}二、删除的旋转
bf 调整原则
删左节点父节点的 bf删右节点父节点的 bf--bf 为 0 继续向上调整bf 为 1 或 -1 停止向上调整与插入正好反过来cur-bf 为 2 的时候情况就与插入不同了插入的时候调整的是插入的节点所在的半边子树而删除要调整的是删除节点对面那一半进行旋转这点很重要也就是如果 cur 节点的 bf 为 2意味着右边高删除的节点一定在 cur 的左子树接下来要调整右子树 与插入不同的是删除左右单旋各自会出现一种新的情况这种情况是插入中不可能发生的也就是上面删除叶子节点的两种特殊情况 由于插入的时候一定是插入的那半边子树高所以插入的时候只能在 B 的左右一个子树插入所以 B 树的平衡因子不可能为 0而删除就不同了删除节点影响的是另一半边子树旋转的也是另一半边子树上面删除的地方一定是是高度为h的那颗子树所以这种情况就出现了这种情况依然是按照左单旋和右单旋处理。旋转完成之后记得要调整整个树的 bf 值。
// bf调整原则
// 1. 删左节点父节点的bf
// 2. 删右节点父节点的bf--
// 3. bf为0继续向上调整bf为1或-1停止向上调整
// 4. cur-bf为2的时候情况就与插入不同了插入的时候调整的是插入的节点所在cur的半边子树而删除要调整的是删除节点对面那一 半进行旋转这点很重要
// 旋转的操作与插入相同
void Erase_rotate(Node* cur) // 删除节点的操作函数 传入的是已经修改过bf的删除节点的父节点
{Node* prev nullptr;while (cur ! nullptr){if (cur-_bf 1 || cur-_bf -1){break;}else if (cur-_bf 0){prev cur;cur cur-_parent;}else if (cur-_bf 2 || cur-_bf -2){if (cur-_bf 2){if (cur-_right-_bf 0) // 这种情况是插入没有的这里要特殊处理一下{RotateL(cur);cur-_parent-_bf -1;cur-_bf 1;break; // 由于旋转完的树的bf的值为-1所以不用继续循环}else if (cur-_right-_bf 1) //左单旋{RotateL(cur);// 下面这两步置零其实可以不用写因为在左旋的实现里面已经置零了// cur-_parent-_bf 0;// cur-_bf 0;prev cur-_parent;cur prev-_parent;continue;}else if (cur-_right-_bf -1) //先来一个右单旋 再来一个左单旋{RotateRL(cur);prev cur-_parent;cur prev-_parent;continue;}}else if(cur-_bf -2){if (cur-_left-_bf 0) // 这种情况是插入没有的这里要特殊处理一下{RotateR(cur);cur-_bf -1;cur-_parent-_bf 1;break;}else if (cur-_left-_bf -1) //右单旋{RotateR(cur);prev cur-_parent;cur prev-_parent;continue;}else if (cur-_left-_bf 1) // 先来一个左单旋 再来一个右单旋{RotateRL(cur);prev cur-_parent;cur prev-_parent;continue;}}}else{assert(false);}// 更新平衡因子if (cur cur-_left prev)cur-_bf;else if (cur cur-_right prev)cur-_bf--;}
}Ⅵ. AVL树的性能
AVL 树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过 1这样可以保证查询时高效的 时间复杂度即 O( l o g 2 n log_2 n log2n)。但是如果要对 AVL 树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。
因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑 AVL 树但一个结构经常修改就不太适合。
Ⅶ. AVL树的整体框架
前言中说到我们这里不实现 AVL 树的拷贝构造以及赋值重载但是我们这里会实现一下 operator[]毕竟 insert 函数的出现就是为了它的
operator[] 的实现代码
V operator[](const K key)
{pairNode*, bool res Insert(make_pair(key, V()));return res.first-_kv.second;
} 测试代码
#include AVLTree.hvoid TestTree1()
{AVLTreeint, int t;int arr[] { 3,10,1,2,9,4,5,6,7 };//int arr[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int arr[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : arr){t.Insert(make_pair(e, 1));}t.Inorder();cout t.IsAVLTree() endl;t[3] * 102;t[1] * 10;t[2] * 10;t.Inorder();t.Erase(3);t.Inorder();cout t.IsAVLTree() endl;t.Erase(1);t.Inorder();cout t.IsAVLTree() endl;t.Erase(1);t.Inorder();cout t.IsAVLTree() endl;t.Erase(2);t.Inorder();cout t.IsAVLTree() endl;t.Erase(4);t.Inorder();cout t.IsAVLTree() endl;t.Erase(5);t.Inorder();cout t.IsAVLTree() endl;t.Erase(6);t.Inorder();cout t.IsAVLTree() endl;t.Erase(7);t.Inorder();cout t.IsAVLTree() endl;t.Erase(8);t.Inorder();cout t.IsAVLTree() endl;t.Erase(9);t.Inorder();cout t.IsAVLTree() endl;t.Erase(10);t.Inorder();cout t.IsAVLTree() endl;t.Erase(10);t.Inorder();cout t.IsAVLTree() endl;
}int main()
{TestTree1();return 0;
}AVLTree.h
#pragma once
#include iostream
#include string
#include cassert
using namespace std;template class K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf; //该点的平衡因子 -- balance factorAVLTreeNode(const pairK, V kv): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};template class K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:AVLTree():_root(nullptr){}V operator[](const K key){pairNode*, bool res Insert(make_pair(key, V()));return res.first-_kv.second;}~AVLTree(){Destory(_root);_root nullptr;}pairNode*, bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return make_pair(_root, true);}// 先找到该节点Node* cur _root;Node* parent _root;while (cur ! nullptr){if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{return make_pair(cur, false);}}// 接着插入节点cur new Node(kv);Node* newnode cur; // 这一步是为了后面返回值返回的if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}// 1、更新平衡因子while (parent ! nullptr) // 或者while(cur ! _root){if (parent-_left cur){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){// 2、调整高度if (parent-_bf -2){if (cur-_bf -1){RotateR(parent); //右单旋}else if(cur-_bf 1){RotateLR(parent); //左右双旋}}else if (parent-_bf 2){if (cur-_bf 1){RotateL(parent); //左单旋}else if (cur-_bf -1){RotateRL(parent); //右左双旋 }}// 注意这里的break很关键因为我们调整了子树的平衡因子后它的父亲其实就已经不会有影响了break;}else{// 插入节点之前树已经不平衡了或者bf出错。需要检查其他逻辑assert(false);}}return make_pair(newnode, true);}void RotateR(Node* parent){// SubL: Parent的左孩子// SubLR: Parent左孩子的右孩子Node* subL parent-_left;Node* subLR subL-_right;// 先将parent的左子树连上subLR注意要双向链接parent-_left subLR;if (subLR ! nullptr)subLR-_parent parent;// 让parent作为subL的右子树subL-_right parent;Node* parent_parent parent-_parent; // 先将parent的parent记录下来后面链接要用到parent-_parent subL;// 判断一下parent是否为二叉树的根节点if (parent _root){_root subL;_root-_parent nullptr;}else{if (parent_parent-_left parent){parent_parent-_left subL;}else{parent_parent-_right subL;}subL-_parent parent_parent;}// 最后记得要将平衡因子置零subL-_bf parent-_bf 0;}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* parent_parent parent-_parent;parent-_parent subR;if (parent _root){_root subR;_root-_parent nullptr;}else{if (parent_parent-_left parent){parent_parent-_left subR;}else{parent_parent-_right subR;}subR-_parent parent_parent;}// 最后记得要将平衡因子置零subR-_bf parent-_bf 0;}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;// 旋转之前保存subLR的平衡因子旋转完成之后需要根据该平衡因子来调整其他节点的平衡因子int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 1){subL-_bf -1;subLR-_bf 0;parent-_bf 0;}else if (bf -1){subL-_bf 0;subLR-_bf 0;parent-_bf 1;}else if (bf 0){subL-_bf 0;subLR-_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){parent-_bf -1;subRL-_bf 0;subR-_bf 0;}else if (bf -1){parent-_bf 0;subRL-_bf 0;subR-_bf 1;}else if (bf 0){parent-_bf 0;subRL-_bf 0;subR-_bf 0;}else{assert(false);}}Node* Find(const K key){Node* cur _root;while (cur ! nullptr){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return nullptr;}bool Erase(const K key){if (_root nullptr)return false;Node* cur _root;Node* parent nullptr;while (cur ! nullptr){if (cur-_kv.first key){parent cur;cur cur-_left;}else if (cur-_kv.first key){parent cur;cur cur-_right;}else{// 找到了该节点准备删除// 1、左右都为空或者其中一个为空if (cur-_left nullptr || cur-_right nullptr){if (_root cur){if (cur-_left nullptr)_root _root-_right;else_root _root-_left;delete cur;// 平衡因子调节if(_root ! nullptr)_root-_bf 0;}else if (cur-_left nullptr cur-_right nullptr){if (parent-_left cur){parent-_left nullptr;parent-_bf;}else{parent-_right nullptr;parent-_bf--;}delete cur;// 调节高度Erase_rotate(parent);}else if (cur-_left nullptr cur-_right ! nullptr){cur-_kv cur-_right-_kv;delete cur-_right;cur-_right nullptr;// 调节高度cur-_bf--;Erase_rotate(cur);}else if (cur-_left ! nullptr cur-_right nullptr){cur-_kv cur-_left-_kv;delete cur-_left;cur-_left nullptr;// 调节高度cur-_bf;Erase_rotate(cur);}}else // 2、左右都不为空{Node* minRight cur-_right;Node* minParent cur;while (minRight-_left ! nullptr){minParent minRight;minRight minRight-_left;}cur-_kv minRight-_kv;// 将删除节点转化为上面左右都为空或者其中一个为空的情况解决if (cur minParent){if (minRight-_right ! nullptr){minRight-_kv minRight-_right-_kv;delete minRight-_right;minRight-_right nullptr;minRight-_bf;Erase_rotate(minRight);}else{minParent-_right nullptr;delete minRight;minParent-_bf--;Erase_rotate(minParent);}}else{if (minRight-_right ! nullptr){minRight-_kv minRight-_right-_kv;delete minRight-_right;minRight-_right nullptr;minRight-_bf;Erase_rotate(minRight);}else{minParent-_left nullptr;delete minRight;minParent-_bf;Erase_rotate(minParent);}}}return true;}}return false;}void Erase_rotate(Node* cur){Node* prev nullptr;while (cur ! nullptr){if (cur-_bf 1 || cur-_bf -1){break;}else if (cur-_bf 0){prev cur;cur cur-_parent;}else if (cur-_bf 2 || cur-_bf -2){if (cur-_bf 2){if (cur-_right-_bf 0) // 这种情况是插入没有的这里要特殊处理一下{RotateL(cur);cur-_parent-_bf -1;cur-_bf 1;break; // 由于旋转完的树的bf的值为-1所以不用继续循环}else if (cur-_right-_bf 1){RotateL(cur);// 下面这两步置零其实可以不用写因为在左旋的实现里面已经置零了// cur-_parent-_bf 0;// cur-_bf 0;prev cur-_parent;cur prev-_parent;continue;}else if (cur-_right-_bf -1){RotateRL(cur);prev cur-_parent;cur prev-_parent;continue;}}else if(cur-_bf -2){if (cur-_left-_bf 0) // 这种情况是插入没有的这里要特殊处理一下{RotateR(cur);cur-_bf -1;cur-_parent-_bf 1;break;}else if (cur-_left-_bf -1){RotateR(cur);prev cur-_parent;cur prev-_parent;continue;}else if (cur-_left-_bf 1){RotateRL(cur);prev cur-_parent;cur prev-_parent;continue;}}}else{assert(false);}// 更新平衡因子if (cur cur-_left prev)cur-_bf;else if (cur cur-_right prev)cur-_bf--;}}bool IsAVLTree(){return IsBalanceTree(_root);}void Inorder(){_Inorder(_root);cout endl;}
private:void Destory(Node* root){if (root nullptr)return;Destory(root-_left);Destory(root-_right);delete root;}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);}int Height(Node* root){if (root nullptr)return 0;int leftH Height(root-_left);int rightH Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}bool IsBalanceTree(Node* root){if (root nullptr)return true;int leftH Height(root-_left);int rightH Height(root-_right);// 检查一下平衡因子是否正确 (右平衡因子 - 左平衡因子)if (rightH - leftH ! root-_bf){cout 平衡因子异常: root-_kv.first endl;return false;}if (abs(rightH - leftH) 2)return false;return IsBalanceTree(root-_left) IsBalanceTree(root-_right);}Node* _root;
};
