目录

AVL树定义

 节点定义

购买节点

 插入节点

平衡化旋转

 左旋

右旋

改变平衡因子

单旋与双旋的判断

先左后右型：

 当为左单旋时图解：

 当为双旋时（E的balance为1时）图解：

 当为双旋时（E的balance为-1时）图解：

先右后左型：

 当为单旋时：

  当为双旋时（D的balance为-1时）图解：

   当为双旋时（D的balance为1时）图解：

AVL树定义

一颗AVL树或者是孔数，或者是具有以下性质的二叉搜索树：它的左子树和右子树都是AVL树，且左子树和右字数的高度之差的绝对值不超过1

 节点的平衡因子

•    每个节点附加一个数字，给出该节点柚子树的高度减去左子树的高度所得的高度差。这个数字即为节点的平衡因子balance
•    根据AVL树的定义，任一节点的平衡因子只能取-1,0和1
•    如果一个节点的平衡因子的绝对值大于1，则这可二叉树搜索树就失去了平衡，不再是AVL树
•    如果一颗二叉搜索树是高度平衡的，它就成为了AVL树。如果他有n个节点，其高度可保持在O(log2n)

 节点定义

typedef int KeyType;typedef struct AVLNode{struct AVLNode* leftchild;//左孩子struct AVLNode* parent;//父母struct AVLNode* rightchild;//右孩子KeyType key;//值int balance;   // 平衡因子-1 0 1;}AVLNode , *AVLTree;

购买节点

AVLNode* Buynode(KeyType kx)//购买普通节点{AVLNode* s = (AVLNode*)malloc(sizeof(AVLNode));if (nullptr == s) exit(1);memset(s, 0, sizeof(AVLNode));s->key = kx;s->balance = 0;return s;}AVLNode* MakeRoot(KeyType kx)//购买根节点{AVLNode* root = Buynode(kx);return root;}

 插入节点

bool Insert(AVLNode*& tree, KeyType kx){if (tree == nullptr){tree = MakeRoot(kx);//如果二叉树为空，则先购买一个根节点（函数单独给出）return true;}//如果二叉树不为空，则执行以下语句AVLNode* pa = nullptr;//提前定义好的空指针，用来追踪新插入的节点位置AVLNode* p = tree;//从根节点开始向下比较while (p != nullptr && p->key != kx){pa = p;p = kx key ? p->leftchild : p->rightchild;}if (p != nullptr && p->key == kx) return false;//上述循环可能是因为p->key==kx相等时推出的(即该节点已存在，无需插入)，直接退出p = Buynode(kx);//如搜寻到底，也没找到相同的节点，则正是插入该节点，此时再购买节点---改变节点的key   1p->parent = pa;//改变节点的父母   2if (kx key){pa->leftchild = p;//改变节点的左孩子  34}else{pa->rightchild = p;//改变节点的右孩子  34}PassBalance(tree, p);//改变节点的balance  5return true;}

插入节点后，再去判断每个节点的balance时候都在-1,0,1之间，若不在，则进行旋转改变

平衡化旋转

• 如果在一棵原本平衡的二叉搜索树插入了一个新节点，造成了不平衡。此时必须调整数的结构，使之平衡化
• 平衡化的旋转有两类：

1. 单旋转：左旋和右旋
2. 双旋转：左平衡和右平衡

• 每插入一个新节点时，AVL树中相关的平衡状态会发生改变。因此，在插入一个新节点后，需要从插入位置沿通向根的位置回溯，检查各节点的平衡因子（左右子树的高度差），如果在某一节点发现高度不平衡，则停止回溯。
• 从发生不平衡的节点起，沿刚才回溯的路径取直接下两层的节点
• 如果这三个节点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为左单旋转和右单旋转，其中一个是拎一个的镜像，其方向与不平衡的形状相关
• 如果这三个节点处于一条折线上，则采用双旋转进行平衡化（双旋转分为先左后右和先右后左两类）

 左旋

对处于同一直线上的三个节点，使用两个指针ptr和newroot,ptr指向发生不平衡的节点，newroot指向不平衡节点的下一层节点，然后让ptr节点指向newroot的左孩子，之后让newroot的左孩子节点指向ptr(细节问题之后会处理，这里只说大致思路)

图解：

 图解要点：左旋时，ptr的左孩子不会改变，newroot的右孩子不会改变

void RotateLeft(AVLTree& tree, AVLNode* ptr){AVLNode* newroot = ptr->rightchild;newroot->parent = ptr->parent; // 改变newroot的父母ptr->rightchild = newroot->leftchild;//改变ptr的右孩子if (newroot->leftchild != nullptr){newroot->leftchild->parent = ptr;  // 2 改变newroot左孩子的父母}newroot->leftchild = ptr;//改变newroot的左孩子    //你可能会问，这一步和第二步不是一样的吗？    //我们在定义一个AVL数节点时，对于节点的左孩子，右孩子，还有父母都是单独定义的，所以对于一个旋转之后的节点来说，它的这三者都可能会改变，所以必须重新赋值if (ptr == tree){tree = newroot;//如果ptr是根节点，那么旋转之后，newroot就是根节点}else//判断ptr是ptr父母的左孩子还是右孩子，根据此结果改变ptr父母的孩子节点{if (ptr->parent->leftchild == ptr){ptr->parent->leftchild = newroot;}else{ptr->parent->rightchild = newroot;}}ptr->parent = newroot; //改变ptr的父母}

右旋

右旋与左旋刚好相反

void RotateRight(AVLTree& tree, AVLNode* ptr){AVLNode* newroot = ptr->leftchild;newroot->parent = ptr->parent; //1ptr->leftchild = newroot->rightchild;if (newroot->rightchild != nullptr){newroot->rightchild->parent = ptr;}newroot->rightchild = ptr;if (ptr == tree){tree = newroot;}else{if (ptr->parent->leftchild == ptr){ptr->parent->leftchild = newroot;}else{ptr->parent->rightchild = newroot;}}ptr->parent = newroot;}

总结：所有的节点都有五个部分，即：leftchild,rightchild,parent,key,balance,在旋转时，涉及到的节点，不论哪个部分发生改变，都需要重新赋值，都需要重新赋值，都需要重新赋值......（这里的左旋和右旋只改变前三个部分，其它两部分会在其它模块改变）

改变平衡因子

从新节点的插入位置p开始向上回溯，用pa指向p的父母节点，在回溯的过程中，我们首先要判断此时的p是pa的左孩子还是右孩子，如果是左孩子，那么说明pa的左子树高度比右子树高度又高一层，此时的pa->palance应该减1，但是如果本身就为-1，那么减1之后必然导致不平衡，此时我们应该去旋转子树；如果是右孩子，那么说明pa的右子树高度比左子树高度又高一层，此时的pa->palance应该加1，但是如果本身就为1，那么减1之后必然导致不平衡，此时我们也应该去旋转子树。

代码如下：

void PassBalance(AVLTree& tree, AVLNode* p){AVLNode* pa = p->parent;bool tall = true;for (; pa != nullptr && tall;){if (pa->leftchild == p){switch (pa->balance){case 0: pa->balance = -1; break;case 1: pa->balance = 0; tall = false;break;case -1:LeftBalance(tree, pa);tall = false;break;}}else  // p -->pa->rightchild{switch (pa->balance){case 0: pa->balance = 1; break;case -1: pa->balance = 0; tall = false;break;case 1:RightBalance(tree, pa);tall = false;break;}}p = pa;pa = p->parent;}}

单旋与双旋的判断

在进行子树的旋转时，需要先判断不平衡节点以及下两层组成的三节点是否是一条直线，如果是一条直线，则只进行左单旋或右单旋，如果是一条折线，则需要双旋，即：先左后右或先右后左

先左后右型：

图解：

 当为左单旋时图解：

 当为双旋时（E的balance为1时）图解：

 当为双旋时（E的balance为-1时）图解：

 代码如下：

void LeftBalance(AVLTree& tree, AVLNode* ptr){AVLNode* leftsub = ptr->leftchild, * rightsub = nullptr;switch (leftsub->balance){case 0: cout << "left balance " <balance = 0;leftsub->balance = 0;RotateRight(tree, ptr);break;case 1:rightsub = leftsub->rightchild;switch (rightsub->balance){case -1:leftsub->balance = 0;ptr->balance = 1;break;case 1:leftsub->balance = -1;ptr->balance = 0;break;case 0:  leftsub->balance = 0;ptr->balance = 0;break;}rightsub->balance = 0;RotateLeft(tree, leftsub);RotateRight(tree, ptr);break;}}

先右后左型：

 当为单旋时：

  当为双旋时（D的balance为-1时）图解：

   当为双旋时（D的balance为1时）图解：

 代码如下：

void RightBalance(AVLTree& tree, AVLNode* ptr){AVLNode* rightsub = ptr->rightchild, * leftsub = nullptr;switch (rightsub->balance){case 0: cout << "left balance " <balance = 0;rightsub->balance = 0;RotateLeft(tree, ptr);break;case -1:leftsub = rightsub->leftchild;switch (leftsub->balance){case -1:rightsub->balance = 1;ptr->balance = 0;break;case 1:rightsub->balance = 0;ptr->balance = -1;break;case 0:rightsub->balance = 0;ptr->balance = 0;break;}leftsub->balance = 0;RotateRight(tree, rightsub);RotateLeft(tree, ptr);break;}}

创作打卡挑战赛 赢取流量/现金/CSDN周边激励大奖