企业官网建设流程全解析

1.AVL树的由来：

假设此时有一个二叉搜索树：我们要进行删除操作

二叉搜索树，经过多次的插入或删除操作的影响，二叉搜索树可能会退化为链表形式。

时间复杂度由O（logN）逐渐退化为O（N）

由于这种退化现象，我们就引出了AVL树。

2.AVL树的概念：

AVL树主要解决的就是二叉搜索树在多次添加或者删除节点之后，保证其树的结构不会发生退化，从而使其操作函数的时间复杂度依旧保持O（logN）

AVL树既是二叉搜索树，也是平衡二叉树，所以AVL树一般叫平衡二叉搜索树。

整体代码实现之前我们的头文件

#pragma once typedef int ELEMTYPE; //AVL树有效节点的结构体设计 typedef struct AVLNode { ELEMTYPE data;//数据域 struct AVLNode* leftchild;//左孩子指针 struct AVLNode* rightchild;//右孩子指针 //struct AVLNode* parent;//双亲指针 //int balance;//平衡因子 int height;//节点的高度 }AVLNode,*PAVLNode; //AVL树辅助节点结构体设计 typedef struct AVLTree { struct AVLNode* root;//根节点指针 //int cursize;//当前节点的个数 }AVLTree; //要实现的函数 //工具函数 ： // 1.购买新节点 AVLNode* BuyBNode(); // 2.获取当前节点的高度 int Get_Height(AVLNode*node); // 3.更新当前节点的高度 void Update_Height(AVLNode* node); // 4.获取当前节点的平衡因子 int Get_BalanceFactor(AVLNode* node); // 5.左旋 AVLNode* Left_Rotate(AVLNode* node); // 6.右旋 AVLNode* Right_Rotate(AVLNode* node); // 7.通用的平衡旋转调整函数 AVLNode* Rotate(AVLNode* node); //普通操作函数： // 1.初始化 void Init_AVLTree(AVLTree* pTree); // 2.插入 bool Insert(AVLTree* pTree, ELEMTYPE val); //2.5 帮助函数 （帮助我们递归形式的去实现插入 AVLNode* Insert_Helper(AVLNode* node, ELEMTYPE val); // 3.删除 // 4.查找（和BST树的查找一样） AVLNode* Search_AVLTree(AVLTree* pTree, ELEMTYPE val); // 5.打印 void Show_InOder(AVLTree* root); // 6.判空 bool IsEmpty(AVLTree* pTree); // 7.销毁 AVLNode* Destroy(AVLNode* root);

所需要的工具函数：

购买新节点

// 1.购买新节点 AVLNode* BuyBNode() { AVLNode* pnewnode = (AVLNode*)malloc(sizeof(AVLNode)); if (pnewnode == NULL) { exit(EXIT_FAILURE); } pnewnode->leftchild = NULL; pnewnode->rightchild = NULL; pnewnode->height = 0; return pnewnode; }

获取当前节点的高度

// 2.获取当前节点的高度 int Get_Height(AVLNode* node) { //assert(node!=NULL)是错的 node 接收的NULL是合法参数 if (node == NULL) { return -1; } return node->height; }

更新当前节点高度

// 3.更新当前节点的高度 // (高度的定义就是当前节点到他最远的叶子节点的总的节点个数 // 包含他自己的节点 void Update_Height(AVLNode* node) { int height_left = Get_Height(node->leftchild); int height_right = Get_Height(node->rightchild); node->height = height_left > height_right ? height_left + 1 : height_right + 1; }

获取当前节点的平衡因子

// 4.获取当前节点的平衡因子 int Get_BalanceFactor(AVLNode* node) { //node==NULL 是一个合法参数 if (node != NULL) { return 0; } return Get_Height(node->leftchild) - Get_Height(node->rightchild); }

3.AVL树的平衡旋转

（1） AVL树怎么保证其不退化？

AVL树定义了平衡的概念：

平衡指的是，任何一个节点的左右子树的高度差绝对值要小于等于1 可以让树保持均衡的状态，不会出现一边倒的情况

平衡因子：左子树-右子树的高度（平衡因子的的取值 -1 0 1）

