文章目录前言平衡二叉搜索树(AVL树) AVL树的节点数据结构在原始数据上建立AVL树调整和平衡树节点的操作：旋转LL )右转) hxsdbg左侧实现数据编码) RR )右子叶右侧实现数据编码(LR )左右旋转)
前言
我之前种过AVL树，为什么还要写呢？ 还忘了，要再刷一次哦。
平衡二叉树(AVL树)二叉树可以在一定程度上提高搜索效率，但原序列有序，如序列a={ 1，2，3，4，5，6 }，则生成二叉树。 基于该序列构建的二叉树为右斜树，同时二叉树退化为单链表，搜索效率降低为o(n )。
下图：
要在此双叉搜索树中搜索元素6，必须搜索6次。 由于二叉搜索树的搜索效率取决于树的高度，保持树的高度最小可以保证树的搜索效率。 通过如下图所示存储相同的数组a，在查找要素6时只需进行三次比较，检索效率就会变为2倍。
可以看出，当节点数一定且树的左右两端保持平衡时，树的搜索效率最高。 这左右的部分树的高度在1以下的树是平衡的二叉树。
AVL树的节点数据结构与上面使用的一般结构略有不同。
class TreeNode{public://这些数据要公开，以便于操作int depth； //深度，在此可以计算各节点的深度，根据深度的比较求出TreeNode* parent是否平衡//该节点的父节点，便于操作int val的TreeNode* left； TreeNode* right； treenode(intx ) :val ) x、depth(0)、left (null )、right ) {} TreeNode ) ) 3360val )0)、depth )0)。 尝试在原始数据中创建AVL树的我的代码：
(首先对原始数据进行排序，然后输入双叉搜索树，使用递归方法。 ）
# include iostream # includevectorusingnamespacestd； 如果只剩下一个voidcreatetree(vectorintvec，TreeNode* root，int begin，int end ) /密钥if (begin==end ) root-val=vec [ (intmid_SZ=) Beginend )/2； root-val=vec[mid_sz]； mid _ SZ-1=begin ) root-left=newtreenode(0)； createtree(vec，root-left，begin，mid_sz - 1 )； }root-right=newtreenode(0； createtree(vec，root-right，mid_sz 1，end )； } voidpreordertraverse (treenode * root ) if ) null==root ) return； cout root-val； preorder traverse (根左)； preorder traverse (根权限； }int main () treenode*roott=newtreenode ) 0； vectorint vec={ 0，1，2，3，4，5，6，7 }； 创建树(vec，roott，0，vec.size ) (-1 )； preordertraverse(roott； }调整和平衡树节点的操作：在旋转LL (右转) hxsdbg的左侧插入数据图解流程：
在代码实现hxsdbg的左侧插入数据treenode*ll(treenode*root ) ({ TreeNode* x=root-left； //返回节点是y的左子节点(其b ) TreeNode* temp=x-right； //首先取出y右边的子节点(是那个e ) x-right=root； 将//Y放入x的右子节点中(将a放入b的右子节点中)； //将之前存放的东西作为y的左子节点(e为a的右节点)返回x； //(返回那个b ) }int main ) ) treenode*roott=newtreenode(0)； vectorintvec={ 0，1，2 }
,3,4,5,6,7}; createTree(vec,roott,0,vec.size()-1); roott = LL(roott); PreOrderTraverse(roott);} RR（左旋）：在右子叶的右侧插入数据图解过程：
右旋其实就是上面左旋的镜像过程，所以不难，直接仿写上面左旋的过程即可：
代码实现 TreeNode* RR(TreeNode* root) { TreeNode* x = root->right;//即将返回的节点是y的右子节点 TreeNode* temp = x->left;//先把x的左子节点取出来 x->left = root;//把y放进x的左子节点 root->right = temp;//把前面预存的放到y的右子节点 return x;}int main() { TreeNode* roott = new TreeNode(0); vector<int> vec = { 0,1,2,3,4,5,6,7}; createTree(vec,roott,0,vec.size()-1); roott = RR(roott); PreOrderTraverse(roott);}后面的部分，就比较抽象了。
LR（左右旋）：在hxsdbg节点的右侧插入数据我们将这种情况抽象出来，得到下图：
我们需要对节点y进行平衡的维护。步骤如下图所示（第三个图里面x和z的位置换一下。）：
我们将这种情况抽象出来，得到下图：
我们需要对节点y进行平衡的维护。步骤如下图所示（第三个图里面x和z的位置换一下。）：
第二个图中y的左孩子为T1
（被水印遮住的部分为：T1，T2，T3，T4）
在这里需要先补两个函数，虽然可能现在看不懂，但是配上调用函数的上下文就懂了。
计算平衡因子 int getBalanceFactor(TreeNode* node){if(node==NULL){return 0;}return get_depth(node->left)-getHeight(node->right);} int get_depth(TreeNode* node){if(node==NULL){return 0;}return node->depth;}对getBalanceFactor函数返回值的分析：
如果刚插入的叶子节点的爷爷节点的返回值大于0
如果刚插入的叶子节点的父节点的返回值大于0：(LL)如果刚插入的叶子节点的父节点的返回值小于0：(LR)如果刚插入的叶子节点的爷爷节点的返回值小于0
如果刚插入的叶子节点的父节点的返回值大于0：(RL)如果刚插入的叶子节点的父节点的返回值小于0：(RR) 完整代码（测试过）更新有点慢了，这两天事情太多，加上要调整两地状态。
#include<iostream>#include<vector>using namespace std;class TreeNode {public://这几个数据放做公有的，方便操作int depth; //深度，这里计算每个结点的深度，通过深度的比较可得出是否平衡int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), depth(0), left(NULL), right(NULL) {}TreeNode() : val(0), depth(0), left(NULL), right(NULL) {}int getnode() {return this->val;}TreeNode* getleft() {return this->left;}TreeNode* getright() {return this->right;}void setleft(TreeNode* node) {this->left = node;}void setright(TreeNode* node) {this->right = node;}};void preorder(TreeNode* head) {if (head == NULL) {return;}cout << head->getnode() << endl;preorder(head->getleft());preorder(head->getright());}class AVL_Tree {public:AVL_Tree() {}TreeNode* right_rotate(TreeNode* root) {TreeNode* temp = root->left;root->left = temp->right;temp->right = root;return temp;}TreeNode* left_rotate(TreeNode* root) {TreeNode* temp = root->right;root->right = temp->left;temp->left = root;return temp;}TreeNode* right_left_rotate(TreeNode* root) {root->right = right_rotate(root->right);return left_rotate(root);}TreeNode* left_right_rotate(TreeNode* root) {root->left = left_rotate(root->left);return right_rotate(root);}int get_depth(TreeNode* node) {if (!node) {return 0;}int maxL = 0;int maxR = 0;//2.计算左子树的最大深度； if (node->left != NULL)maxL = get_depth(node->left);//3.计算右子树的最大深度； if (node->right != NULL)maxR = get_depth(node->right);//4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1 return maxL > maxR ? maxL + 1 : maxR + 1; }int getbalance(TreeNode* node) {return get_depth(node->left) - get_depth(node->right);}//先假设这个二叉树足够高TreeNode* insert_node(TreeNode* head,int val) {//插入一个节点，不管三七二十一先插到叶子节点再说if (head != NULL) {if (val < head->val) {head->left = insert_node(head->left, val);}else {head->left = insert_node(head->right, val);}}else {//这里不放else等着失败head = new TreeNode(val);}//插入之后就该旋转了if (getbalance(head) == 2) {//如果需要旋转（左边高）if (getbalance(head->left) == 1) {//左左，需要右右旋转return right_rotate(head);//这里还需要向上衔接}else if (getbalance(head->left) == -1) {//左右，这里需要右左旋转return right_left_rotate(head);}}else if (getbalance(head) == -2) {//如果需要旋转（右边高）if (getbalance(head->right) == -1) {//右右，需要左左旋转return left_rotate(head);//这里还需要向上衔接}else if (getbalance(head->right) == -1){//左右，这里需要右左旋转return left_right_rotate(head);}}return head;}TreeNode* delete_node(TreeNode* head,int val) {if (head!=NULL) {if (val < head->val) {head->left = delete_node(head->left, val);}else if(val > head->val){head->left = delete_node(head->right, val);}else {TreeNode* temp = head->left;while (temp && temp->right) {temp = temp->right;}head->val = temp->val;if (temp->left) {//如果最右子节点还有左子节点//那顶多就一个节点temp->val = temp->left->val;//temp->left = temp->left->left;//temp->right = temp->left->right;temp->left->val = NULL;delete temp->left;}else {temp->val = NULL;delete temp;}return NULL;}}if (getbalance(head) == 2) {//如果需要旋转（左边高）if (getbalance(head->left) == 1) {//左左，需要右右旋转return right_rotate(head);//这里还需要向上衔接}else if (getbalance(head->left) == -1) {//左右，这里需要右左旋转return right_left_rotate(head);}}else if (getbalance(head) == -2) {//如果需要旋转（右边高）if (getbalance(head->right) == -1) {//右右，需要左左旋转return left_rotate(head);//这里还需要向上衔接}else if (getbalance(head->right) == -1) {//左右，这里需要右左旋转return left_right_rotate(head);}}return head;}};int main() {//TreeNode* a0 = new TreeNode(0);TreeNode* a1 = new TreeNode(1);//TreeNode* a2 = new TreeNode(2);TreeNode* a3 = new TreeNode(3);//TreeNode* a4 = new TreeNode(4);TreeNode* a5 = new TreeNode(5);TreeNode* a6 = new TreeNode(6);TreeNode* a7 = new TreeNode(7);//TreeNode* a8 = new TreeNode(8);TreeNode* a9 = new TreeNode(9);//TreeNode* a10 = new TreeNode(10);a5->setleft(a3);a5->setright(a7);a3->setleft(a1);//a3->setright(a4);a7->setleft(a6);a7->setright(a9);AVL_Tree* avl = new AVL_Tree();a5 = avl->insert_node(a5,2);//左左插入preorder(a5);//cout << avl->get_depth(a5) << endl;}