没事儿就学习（1）：AVL树插入

本文主要是介绍没事儿就学习（1）：AVL树插入，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

AVL树是最先发明的自平衡二叉树，这是个啥树呢，为啥要平衡呢？我们可以在分析其原理的时候慢慢用C++实现它一下。

故名思意，自平衡二叉树是一种可以实现自我平衡的二叉树，分开看是自动化的、平衡的、二叉树。数据结构中的二叉树是一种特殊的树，因为其限定了树中的每个节点最多只能包含两个子节点，那么根据其特性就不难发现在二叉树的第n层，就最多仅有2^(n-1)个子节点。二叉树可以沿任意一侧不断延伸到任意的深度，导致了二叉树可以具有各种各样的形状，比如下面画的巨丑的一张图，左边是一棵满二叉树，而右边则是一棵普通二叉树。

规整的二叉树和不规整的二叉树差别在什么地方呢？从直观上来说，一棵树越趋向于满二叉树，那么它的通过递归查找的次数可能越少，效率就越高，因此趋向于将数据向满二叉树排列。那么一个简单的排序树是什么样的呢？我们先随便说一串数字，比如{1，2，4，8，5，7，3，9，6}，在构建树的时候，先把第一个元素作为根节点，然后后续插入时将比节点中数值大的作为其右子节点，否则为左子节点，具体的流程可以从下图的步骤中看出。

按顺序构建的二叉树长的和北斗七星一样，9个数值构建出的深度竟然达到了7层之多，如果按满二叉树的方式构建，最多只需要4层就足够进行摆放。那么有没有什么方法可以将狂野生长的二叉树变成比较规矩的，每一层都有足够节点的二叉树呢？平衡的概念就此提出。我们很明显的看出上图中最后生成的树一点都不平衡，根节点左侧啥也没有，右侧延伸出一个北斗七星，只有在左右两侧节点深度和数量差不多的情况下树才能平衡啊，不然就是一边倒了，所以我们要给出一些限定条件来转换节点之间的位置和顺序。

平衡有相对的平衡和绝对的平衡，自然界中没有绝对的平衡存在，所有的平衡都有一定的缓冲范围，也就是所谓的阈值，超过这个阈值的限定即为不平衡，需要通过一定的手段对环境进行再平衡。这个阈值在自平衡二叉树中体现在每个结点的左子树和右子树的深度相差不能大于1，否则即为不平衡的状态，否则需要通过一系列的手段，左旋和右旋将树转换到稳定态。我们先拿一个最简单的例子{1，2，3}进行一下平衡性实验，如下图所示，首先生成的树如上方所示，1作为根节点，2是1的右子节点，3是2的右子节点，那么根节点1的左子树深度为0，右子树深度为2，相差2>1已经处于不平衡的状态。那么怎么样可以使其变成平衡态呢？很明显，将2作为根节点可以有效解决这一问题。那么怎么将2作为根节点呢？我们可以把这三个节点向左旋转，1作为2的左子节点，3作为2的右子节点，旋转完毕后根节点2左子树深度为1，右子树深度为1，实现了平衡。这样的操作我们就称之为左旋。同样的如果是左侧子树的深度大于右侧子树的深度，就需要对其进行右旋。

所以我们可以先定义一下二叉树节点的数据结构，每个节点可以存储一个值，存储左孩子和右孩子，存储当前平衡的状态，因此定义如下。

//枚举：平衡状态
enum HeightType
{LEFTHEIGHT,//左深RIGHTHEIGHT,//右深EQUALHEIGHT//平衡
};class TreeNode {
public:int value;//存储值TreeNode *leftChild;//左枝TreeNode *rightChild;//右枝HeightType heightType;//平衡状态//构造函数TreeNode(int value) {this->value = value;this->leftChild = nullptr;this->rightChild = nullptr;this->heightType = EQUALHEIGHT;};
};

然后定义一下左旋操作，1的左孩子连向2的右孩子，2的左孩子连向1，再把2作为根节点，于是乎函数可以这样写。

bool TurnLeft(TreeNode* &node) {TreeNode* tempNode = node->rightChild;node->rightChild = tempNode->leftChild;tempNode->leftChild = node;node = tempNode;return true;
}

然后再定义一下右旋操作，与左旋类似。

bool TurnRight(TreeNode* &node) {TreeNode* tempNode = node->leftChild;node->leftChild = tempNode->rightChild;tempNode->rightChild = node;node = tempNode;return true;
}

