哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：查找结构与排序算法实验题目：建立A VL树目录目录 (2)一、实验目的 (3)二、实验要求及实验环境 (3)1.实验要求： (3)2.实验环境： (3)三、设计思想 (3)1．逻辑设计 (3)(1)平衡查找二叉树 (3)(2)平衡因子 (4)(3)失衡情况与修正操作 (4)2．物理设计 (5)(1)存储结构 (5)(2)建立平衡二叉查找树 (6)(3)插入新结点 (6)(4)删除结点 (11)四、测试结果 (15)五、系统不足与经验体会 (15)六、附录：源代码（带注释） (16)一、实验目的通过实现A VL树的建立、插入与删除，掌握A VL树结构。

二、实验要求及实验环境1.实验要求：要求：1.具有插入（建立）、删除和查找功能2.插入操作应包括四种类型的平衡化处理3.删除操作应包括四种类型的平衡化处理并且包括多次平衡化处理4.能体现操作前后二叉树的形态及其变化2.实验环境：Microsoft Windows7, Code：：Blocks 10.05三、设计思想1．逻辑设计(1)平衡查找二叉树平衡二叉树的定义是：平衡二叉树或为空树，或满足下列特征：A若其左子树非空，则左子树上所有结点的关键字值都小于根节点关键字值B若其右子树非空，则右子树上所有结点的关键字值都大于根节点关键字值C根节点的左右子树高度之差的绝对值不超过1D根节点的左子树和右子树仍为A VL树平衡查找二叉树不会退化为线性链表，因此时间复杂度比较稳定。

(2)平衡因子为了更好地实现平衡查找二叉树，引进平衡因子Balanced Factor。

平衡因子的值为一个结点的左子树与右子树的高度之差，对于A VL树中的结点而言，BF只能是-1,0,和1。

当插入或删除操作导致平衡二叉查找树的某个结点的平衡因子偏离正确范围时，就可以及时进行修正操作，以保证二叉树保持平衡。

(3)失衡情况与修正操作从平衡二叉查找树出发，插入或删除某个结点后，二叉树失衡，从最底层结点来看只有四种可能：LL型：新结点插入到根节点的左子树的左子树上导致失衡。

对这种情况，应该顺时针旋转原树并进行相应修改：RR型：新结点插入到根节点的右子树的右子树上导致失衡。

对这种情况，应该顺时针旋转原树并进行相应修改：LR型：新结点插入到根节点的左子树的右子树上导致失衡。

对这种情况，应该先逆时针再顺时针旋转原树并进行相应修改：RL型：新结点插入到根节点的右子树的左子树上导致失衡。

对这种情况，应该先顺时针再逆时针旋转原树并进行相应修改：对于删除操作，由于被删除结点可能位于树的内部，需要进一步考虑更多操作。

2．物理设计(1)存储结构基础结构：平衡树结点组合结构：平衡树(2)建立平衡二叉查找树实现操作的主函数为：此函数只是接收参数。

其具体实现依赖于将要提及的插入函数。

(3)插入新结点插入的主函数为：根据插入元素的大小决定插入哪株子树。

如果插入成功，如树增高，根据增长的不同程度决定是否、如何旋转。

插入的过程中会调用平衡树的调整函数。

其中旋转操作的实现函数为：分别实现对特定结点的“旋转”操作。

而要在插入过程中实现调平，还需要更进一步的函数：调平时也结合平衡因子进行判定，并采取相应行为。

针对右子树的调平大体类似。

(4)删除结点删除过程中，对于被删除的结点，如果其左右子树有一为空，则可以以另一子树的根节点替代其地位。

否则，删除后须继续考虑调平。

此处的调平有利用前面的部分函数，也有一些新的函数：删除操作的从函数。

其有二级从函数：四、测试结果输入-1后开始选择函数五、系统不足与经验体会1.没有找到更直观的显示方式，界面不够友好；2.没有输出到文件中，读取不方便。

六、附录：源代码（带注释）见附件。