（2）如果平衡因子不是-1，0，1这三个值，则说明其失衡的了，需要介入进行平衡旋转操作，让其再次保持平衡。

（3）平衡旋转

旋转结果分为四种：

单右旋

简单情况：

复杂情况

解决方案：冲突的右孩变左孩

// 6.右旋 AVLNode* Right_Rotate(AVLNode* node) { //0.aseert assert(node != NULL); //1.在申请一两个指针child 和 grandchild //分别指向失衡节点的左孩子及其右孩子（注意：左孩子的右孩子可能不存在 AVLNode* child = node->leftchild; AVLNode* grandchild = child->rightchild;//此时grandchild有可能是空 //2.修改2个指针域 (先处理有可能冲突的那个孙子节点 node->leftchild = grandchild; child->rightchild = node; //2.5修正一下各个节点的高度信息 Update_Height(node); Update_Height(child); //3.返回平衡后的根节点 return child; }

单左旋：

简单情况

复杂情况：

口诀：冲突的左孩子变右孩

AVLNode* Left_Rotate(AVLNode* node) { assert(node != NULL); AVLNode* child = node->rightchild; AVLNode* grandchild = child->leftchild;//注意grandchild可能是NULL node->rightchild = grandchild; child->leftchild = node; Update_Height(node); Update_Height(child); return child; }

双旋-先左再右

先左旋再右旋

先左旋是对失衡节点的孩子说的

再右旋是对失衡节点说的

先右在左：

口诀：先右旋再左旋

先右旋，是对失衡节点的孩子节点说的

再左旋，是对失衡节点说的

怎么判定当前节点需要那种平衡旋转方式？

1.将失衡的情况，分成了四种形态：每一种对应不同的处理策略

失衡节点的平衡因子=2

失衡节点的平衡因子=-2

通用的平衡旋转函数：

/ 7.通用的平衡旋转调整函数 *** //这个函数需要根据传递进来的Node节点信息 //判断属于XX型 然后调用对应的旋转函数； AVLNode* Rotate(AVLNode* node) { //0.assert assert(node != NULL); //1.根据当前Node节点的平衡因子 是2还是-2来确定第一个字母（XX型号） int bf = Get_BalanceFactor(node); if (bf == 2) {//L就确定了 int bf_L = Get_BalanceFactor(node->leftchild); if (bf_L>=0) { //单右旋 return Right_Rotate(node); } else {//LR //先左旋再右旋 node->leftchild = Left_Rotate(node->leftchild); return Right_Rotate(node); } } if (bf == -2) {//R就确定了 int bf_R = Get_BalanceFactor(node->rightchild); if (bf_R == -1||bf_R==0) {//RR //单左旋 return Left_Rotate(node); } else {//RL //先右旋再左旋 node->rightchild = Right_Rotate(node->rightchild); return Left_Rotate(node); } } //2.确定第一个字母之后，在确定第二个 //3.直接调用对应的旋转策略即可 }

普通函数操作：
初始化：

void Init_AVLTree(AVLTree* pTree) { assert(pTree != NULL); pTree->root = NULL; }

4.AVL树的插入

我们只需注意3个节点：

单右旋：

（1）失衡节点自身

（2）它的左孩子

（3）它的左孩子的右孩子

// 2.插入 bool Insert(AVLTree* pTree, ELEMTYPE val) { pTree->root=Insert_Helper(pTree->root, val); return true; } //2.5 帮助函数 （帮助我们递归形式的去实现插入 AVLNode* Insert_Helper(AVLNode* node, ELEMTYPE val) { //0.assert //1.对传入的Node进行判断 // Node节点有可能是空地址 这时只需要购买新节点 返回出去 if (node == NULL) { AVLNode* pnewnode = BuyBNode(); pnewnode->data = val; return pnewnode; } //2.如果Node节点不是NULL 则判断Node其值是否等于val //3.如果Node->val==val 则不用插入 if (node->data == val) { return node; } //4.如果Node->val!=val 通过val值和Node—>val 进行比较 //来决定在Node的左子树还是在右子树里面。 if (val < node->data) { node->leftchild = Insert_Helper(node->leftchild, val); } else { node->rightchild = Insert_Helper(node->rightchild, val); } //5.修正各个节点的高度（注意：此时只需要修正Node的节点高度 Update_Height(node); //6.插入有可能会导致失衡，所以我们把Node节点扔到我们的通用旋转函数里面 return Rotate(node); }

5.AVL树的删除

首先AVL也是二叉搜索树，所以在AVL树上进行删除操作，和BST树的基本逻辑是一样的，也就是说首先判断val值是否存在，如果存在，则判断其所在的有效节点是0分支 /1分支 /2分支

单右旋失衡节点，再将其孩子节点的右孩子被这个失衡节点接收为左孩子

冲突的左孩变右孩

删除有效值5：待删除值5存在，且存在于0分支节点（没有孩子），则可以直接进行删除，然后判定是否失衡，7失衡了，判定7失衡节点的平衡因子为-2， 且其右孩子的平衡因子是1，则判定是RL型需要双旋调整（先右在左）

第二个删除有效值18：

删除有效值14：

删除有效值11：

插入导致的失衡，只需平衡一次

删除导致的失衡，可能需要平衡多次

总结：

1.先按照BST大 的删除逻辑，先确保待删除值val存在

2.再判定这个待删除节点是0分支/1分支/2分支

3.如果是0/1则简单，如果是2分支，则用直接前驱或者直接后继去替代待删除节点，转而去删除其直接前驱或者直接后继

4.删除完成之后，需要回溯去判断是否造成失衡，如果出现失衡节点，则判断属于LL/LR/RL/RR哪种型号，然后调用对应的旋转即可

5.特别注意：插入造成的失衡只需要调整一次，删除操作造成的失衡可能需要调整多次

// 3.删除 bool Delete(AVLTree* pTree, ELEMTYPE val) { pTree->root=Delete_Helper(pTree->root, val); return true; } //3.5删除帮助函数（帮我们递归去实现删除 AVLNode* Delete_Helper(AVLNode* node, ELEMTYPE val) { if (node == NULL) { return NULL; } //此时Node不为空 if (val<node->data) { node->leftchild=Delete_Helper(node->leftchild, val); } else if (val > node->data) { node->rightchild = Delete_Helper(node->rightchild, val); } else { if (node->leftchild != NULL && node->rightchild != NULL) { AVLNode* cat = node->rightchild; while (cat->leftchild != NULL) { cat = cat->leftchild; } node->data = cat->data; //node = cat; node->rightchild = Delete_Helper(node->rightchild, cat->data); } //此时Node一定指向要删除的节点 //如果是0分支 if (node->leftchild == NULL && node->rightchild == NULL) { free(node); node = NULL; } //此时只剩下一分支 else{ AVLNode* child = node->leftchild != NULL ? node->leftchild : node->rightchild; free(node); return child; } //更新当前节点Node节点的高度信息 Update_Height(node); //调用通用旋转函数，对Node节点进行处理，如果Node没有失衡，则自动退出，如果失衡了，则调整好退出 return Rotate(node); } }

6..AVL树的查找

// 4.查找（和BST树的查找一样） AVLNode* Search_AVLTree(AVLTree* pTree, ELEMTYPE val) { assert(pTree != NULL); AVLNode* p = pTree->root; while (p!=NULL&&p->data !=val) { p = val<p->data?p->leftchild:p->rightchild; } return p; }

7.AVL的打印

// 5.打印 void Show_InOder(AVLNode* root) { if (root == NULL) { return; } Show_InOder(root->leftchild); printf("%d ", root->data); Show_InOder(root->rightchild); }

8.判空

// 6.判空 bool IsEmpty(AVLTree* pTree) { return pTree->root == NULL; }

9.销毁

// 7.销毁 AVLNode* Destroy(AVLNode* root) { if (root == NULL) { return; } root->leftchild=Destroy(root->leftchild); root->rightchild=Destroy(root->rightchild); free(root); root = NULL; return NULL; }

AVL树和BST树的比较：

AVL树的查找和打印和BST树的查找和打印是一模一样的

但是，AVL树的插入和删除操作，相较于BST树，基本逻辑框架是一样的，唯独多了一点，就是在插入会和删除操作完成之后，需要判断一下树是否发生失衡，没有失衡则不用调整，失衡了就调整一下即可