AVL 树：图解左右旋单双旋（内附代码）
前⾔
上⼀篇博客讲完了，⼆叉搜索树在分配单元上有⼀些挺好的做法，⾮极端情况下查找的时间复杂度为，但是请看下⾯这种情况，如果我们要查找数字6，时间复杂度会退化为，跟普通链表没什么差别了。所以我们需要⼀种⽅式来平衡⼀下这棵树，使得我们可以⼀
直保持着⽐较快的搜索时间。
重要概念
那么我们应该在什么时候平衡呢？在每⼀次插⼊新节点时进⾏平衡，平衡的操作包括左单旋，右单旋，左双旋，右双旋。听起来⼗分复杂，但其实并没有，我们可以通过画图使得这个步骤变简单。
思考逻辑
我初学的时候直接理解的代码，⾮常难受，后来⽼师上课的时候⼿绘了⼀次旋转的全过程，于是我印象深刻。我理解了以下两个图的变换从⽽写的代码。
导游资格证怎么考单旋转
O (logn )O (n )
把降级为的孩⼦，然后把的Y树分配给实现平衡，这⾥要注意XYZ代表⼦树，这些⼦树可以是空的，只要满⾜了的左右⼦树的⾼
度相差为2，不影响这个转换的过程。
BSTree * RtSgRotation (BSTree * root ) //右单旋（right single rotation ）
{
BSTree * temp ;
temp = root ->lchild ;尚渔味
root ->lchild = temp ->rchild ;
temp ->rchild = root ;
root ->height = getMax (getHeight (root ->lchild ), getHeight (root ->rchild ))+1;
temp ->height = getMax (getHeight (temp ->lchild ), root ->height )+1;
return temp ;
}
BSTree * LtSgRotation (BSTree * root ) //左单旋（left single rotation ）
{
BSTree * temp ;
temp = root ->rchild ;
root ->rchild = temp ->lchild ;
temp ->lchild = root ;
root ->height = getMax (getHeight (root ->lchild ), getHeight (root ->rchild ))+1;
temp ->height = getMax (getHeight (temp ->rchild ), root ->height )+1;
什么食物化痰
return temp ;
}
双旋转
k 1k 2k 2k 1k 1
双旋转可以理解为两次单旋转的结合，把
拆开看是精髓所在，其他同上的单旋转！图如下：BSTree * RtDbRotation (BSTree * root ) //右双旋（right double rotation ）= 左单旋+右单旋
{
root ->lchild = LtSgRotation (root ->lchild );
return RtSgRotation (root );
}
BSTree * LtDbRotation (BSTree * root ) //左双旋（left double rotation ）= 右单旋+左单旋
{
华东计算技术研究所root ->rchild = RtSgRotation (root ->rchild );
return LtSgRotation (root );
}
全部代码
#include <stdio.h>
#include <stdlib.h>
typedef struct BST
{
int data ;
int height ;
struct BST * lchild ;
struct BST * rchild ;
}BSTree ;
BSTree * CreateBSTNode (int x )
{
相关文章
BSTree * newNode = (BSTree *)malloc (sizeof (BSTree ));
newNode ->data = x ;
newNode ->height = 0;
newNode ->lchild = NULL ;
newNode ->rchild = NULL ;
return newNode ;
}
int getHeight (BSTree * root ) //求⼀个节点的⾼
x
int getHeight(BSTree* root)//求⼀个节点的⾼
{
if(!root)
{
return-1;
}
el
{
return root->height;
}
}
int getMax(int a,int b)
{
政治表现及具体事例
if(a > b)
return a;
return b;
}
BSTree*RtSgRotation(BSTree* root)//右单旋（right single rotation）
印度尼西亚首都
{
BSTree* temp;
temp = root->lchild;
root->lchild = temp->rchild;
temp->rchild = root;
root->height =getMax(getHeight(root->lchild),getHeight(root->rchild))+1;
temp->height =getMax(getHeight(temp->lchild), root->height)+1;
return temp;
}
BSTree*LtSgRotation(BSTree* root)//左单旋（left single rotation）
{
BSTree* temp;
temp = root->rchild;
root->rchild = temp->lchild;
temp->lchild = root;
root->height =getMax(getHeight(root->lchild),getHeight(root->rchild))+1;
temp->height =getMax(getHeight(temp->rchild), root->height)+1;
return temp;
}
BSTree*RtDbRotation(BSTree* root)//右双旋（right double rotation）= 左单旋+右单旋
{
root->lchild =LtSgRotation(root->lchild);
return RtSgRotation(root);
}
BSTree*LtDbRotation(BSTree* root)//左双旋（left double rotation）= 右单旋+左单旋
{
root->rchild =RtSgRotation(root->rchild);
return LtSgRotation(root);
}研究生考试国家线
BSTree*CreateBSTree(BSTree* root,int x)
{
if(!root)
{
root =CreateBSTNode(x);
return root;
}
el if(x < root->data)// 插⼊的时候，x会被插⼊在左⼦树
{
root->lchild =CreateBSTree(root->lchild, x);
if(getHeight(root->lchild)-getHeight(root->rchild)==2)//如果左右孩⼦的⾼相差2，就需要右旋转来解决了{
if(x < root->lchild->data)
if(x < root->lchild->data)
root =RtSgRotation(root);// 如果x⽐左孩⼦的数据⼩，说明被插⼊到了左孩⼦的左孩⼦，那么就是右单旋el
root =RtDbRotation(root);// 如果x⽐左孩⼦的数据⼤，说明被插⼊到了左孩⼦的右孩⼦，那么就是右双旋}
}
el if(x > root->data)// 插⼊的时候，x会被插⼊在右⼦树
{
root->rchild =CreateBSTree(root->rchild, x);
if(getHeight(root->rchild)-getHeight(root->lchild)==2)//如果右左孩⼦的⾼相差2，就需要左旋转来解决了{
if(x > root->rchild->data)
root =LtSgRotation(root);// 如果x⽐右孩⼦的数据⼤，说明被插⼊到了右孩⼦的右孩⼦，那么就是左单旋el
root =LtDbRotation(root);// 如果x⽐右孩⼦的数据⼩，说明被插⼊到了右孩⼦的左孩⼦，那么就是左双旋}
}
root->height =getMax(getHeight(root->lchild),getHeight(root->rchild))+1;
return root;
}
void preOrder(BSTree* root)
{
if(root)
{
printf("%d ", root->data);
preOrder(root->lchild);
preOrder(root->rchild);
}
}
void midOrder(BSTree* root)
{
if(root)
{
midOrder(root->lchild);
printf("%d ", root->data);
midOrder(root->rchild);
}
}
void postOrder(BSTree* root)
{
if(root)
{
postOrder(root->lchild);
postOrder(root->rchild);
printf("%d ", root->data);
}
}
BSTree*find(BSTree* root,int x)
{
if(!root)
return NULL;
if(x < root->data)
return find(root->lchild, x);
el if(x > root->data)
return find(root->rchild, x);
el
return root;
}
/*
BSTree* find(BSTree* root, int x)
{
BSTree* curNode = root;
//BSTree* curParNode;
int flag = 0;