但是仅仅这样旋转就结束了吗，很显然不是的，当不平衡发生的时候根节点和其子节点的平衡性符号相反时，1的平衡性符号为RH，3的平衡性符号为LH，如果仅仅进行左旋操作的话，得到的结果为：3为根节点，1为3的左孩子，2为3的右孩子，很明显与要求不符。因此需要先将3和2先调换位置，将2作为1的右孩子，3作为2的右孩子，使1和2的平衡性因子均为RH，然后再进行左旋操作。那么我们可以将左旋和右旋操作的函数写的更加完善一点。

bool BigTurnLeft(TreeNode* &node) {TreeNode *nextNode = node->rightChild;//转换节点位置if (node->heightType != nextNode->heightType) {node->rightChild = nextNode->leftChild;node->rightChild->rightChild = nextNode;nextNode->leftChild = nullptr;}//左旋TurnLeft(node);return true;
}bool BigTurnRight(TreeNode* &node) {TreeNode *nextNode = node->rightChild;//转换节点位置if (node->heightType != nextNode->heightType) {node->leftChild = nextNode->rightChild;node->leftChild->leftChild = nextNode;nextNode->rightChild = nullptr;}//右旋TurnRight(node);return true;
}

在定义完毕基本的左旋和右旋操作后，我们就可以写AVL树的插入函数了，不如我们先小看一下代码？（没错，你没的选，我就是想让你看）

bool InsertIntoATLTree(TreeNode* &node, int value, bool &isGrow) {//如果没有根节点，则创造一个根节点if (node == nullptr) {node = new TreeNode(value);}else {if (value == node->value) { //判断值是否相同，相同则无需插入return false;}if (value < node->value) { //若value值小于当前节点值if (node->leftChild == nullptr) {  //左枝是否为空?将value作为该节点的左节点:递归向下判断TreeNode *newNode = new TreeNode(value);//新建node，连在当前node左枝node->leftChild = newNode;switch (node->heightType)//修改当前节点稳定性{case RIGHTHEIGHT:node->heightType = EQUALHEIGHT;break;case EQUALHEIGHT:node->heightType = LEFTHEIGHT;isGrow = true;break;default:break;}return true;}else {if (InsertIntoATLTree(node->leftChild, value, isGrow)) {if (isGrow) {switch (node->heightType){case LEFTHEIGHT:BigTurnRight(node);node->heightType = EQUALHEIGHT;node->rightChild->heightType = EQUALHEIGHT;isGrow = false;break;case RIGHTHEIGHT:node->heightType = EQUALHEIGHT;break;case EQUALHEIGHT:node->heightType = LEFTHEIGHT;break;default:break;}}}else {return false;}}}else {if (node->rightChild == nullptr) {  //右枝是否为空?将value作为该节点的右节点:递归向下判断TreeNode *newNode = new TreeNode(value);//新建node，连在当前node右枝node->rightChild = newNode;switch (node->heightType)//修改当前节点稳定性{case LEFTHEIGHT:node->heightType = EQUALHEIGHT;break;case EQUALHEIGHT:node->heightType = RIGHTHEIGHT;isGrow = true;break;default:break;}return true;}else {if (InsertIntoATLTree(node->rightChild, value, isGrow)) {if (isGrow) {switch (node->heightType){case LEFTHEIGHT:node->heightType = EQUALHEIGHT;break;case RIGHTHEIGHT:BigTurnLeft(node);node->heightType = EQUALHEIGHT;node->leftChild->heightType = EQUALHEIGHT;isGrow = false;break;case EQUALHEIGHT:node->heightType = RIGHTHEIGHT;break;default:break;}}}else{return false;}}}}return true;
}

树的插入算法是一个递归的过程，首先将需要插入的数值V 与根节点RN 中的数值RV 进行对比，若V<RV 则与其左孩子进行对比，若V>RV则于其右孩子进行对比，直至某个节点没有左孩子或右孩子为止。构建新节点作为新的叶子，判断该叶子的父节点平衡状态，若父节点的平衡状态与叶子节点的悬挂方向相反则表示树没有生长，否则树发生生长，回溯是判断各个父节点的平衡状态，若父节点处于不平衡状态则进行左旋或右旋操作，旋转完毕后再往前回溯的节点不再改变平衡状态。

以一个小例子作为插入的结束C={23， 16， 47， 53， 62， 11， 17， 8 ， 3}；