#include <iostream>using namespace std;const int MAXI = 100;const int LH = 1;const int EH = 0;const int RH = -1;class BSTNode{public:BSTNode(){data = 0;bf = EH;lchild = NULL;rchild = NULL;};~BSTNode(){if(lchild != NULL){lchild->~BSTNode();}if(rchild != NULL){rchild->~BSTNode();}}int data;int bf;//Balance FactorBSTNode *lchild, *rchild;};class BSTpublic:BST(){root = NULL;taller = 0;shorter = 0;}~BST(){};BSTNode *R_Rotate(BSTNode *CurrPTR){BSTNode *TempL = NULL;TempL = CurrPTR->lchild;CurrPTR->lchild = TempL->rchild;TempL->rchild = CurrPTR;CurrPTR = TempL;return CurrPTR;}BSTNode *L_Rotate(BSTNode *CurrPTR){BSTNode *TempR = NULL;TempR = CurrPTR->rchild;CurrPTR->rchild = TempR->lchild;TempR->lchild = CurrPTR;CurrPTR = TempR;return CurrPTR;}void L_Balance(BSTNode *CurrPTR);void R_Balance(BSTNode *CurrPTR);void Establish();bool Insert(int InVal);bool Insert(BSTNode *CurrPTR, int InVal);void Search_M();bool Search_S(BSTNode *CurrPTR, int InVal);void Display_M();void Display_S(BSTNode *CurrPTR, int Height);void Delete_S_L(BSTNode *CurrPTR);void Delete_S_R(BSTNode *CurrPTR);void Delete_S(BSTNode *CurrPTR, BSTNode *NextPTR);bool Delete_M(BSTNode *CurrPTR, int DelVal);private:BSTNode *root;bool taller;bool shorter;};void Selection();int main(){cout << "Hello world!" << endl;cout << "Balanced Selection Tree of Kirov_Tujin." << endl << "main :: Orders:" << endl<< "E. Establish a Balanced Selection Tree." << endl<< "Q. Quit the program." << endl;Selection();return 0;}void Selection(){BST Tree;char Order = 0;bool Selecting = 0;while(Selecting == 0){cout << "Selection 1:Input your Order." << endl;cin >> Order;switch (Order){case 'E':{Selecting = 1;Tree.Establish();break;}case 'Q':{cout << "Selection 1:Quit?('Y' to Quit.)" << endl;cin >> Order;if(Order == 'Y'){return;}else{cout << "Selection 1:Quit:Illegal Input." << endl;}break;}default :{cout << "Selection 1:Illegal Input." << endl;}}}cout << "Selection :: Orders:" << endl<< "S. Search for a key-word." << endl<< "I. Insert a key-word into the tree." << endl<< "D. Delete a key-word from the tree." << endl<< "P. Display the tree." << endl<< "Q. Quit the program." << endl;while(Selecting){cout << "Selection 2:Input your Order." << endl;cin >> Order;switch (Order){case 'S':{cout << "Selection 2:Searching." << endl;Tree.Search_M();cout << "Selection 2:Search Finished." << endl;break;}case 'I':{cout << "Selection 2:Inserting." << endl;int InVal = 0;cout << "Input the value you want." << endl;cin >> InVal;Tree.Insert(InVal);cout << "Selection 2:Insertion Finished." << endl;break;}case 'D':{cout << "Selection 2:Deleteing." << endl;;cout << "Selection 2:Deleting Finished." << endl;break;}case 'P':{cout << "Selection 2:Displaying." << endl;Tree.Display_M();cout << "Selection 2:Display Finished." << endl;break;}case 'Q':{cout << "Selection 2:Quit?('Y' to Quit.)" << endl;cin >> Order;if(Order == 'Y'){return;}else{cout << "Selection 2:Quit:Illegal Input." << endl;}break;}default :{cout << "Selection 2:Illegal Input." << endl;}}}cout << "Selection ended." << endl;return;}void BST :: L_Balance(BSTNode *CurrPTR){BSTNode *TempL = NULL, *TempL_R = NULL;TempL = CurrPTR->lchild;switch (TempL->bf){case LH:{R_Rotate(CurrPTR);CurrPTR->bf = EH;TempL->bf = EH;break;}case RH:{TempL_R = TempL->rchild;L_Rotate(CurrPTR->lchild);R_Rotate(CurrPTR);switch(TempL_R->bf){case LH:{CurrPTR->bf = RH;TempL->bf = EH;break;}case EH:{CurrPTR->bf = EH;TempL->bf = EH;break;}case RH:{CurrPTR->bf = EH;TempL->bf = LH;break;}TempL_R->bf = EH;}}}return;}void BST :: R_Balance(BSTNode *CurrPTR){BSTNode *TempR = NULL, *TempR_L = NULL;TempR = CurrPTR->rchild;switch (TempR->bf){case LH:{R_Rotate(CurrPTR);CurrPTR->bf = EH;TempR->bf = EH;break;}case RH:{TempR_L = TempR->lchild;L_Rotate(CurrPTR->lchild);R_Rotate(CurrPTR);switch(TempR_L->bf){case LH:{CurrPTR->bf = RH;TempR->bf = EH;break;}case EH:{CurrPTR->bf = EH;TempR->bf = EH;break;}case RH:{CurrPTR->bf = EH;TempR->bf = LH;break;}}TempR_L->bf = EH;}}return;}bool BST :: Insert(BSTNode *CurrPTR, int InVal){if(CurrPTR == NULL){BSTNode CURR;CurrPTR = &CURR;CurrPTR->data = InVal;taller = true;}else{if(CurrPTR->data == InVal){taller = false;cout << "BST:Insert_S:Value Existed." << endl;return 0;}else if(CurrPTR->data < InVal){if(Insert(CurrPTR->lchild,InVal) == 0){return 0;}else if(taller){switch(CurrPTR->bf){case LH:{L_Balance(CurrPTR);taller = false;break;}case EH:{CurrPTR->bf = LH;taller = true;break;}case RH:{CurrPTR->bf = EH;taller = false;break;}}}}else if(CurrPTR->data > InVal){if(Insert(CurrPTR->rchild,InVal) == 0){return 0;}else if(taller){switch(CurrPTR->bf){case LH:{CurrPTR->bf = EH;taller = false;break;}case EH:{CurrPTR->bf = RH;taller = true;break;}case RH:{R_Balance(CurrPTR);taller = false;break;}}}}}return 1;}bool BST :: Insert(int InVal){if(root == NULL){BSTNode CURR;root = &CURR;root->data = InVal;taller = true;}else{if(root->data == InVal){taller = false;cout << "BST:Insert_S:Value Existed." << endl;return 0;}else if(root->data < InVal){if(Insert(root->lchild,InVal) == 0){return 0;}else if(taller){switch(root->bf){case LH:{L_Balance(root);taller = false;break;}case EH:{root->bf = LH;taller = true;break;}case RH:{root->bf = EH;taller = false;break;}}}}else if(root->data > InVal){if(Insert(root->rchild,InVal) == 0){return 0;}else if(taller){switch(root->bf){case LH:{root->bf = EH;taller = false;break;}case EH:{root->bf = RH;taller = true;break;}case RH:{R_Balance(root);taller = false;break;}}}}}return 1;}void BST :: Search_M(){cout << "Input the value you want." << endl;int WanaVal = 0;cin >> WanaVal;bool Found = 0;Found = Search_S(root,WanaV al);return;}bool BST :: Search_S(BSTNode *CurrPTR, int WanaVal) {if(WanaVal == CurrPTR->data){return true;}else if((WanaVal < CurrPTR->data)&&(CurrPTR->lchild != NULL)){return Search_S(CurrPTR->lchild,WanaVal);}else if((WanaVal < CurrPTR->data)&&(CurrPTR->rchild != NULL)){return Search_S(CurrPTR->rchild,WanaV al);}return false;}void BST :: Display_M(){Display_S(root,0);return;}void BST :: Display_S(BSTNode *CurrPTR, int Height) {cout << "Height:" << Height << "\tData:";if(CurrPTR == NULL){cout << '#' << endl;return;}else{cout << CurrPTR->data << endl;Display_S(CurrPTR->lchild,Height+1);Display_S(CurrPTR->rchild,Height+1);}return;}void BST :: Establish(){int InVal = 0;do{cout << "Input the value you want." << endl;cin >> InVal;Insert(root,InVal);}while(InVal != -1);return;}void BST :: Delete_S_L(BSTNode *CurrPTR){BSTNode *TempR = NULL, *TempR_L = NULL;if(CurrPTR->bf == LH){CurrPTR->bf = 0;shorter = 0;}else if(CurrPTR->bf == EH){CurrPTR->bf = RH;shorter = 0;}else{TempR = CurrPTR->rchild;if(CurrPTR->bf == EH){L_Rotate(CurrPTR);TempR->bf = 1;CurrPTR->bf = -1;shorter = 0;}else if(TempR->bf == RH){L_Rotate(CurrPTR);TempR->bf = NULL;CurrPTR->bf = 0;shorter = 1;}else{TempR_L = TempR->lchild;TempR->lchild = TempR_L->rchild;TempR_L->rchild = TempR;CurrPTR->rchild = TempR_L->lchild;TempR_L->lchild = CurrPTR;if(TempR_L->bf == EH){CurrPTR->bf = EH;TempR->bf = EH;}else if(TempR_L->bf == RH){CurrPTR->bf = LH;TempR->bf = EH;}else{CurrPTR->bf = 0;TempR->bf = LH;}TempR_L->bf = EH;CurrPTR = TempR_L;shorter = true;}}return;}void BST :: Delete_S_R(BSTNode *CurrPTR){BSTNode *TempL = NULL, *TempL_R = NULL;if(CurrPTR->bf == LH){CurrPTR->bf = 0;shorter = 0;}else if(CurrPTR->bf == EH){CurrPTR->bf = RH;shorter = 0;}else{TempL = CurrPTR->rchild;if(CurrPTR->bf == EH){L_Rotate(CurrPTR);TempL->bf = 1;CurrPTR->bf = -1;shorter = 0;}else if(TempL->bf == RH){L_Rotate(CurrPTR);TempL->bf = NULL;CurrPTR->bf = 0;shorter = 1;}else{TempL_R = TempL->lchild;TempL->lchild = TempL_R->rchild;TempL_R->rchild = TempL;CurrPTR->rchild = TempL_R->lchild;TempL_R->lchild = CurrPTR;if(TempL_R->bf == EH){CurrPTR->bf = EH;TempL->bf = EH;}else if(TempL_R->bf == RH){CurrPTR->bf = LH;TempL->bf = EH;}else{CurrPTR->bf = 0;TempL->bf = LH;}TempL_R->bf = EH;CurrPTR = TempL_R;shorter = true;}}return;}void BST :: Delete_S(BSTNode *CurrPTR, BSTNode *NextPTR) {if(NextPTR->rchild == NULL){CurrPTR->data = NextPTR->data;CurrPTR = NextPTR;NextPTR = NextPTR->lchild;delete(NextPTR);shorter = 1;}else{Delete_S(CurrPTR,NextPTR->rchild);if(shorter == LH)Delete_S_R(CurrPTR);}return;}bool BST :: Delete_M(BSTNode *CurrPTR, int DelVal){bool Deleted = false;BSTNode *DelPTR;if(CurrPTR == NULL){cout << "No such node." << endl;return false;}else if(DelVal<CurrPTR->data){Deleted = Delete_M(CurrPTR->rchild,DelVal);if(shorter == 1)R_Balance(CurrPTR,shorter);return Deleted;}else{DelPTR = CurrPTR;if(CurrPTR->rchild == NULL){CurrPTR = CurrPTR->lchild;delete DelPTR;shorter = 1;}else if(CurrPTR->lchild == NULL){CurrPTR = CurrPTR->rchild;delete DelPTR;shorter = 1;}else{Delete_S(DelPTR,DelPTR->lchild,shorter);if(shorter == 1)L_Balance(CurrPTR,shorter);CurrPTR = DelPTR;}return true;}}。