对AVL树首先要弄清它的定义:AVL树是一棵高度平衡的二叉搜索树,它要么是一棵空树要么是一棵左右子树均为AVL树,且左右子树高度差的绝对值不大于一的二叉搜索树数据结构教科书介绍的AVL树平衡化旋转共有四种方式:LR左单旋转,RR右单旋转,LRR先左后右双旋转,RLR先右后左双旋转,LR和RRLRR和RLR互为镜像,若不熟悉请参看数据结构教科书,下面要对保证AVL树插入删除操作正确性的原理进行简单的讨论。当在AVL树中删除一个节点时按对二叉搜索树执行删除节点操作时采用的方式找到待删除节点但由二叉搜索树删除算法(请参看数据结构教科书)可知待删除节点不一定是实际删除节点在某些情况下待删除节点没有被实际删除而是将非待删除节点的实际删除节点的数据域替换带删除节点的数据域此后删除的是实际被删除的节点而不是带删除节点当然在另一些情况下,待删除节点就是实际删除节点。这样每当按对二叉搜索树执行删除操作的方式成功删除(注意待删除节点未必被实际删除)AVL树中的待删除节点后,通过指针定位到实际被删除节点的父节点及该父节点的被实际删除节点的子树的根节点,设指向该父节点的指针为parent指向实际被删除节点的该父节点的子树的根节点的指针为q(可能为NULL)那么分别讨论可知,无论在AVL树中对待删除节点执行删除操作对应删除二叉搜索树中节点时可能出现的哪一种情形,以parent为根的子树总满足以下条件A1.以parent指向的节点为根节点的子树在执行删除操作前是AVL树(由AVL树定义)2.以q指向的节点为根节点的子树在被删除一个节点后经过一系列或不经过平衡化旋转后,其高度相比删除前下降一,并且仍然为AVL树以此为基础我们来寻找循环不变量现假设存在一棵以parent指向的节点为根节点的二叉搜索树,在对它的子树执行删除操作前它是AVL树且该树是执行删除操作前原AVL树的一棵子树若在parent的左子树或右子树上按对二叉搜索树执行删除的方式删除一个节点后经过一系列或不经过平衡化旋转后,左子树的高度相比于删除前下降一并且仍然为AVL树(即parent树满足条件A),q为指向此时该子树根节点的指针,则对parent树而言有如下几种情形:情形A以parent指向的节点为根节点的AVL树A在执行删除前根节点平衡因子为0,在parent的左子树上删除一个节点并做或不做平衡化旋转调整后左子树高度下降一,此时parent平衡因子变为1,由于作删除操作的AVL树A满足条件A,以此为依据根据AVL树定义不难验证这时parent树仍然为AVL树,当然其高度相比于删除前没有任何变化,于是从树A根节点到原AVL树根节点的路径上各节点(除树A根节点)的平衡因子仍然和删除前相同,即这些节点仍然平衡,于是按AVL树的定义从A的根节点的父节点到原树根节点逐层向上递推,最后即得以A根节点到原树父节点的路径上的节点为根节点的子树均为AVL树,当然原树仍然为AVL树于是可以结束平衡化过程情形A*和情形A对称,分析是类似的,此时对树A不做任何平衡化旋转,原树已平衡,结束平衡化过程情形B以parent指向的节点为根节点的AVL树A在执行删除前根节点平衡因子为-1,在parent的左子树上删除一个节点并做或不做平衡化旋转调整后左子树高度下降一,此时parent平衡因子变为0由于作删除操作的AVL树A满足条件A,以此为依据根据AVL树定义不难验证这时parent树仍然为AVL树且其高度相比于删除节点前下降一,此时不对A做任何平衡化旋转这样就可以发现树A满足在树A上按对二叉搜索树执行删除的方式删除一个节点后经过一系列或不经过平衡化旋转后,树A的高度相比于删除前下降一并且仍然为AVL树注意到树A高度降一影响到其根节点父节点平衡因子有可能使其失衡所以令parent为树A根节点的父节点,q为树A根节点回溯至上一层再按各种情形进行相应的处理。这样做是合理的因为此时以parent为根的子树(q为parent左子树或右子树根节点)刚好满足条件A这样就能就各种情形以相同的方式进行同样的处理情形C以parent指向的节点为根节点的AVL树A右子树根节点平衡因子为0在执行删除前根节点平衡因子为1,在parent的左子树上删除一个节点并做或不做平衡化旋转调整后左子树高度下降一,此时parent平衡因子变为2,树A失衡于是对树A做左单旋转由于作删除操作的AVL树A满足条件A以此为依据根据AVL树定义不难验证左单旋转后的树A仍然为AVL树,且其高度相比于删除前没有任何变化于是从树A根节点到原AVL树根节点的路径上各节点(除树A根节点)的平衡因子仍然和删除前相同,即这些节点仍然平衡,于是按AVL树的定义从A的根节点的父节点到原树根节点逐层向上递推,最后即得以A根节点到原树父节点的路径上的节点为根节点的子树均为AVL树,当然原树仍然为AVL树这样就可以结束平衡化过程情形C*和情形C对称,分析是类似的,此时对树A做右单旋转,然后原树已平衡,结束平衡化过程情形D以parent指向的节点为根节点的AVL树A右子树根节点平衡因子为1在执行删除前根节点平衡因子为1,在parent的左子树上删除一个节点并做或不做平衡化旋转调整后左子树高度下降一,此时parent平衡因子变为2树A失衡于是对树A做左单旋转。由于作删除操作的AVL树A满足条件A,以此为依据根据AVL树定义不难验证左单旋转后的树A仍然为AVL树且其高度相比于删除节点前下降一,这样就可以发现树A满足在树A上按对二叉搜索树执行删除的方式删除一个节点后经过一系列或不经过平衡化旋转后,树A的高度相比于删除前下降一并且仍然为AVL树注意到树A高度降一影响到其根节点父节点平衡因子有可能使其失衡所以令parent为树A根节点的父节点,q为树A根节点回溯至上一层再按各种情形进行相应的处理。这样做是合理的因为此时以parent为根的子树(q为parent左子树或右子树根节点)刚好满足条件A这样就能就各种情形以相同的方式进行同样的处理情形D*和情形D对称,分析是类似的,此时对树A做右单旋转,然后回溯至上一层继续平衡化情形E以parent指向的节点为根节点的AVL树A右子树根节点平衡因子为-1,在执行删除前根节点平衡因子为1,在parent的左子树上删除一个节点并做或不做平衡化旋转调整后左子树高度下降一,此时parent平衡因子变为2树A失衡于是对树A做先右后左双旋转。由于作删除操作的AVL树A满足条件A,以此为依据根据AVL树定义不难验证先右后左双旋转后的树A仍然为AVL树且其高度相比于删除节点前下降一,这样就可以发现树A满足在树A上按对二叉搜索树执行删除的方式删除一个节点后经过一系列或不经过平衡化旋转后,树A的高度相比于删除前下降一并且仍然为AVL树注意到树A高度降一影响到其根节点父节点平衡因子有可能使其失衡所以令parent为树A根节点的父节点,q为树A根节点回溯至上一层再按各种情形进行相应的处理。这样做是合理的因为此时以parent为根的子树(q为parent左子树或右子树根节点)刚好满足条件A这样就能就各种情形以相同的方式进行同样的处理情形E*和情形E对称,分析是类似的,此时对树A做先左后右双旋转,然后回溯至上一层继续平衡化从以上讨论就可以看出循环不变量了,它就是parent子树满足的条件A,如果parent子树满足条件A且对应A,A* 两种情形则不做平衡化旋转并结束平衡化,如果对应C,C*两种情形则做单旋转并结束平衡化,如果对应BB*两种情形则不做平衡化旋转并回溯至上一层平衡化(以parent父节点为根的子树满足条件A),若对应D,D*两种情形则做单旋转并回溯至上一层平衡化(以parent父节点为根的子树满足条件A)若对应EE*两种情形则做双旋转并回溯至上一层平衡化(以parent父节点为根的子树满足条件A).由此可以总结出删除AVL树某节点过程中经历的平衡化过程如下从本文开头提及的最初的parent子树开始,该parent子树满足条件A,q为parent子树被删除节点的子树的根节点指针(可能为NULL).AVL树删除算法(调整平衡因子的细节没有给出,请参考下方代码):(1)在AVL树上执行二叉搜索树删除算法,之后令parent为实际被删除节点的父节点,q为实际被删节点所在的该父节点的子树的根节点的指针(2) if(parent子树对应于A,A* C,C*情形)A,A*情形,直接转3C情形 parent子树左单旋转, 然后转3C*情形 parent子树右单旋转, 然后转3elseB,B*情形 如果 parent为根节点转3 否则 qparent parentparent父节点转2D情形 parent子树左单旋转 随后如果 parent为根节点转3 否则qparent parentparent父节点 转2D*情形 parent子树右单旋转 随后如果 parent为根节点转3 否则qparent parentparent父节点 转2E情形 parent子树先右后左双旋转 随后如果 parent为根节点转3 否则qparent parentparent父节点 转2E*情形 parent子树先左后右双旋转 随后如果 parent为根节点转3 否则qparent parentparent父节点 转2(3)结束在这里发表一些个人看法,一些数据结构教科书上(如数据结构与算法分析:java语言描述)提到AVL树删除算法的正确编写有一定难度,实际上并非如此.从以上算法来看,编程实现时思路的推进完全是线性的根本没有难度。非要说实现难度大那也只能是琐碎的编码细节令人抓狂事实上从以上算法来看删除算法本质上非常简单,并不复杂,编写代码只需用心就能正确实现删除算法下面讨论AVL树的插入插入操作和删除相比更为简单,实现难度更低分析插入操作还是要先寻找循环不变量首先插入新节点后只有新节点父节点至根节点的路径上的节点的平衡因子受影响,以路径上各节点为根的子树的高度要么加一要么不变即平衡因子要么加减一要么不变。因此路径上各节点的平衡因子在插入新节点后的范围在-2至2之间按最一般情形考虑插入新节点(在非空树中插入)后,令parent为新插入节点父节点,q为新插入节点。若插入后parent平衡因子(不是为-1就是为0)为0,则根据定义不难验证原树已平衡为AVL树,这样就可以结束平衡化过程,若平衡因子为-1(插入前parent为叶节点),则令qparent,parent为其父节点,这样parent子树满足条件B:q为AVL树 插入前q平衡因子为0,插入后绝对值为1,q高度相比于插入前加一,且此时没有对q或其子树做平衡化旋转这样设有一棵原AVL树的子树,根节点为parent,parent的按二叉搜索树插入方式插入节点的子树根节点为q,parent满足条件B。根据节点插入parent右子树或左子树加减parent平衡因子,调整parent平衡因子为插入后平衡因子。然后如果parent平衡因子为-1,则插入前为0且parent高度相比于插入前加一插入后parent仍然为AVL树此时不对parent进行平衡化旋转,由于parent插入后高度加一parent父节点的平衡因子受到影响,因此令qparent,parentparent父节点回溯到上一层按所列各情形进行平衡化操作。这样做是合理的,因为根据上述分析回溯到上一层后parent子树满足条件B所以完全可以按照各情形以相同方式进行相同处理如果parent平衡因子为0,则插入前parent平衡因子绝对值为1,即新节点在较矮的子树上插入插入后parent左右子树等高不难看出插入后parent子树仍为AVL树且高度相比于插入前不变于是沿从parent父节点到原AVL树根节点的路径层层向上递推即可验证插入后原树仍为AVL树故此时可结束平衡化过程若parent平衡因子绝对值为2,则有以下几种情形:情形一插入后parent平衡因子为-2,q平衡因子为-1,即在q的左子树上插入,左子树在插入后高度加一,q为parent左子树此时直接对parent做右单旋转根据做平衡化旋转前的parent树满足条件B和AVL树定义可验证旋转后parent仍然为AVL树且高度相比于插入前不变这样原树已平衡直接结束平衡化过程情形一*和情形一对称插入后parent平衡因子为2,q平衡因子为1,即在q的右子树上插入,右子树在插入后高度加一q为parent右子树,此时对parent做左单旋转并结束平衡化过程情形二插入后parent平衡因子为-2,q平衡因子为1,即在q的右子树上插入,q为parent左子树q的右子树插入后高度增一故必有q的右子女p(树C的根)。由于是在子树p上插入,所以p一定为从最初的parent子树的根节点至q的回溯路径上的一个节点因此插入后p的平衡因子为-1,插入前为0因此一定为在p的两棵等高子树之一上插入,插入后子树p的高度状况如上图所示此时直接对parent做先左后右双旋转根据做平衡化旋转前的parent树满足条件B和AVL树定义可验证旋转后parent仍然为AVL树且高度相比于插入前不变这样原树已平衡直接结束平衡化过程情形二*和情形二对称分析是类似的插入后parent平衡因子为2,q平衡因子为-1,即在q的左子树上插入,q为parent右子树q的左子树插入后高度增一故必有q的左子女p(树C的根)。由于是在子树p上插入,所以p一定为从最初的parent子树的根节点至q的回溯路径上的一个节点因此插入后p的平衡因子为-1,插入前为0因此一定为在p的两棵等高子树之一上插入,插入后子树p的高度状况如上图所示此时直接对parent做先右后左双旋转根据做平衡化旋转前的parent树满足条件B和AVL树定义可验证旋转后parent仍然为AVL树且高度相比于插入前不变这样原树已平衡直接结束平衡化过程由以上讨论可以看出循环不变量就是parent子树满足的条件B,如果parent子树满足条件B,那么若parent在插入后的平衡因子绝对值为1则令qparent parentparent父节点 回溯到上一层继续按文中列出的情形进行平衡化,若parent在插入后的平衡因子为0,则直接结束平衡化过程,若parent在插入后的平衡因子绝对值为2此时若parent子树对应情形一则对parent子树执行右单旋转并结束平衡化过程,对应情形一*则对parent子树执行左单旋转并结束平衡化过程对应情形二则对parent子树执行先左后右双旋转并结束平衡化过程对应情形二*则对parent子树执行先右后左双旋转并结束平衡化过程。根据上述分析按和分析删除操作类似的方式就可以总结出AVL树的插入算法可以自行分析这里就不赘述了。下面是删除与插入操作的具体代码实现代码中加入判断是否为AVL树的代码(非递归)以检验删除操作的正确性也就是每次删除插入成功后用判断函数检验删除插入后的二叉树是否为AVL树从而检验插入删除算法的正确性#include stack #include vector #include iostream #include string #include cmath #include algorithm #include random #include ctime using namespace std; #define TYPE int template typename T struct AVLNode //AVL树节点类 { int bf; //节点平衡因子 T data; //节点数据域 AVLNode* left; AVLNode* right; AVLNode(int b, T d) :bf(b), data(d), left(nullptr), right(nullptr) {} }; template typename T void RotateLR(AVLNodeT* ptr) //对以ptr为根的子树执行先左后右双旋转,ptr成为旋转后新树根节点指针 { AVLNodeT* p ptr-left; AVLNodeT* q p-right; p-right q-left; q-left p; ptr-left q-right; q-right ptr; if (q-bf 0) { p-bf ptr-bf 0; } else { if (q-bf -1) { p-bf 0; ptr-bf 1; } else { p-bf -1; ptr-bf 0; } q-bf 0; } ptr q; } template typename T void RotateRL(AVLNodeT* ptr) //对以ptr为根的子树执行先右后左双旋转,ptr成为旋转后新树根节点指针 { AVLNodeT* p ptr-right; AVLNodeT* q p-left; p-left q-right; q-right p; ptr-right q-left; q-left ptr; if (q-bf 0) { p-bf ptr-bf 0; } else { if (q-bf -1) { p-bf 1; ptr-bf 0; } else { p-bf 0; ptr-bf -1; } q-bf 0; } ptr q; } template typename T void RotateR(AVLNodeT* ptr) //对以ptr为根的子树执行右单旋转,ptr成为旋转后新树根节点指针 { AVLNodeT* p ptr-left; ptr-left p-right; p-right ptr; if (p-bf -1) { p-bf ptr-bf 0; } else { p-bf 1; } ptr p; } template typename T void RotateL(AVLNodeT* ptr) //对以ptr为根的子树执行左单旋转, ptr成为旋转后新树根节点指针 { AVLNodeT*p ptr-right; ptr-right p-left; p-left ptr; if (p-bf 0) { p-bf -1; ptr-bf 1; } else { ptr-bf p-bf 0; } ptr p; } template typename T int Searchd(AVLNodeT* ptr, int d) { if (d 2) return 0; else { if (d 1) { if (ptr-right nullptr) return 0; else return 2; } else { if (ptr-left ! nullptr) return 1; else { if (ptr-right ! nullptr) return 2; else return 0; } } } } template typename T bool isAVL(AVLNodeT* root) //判断以root为根节点的二叉树是否为AVL树 { struct memory { AVLNodeT* p; int direction; T lmin; int lh 0; //节点左子树高度 memory(AVLNodeT* p, int d) :p(p), direction(d) {} }; T rmin; T rmax; T lmax; int rh; int d 0; AVLNodeT* ptr root; AVLNodeT* const dest ptr; stackmemory arrange; bool TF false; while (true) { if (Searchd(ptr, d) 0) { if (ptr dest) { if (d 0) return true; } if (d 0) { if (arrange.top().direction 1) { arrange.top().lh 1; arrange.top().lmin ptr-data; lmax ptr-data; } else { rh 1; rmin ptr-data; rmax ptr-data; } } else { if (d 1) { if (lmax ptr-data) { cout 当前树非二叉搜索树,也非AVL树 endl; return false; } if (arrange.top().lh 1) { cout 存在左右子树高度差绝对值大于一的子树,原树非AVL树 endl; return false; } if (ptr dest) return true; T lmin arrange.top().lmin; int lh arrange.top().lh; arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin lmin; arrange.top().lh lh 1; lmax ptr-data; } else { rmin lmin; rmax ptr-data; rh lh 1; } } else { if (rmin ptr-data) { cout 当前树非二叉搜索树,也非AVL树 endl; return false; } if (abs(rh - arrange.top().lh) 1) { cout 存在左右子树高度差绝对值大于一的子树,原树非AVL树 endl; return false; } if (ptr dest) return true; if (ptr-left nullptr) { arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin ptr-data; lmax rmax; arrange.top().lh rh 1; } else { rmin ptr-data; rh; } } else { T lmin arrange.top().lmin; int lh arrange.top().lh; arrange.pop(); if (arrange.top().direction 1) { arrange.top().lmin lmin; arrange.top().lh max(lh, rh) 1; lmax rmax; } else { rmin lmin; rh max(lh, rh) 1; } } } } ptr arrange.top().p; d arrange.top().direction; } else { AVLNodeT* interval nullptr; if (d 0) { arrange.push(memory(ptr, Searchd(ptr, d))); if (arrange.top().direction 1) ptr ptr-left; else ptr ptr-right; } else { if (ptr-data lmax) { cout 当前树非二叉搜索树,也非AVL树 endl; return false; } arrange.top().direction 2; ptr ptr-right; } d 0; } } } template typename T void linkWithUpper(AVLNodeT* parent, AVLNodeT* original, AVLNodeT* _new) { if (original parent-left) { parent-left _new; } else { parent-right _new; } } template typename T bool executeDelete(AVLNodeT* parent, AVLNodeT* q, AVLNodeT* p, AVLNodeT* left_or_right, stackAVLNodeT* stackforflashback) { if (stackforflashback.empty()) //被删节点有父节点 { parent left_or_right; delete p; //删除被删节点后原AVL树恢复平衡,parent为根节点结束 return true; } parent stackforflashback.top(); stackforflashback.pop(); if (parent-left p) parent-left left_or_right; //将被删节点左子树或右子树链接至被删节点父节点相应链指针并删除被删节点 else parent-right left_or_right; q left_or_right; //parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树或右子树根节点指针 delete p; return false; } template typename T void executeDelete(AVLNodeT* q, AVLNodeT* p, AVLNodeT* left_or_right) { left_or_right q-right; //left_o_right为parent-left时用该节点数据域替换被删节点数据域,将其右子树链接至其父节点左链指针,随后删除该节点 p-data q-data; //left_o_right为p-right时用被删节点右子女数据域替换被删节点指针域,将右子女右子树链接至被删节点右链指针,并删除右子女 delete q; q left_or_right; //left_o_right为parent-left时parent为需要做或不做平衡化旋转的第一棵子树根节点指针,q为该子树左子树根节点指针 } template typename T AVLNodeT* DelAVL(AVLNodeT* root, T key) //在以root为根节点的AVL树中删除关键码key { //AVL树的删除 AVLNodeT* p root; stackAVLNodeT* stackforflashback; while (p ! nullptr) //搜索被删除节点,同时将回溯路径记录在栈中 { if (p-data key) break; else { stackforflashback.push(p); if (key p-data) { p p-left; } else { p p-right; } } } if (p ! nullptr) //被删除节点存在,被p指向 { AVLNodeT* parent nullptr; AVLNodeT* q nullptr; if (p-left ! nullptr p-right ! nullptr) //被删节点左右子树均存在 { q p-right; parent p; if (q-left ! nullptr) //被删节点右子树根节点有左子树 { while (q-left ! nullptr) //在被删节点右子树根节点左子树中搜索中序遍历的第一个节点,同时用栈记录回溯路径 { stackforflashback.push(parent); parent q; q q-left; } executeDelete(q, p, parent-left); } else executeDelete(q, p, p-right); } else { if (p-left ! nullptr) //被删节点左子树不空,右子树空 { if (executeDelete(parent, q, p, p-left, stackforflashback)) return parent; } else if (p-right ! nullptr) //处理过程和以上情形完全对称 { if (executeDelete(parent, q, p, p-right, stackforflashback)) return parent; } else //被删节点为叶节点 { if (executeDelete(parent, q, p, static_castAVLNodeT*(nullptr), stackforflashback)) return parent; } } bool TF false; if (parent-right nullptr parent-left nullptr) { parent-bf 0; if (stackforflashback.empty()) return root; q parent; parent stackforflashback.top(); stackforflashback.pop(); } bool before; do { if (TF true) { if (!before) { linkWithUpper(stackforflashback.top(), q, parent); if (parent-bf ! 0) return root; } q parent; parent stackforflashback.top(); stackforflashback.pop(); } else { TF true; } bool l parent-left q; if (parent-bf 0) { if (l) parent-bf 1; //情形a else parent-bf -1; //情形a* return root; } if (l ? parent-bf 1 : parent-bf -1) { q parent; if (l) { p parent-right; if (p-bf ! -1) RotateL(parent); //对以parent为根的子树执行左单旋转 //情形c //情形d //对以parent为根的子树执行左单旋转 else //情形e RotateRL(parent);//对以parent为根的子树执行先右后左双旋转 } else { p parent-left; if (p-bf ! 1) //情形c* RotateR(parent);//对以parent为根的子树执行右单旋转 //情形d* //对以parent为根的子树执行右单旋转 else //情形e* RotateLR(parent);//对以parent为根的子树执行先左后右双旋转 } before false; } else { before true; } if (before) parent-bf 0; } while (stackforflashback.empty() false); return parent; //原AVL树已恢复平衡,返回根节点 } else { cout AVL树中不存在要删除的数据元素,删除失败 endl; return nullptr; } } template typename T AVLNodeT* InsertAVL(AVLNodeT* root, T key) { //AVL树的插入 if (root nullptr) return new AVLNodeT(0, key); else { stackAVLNodeT* stackforflashback; AVLNodeT* p root; while (p ! nullptr) //搜索插入位置 { stackforflashback.push(p); if (key p-data) p p-left; else if (key p-data) p p-right; else { cout 要插入的关键字在AVL树中已存在,插入失败 endl; return nullptr; } } p new AVLNodeT(0, key); if (key stackforflashback.top()-data) { stackforflashback.top()-left p; //新节点插入并调整父节点平衡因子 } else { stackforflashback.top()-right p; } AVLNodeT* parent nullptr; while (stackforflashback.empty() false) { parent stackforflashback.top(); stackforflashback.pop(); if (parent-left p) --parent-bf; else parent-bf; if (parent-bf 0) return root; //已平衡,返回根节点 else if (parent-bf -1 || parent-bf 1) p parent; //以parent为根的子树已平衡其高度加一回溯至父节点 else { AVLNodeT* q parent; if (parent-bf -2) { if (p-bf 1) RotateLR(parent);//对parent为根的子树执行先左后右双旋转 //已平衡 else RotateR(parent);//对以parent为根子树执行右单旋转 //已平衡 } else { if (p-bf -1) { RotateRL(parent);//对parent为根的子树执行先右后左双旋转 //已平衡 } else { RotateL(parent);//对以parent为根的子树执行左单旋转 //已平衡 } } if (stackforflashback.empty() false) { linkWithUpper(stackforflashback.top(), q, parent); return root; //返回恢复平衡的AVL树根节点 } return parent; } } return p; //原AVL树已平衡,返回根节点 } } template typename T struct memory { AVLNodeT* p; int direction; int last; memory(AVLNodeT* p, int d, int l) :p(p), direction(d), last(l) {} }; template typename T void set(stackmemoryT arrange) { if (arrange.top().last 0) { if (arrange.top().direction 1) { arrange.top().last 1; } else { cout ,; arrange.top().last 2; } } else { cout ,; arrange.top().last 2; } } template typename T void output(AVLNodeT* ptr) //输出以ptr为根的AVL树对应的广义表形式 { int d 0; AVLNodeT* const dest ptr; stackmemoryT arrange; while (true) { if (Searchd(ptr, d) 0) { if (ptr dest) { if (d 0) cout ptr-data (; else { if (arrange.top().last 1) cout , ; } cout ); break; } else { if (d 0) { set(arrange); cout ptr-data; } else { if (arrange.top().last ! 2) cout , ; cout ); arrange.pop(); } ptr arrange.top().p; d arrange.top().direction; } } else { AVLNodeT* interval nullptr; if (d 0) { if (arrange.empty() false) set(arrange); cout ptr-data (; arrange.push(memoryT(ptr, Searchd(ptr, d), 0)); if (arrange.top().direction 1) ptr ptr-left; else ptr ptr-right; } else { arrange.top().direction 2; ptr ptr-right; } d 0; } } } void printNULL(size_t num) { for (size_t o 1; o num; o) cout ; cout NULL endl; } template typename T void printAVLTree(AVLNodeT* root, size_t offset) { if (root nullptr) cout NULL空树 endl;; for (int i 1; i offset; i) cout ; string s to_string(root-data); offset s.size() 4; cout s : bf; if (root-bf -1) { cout -1; offset 2; } else if (root-bf 1) { cout 1; offset 2; } else { cout 0; offset 1; } cout endl; if (root-left nullptr) { if (root-right ! nullptr) { printNULL(offset); printAVLTree(root-right, offset); } } else { printAVLTree(root-left, offset); if (root-right nullptr) { printNULL(offset); } else printAVLTree(root-right, offset); } } int main() { const int N 2000; //vectorTYPE insertvalue{ 13, 5, 3, 2, 1, 4, 10, 8, 7, 6, 9, 11, 12, 16, 14, 15, 18, 17, 20, 19 }; vectorTYPE insertvalue; for (int i 1; i N; i) { insertvalue.push_back(i); } shuffle(insertvalue.begin(), insertvalue.end(), default_random_engine()); AVLNodeTYPE* root nullptr; for (vectorTYPE::const_iterator p insertvalue.cbegin(); p ! insertvalue.cend(); p) { cout 插入节点 *p endl; root InsertAVL(root, *p); //output(root); cout endl; if (isAVL(root) true) { cout 当前树是AVL树; cout endl; } else { cerr 错误当前树不是AVL树! endl; exit(0); } } cout endl; //cout 插入完成后删除前AVL树为: endl; //printAVLTree(root, 0); //cout 插入完成后删除前AVL树对应的广义表形式为: endl; //output(root); cout endl; cout endl; for (vectorTYPE::const_iterator p insertvalue.cbegin(); p ! insertvalue.cend(); p) { cout 删除节点 *p endl; root DelAVL(root, *p); if (root ! nullptr) { //printAVLTree(root, 0); cout endl; if (isAVL(root) true) { cout 当前树是AVL树; cout endl; } else { cerr 错误当前树不是AVL树! endl; exit(0); } } else cout NULL; cout endl; } return 0; }