Root of AVL Tree (25)

1、题意

求所有数插入后，根节点是哪个数

2、两种代码：

2.1 代码1：

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 30; 
int l[N],r[N],v[N],h[N],idx;

void update(int u)// 计算子树的高度 
{
h[u] = max(h[l[u]],h[r[u]]) + 1;
} 

void R(int &u)// 右旋 
{
int p = l[u];
l[u] = r[p],r[p] = u;
update(u),update(p);
u = p; 
}

void L(int &u)
{
int p = r[u];
r[u] = l[p],l[p] = u;
update(u),update(p);
u = p;
}

int get_balance(int u)
{
//左子树高度减去右子树高度
return h[l[u]] - h[r[u]]; 
}
void insert(int &u,int w)
{
if(!u) u = ++idx,v[u] = w; // 一开始u = 0 
else if(w<v[u]) 
{
insert(l[u],w);
if(get_balance(u)==2)
{
if(get_balance(l[u])==1) R(u);
else L(l[u]),R(u);
}
}
else
{
insert(r[u],w);
if(get_balance(u)==2)
{
if(get_balance(r[u])==-1) L(u);
else R(r[u]),L(u);
}

}
update(u);// 每次都要统计一下高度,这个高度在不断的迭代 
}

int main()
{
int n,root = 0;
scanf("%d",&n);
while(n--)
{
int w;
scanf("%d",&w);
insert(root,w);
}
cout<<v[root]<<endl;
return 0;
 } 

2.2 手写AVL树

// 一次机会手写AVL树
#include<bits/stdc++.h> 
#define LH 1
#define EH 0
#define RH -1
using namespace std;

struct AVLTreeNode
{
int value; // 值，平衡因子 
int BF;
AVLTreeNode* lchild;// 左孩子 
AVLTreeNode* rchild;// 右孩子
};
// 平衡操作
void RightRotation(AVLTreeNode* &pRoot);// 右旋操作
void LeftRotation(AVLTreeNode* &pRoot);// 左旋操作
void LeftBalance(AVLTreeNode* &pRoot);// 左平衡
void RightBalance(AVLTreeNode* &pRoot);// 右平衡

// 常规操作
bool InsertAVL(AVLTreeNode* &pRoot,int value,bool &taller);

int main()
{
std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
AVLTreeNode* pRoot = NULL;
bool taller = false;
int value,N;
cin>>N;
for(int i = 0;i<N;i++)
{
cin>>value;
InsertAVL(pRoot,value,taller);
}
cout<<pRoot->value<<endl;
return 0;
} 
// 新节点插入成功，则返回true
// taller 反映树是否长高
bool InsertAVL(AVLTreeNode* &pRoot,int value,bool &taller)
{
if(!pRoot)
{
pRoot = new AVLTreeNode();
pRoot->BF = EH;
pRoot->value = value;
pRoot->lchild = pRoot->rchild = NULL;
taller = true;
}
else
{
if(value == pRoot->value)
{
taller = false;
return false;
}
if(value < pRoot->value)
{
if(!InsertAVL(pRoot->lchild,value,taller))
return false;
if(taller)
{
switch(pRoot->BF)
{
case LH: // 原来左边偏高，还是插在了左边
LeftBalance(pRoot);
taller = false;// 处理后高度不变；
break;
case EH:// 原本等高，插左边后长高
pRoot->BF = LH;
taller = true;
break;
case RH:// 原本右侧高，插在左侧，高度不变 
pRoot->BF = EH;
taller = false;
break; 
}
}
}
else 
{
if(!InsertAVL(pRoot->rchild,value,taller))
return false;
if(taller)
{
switch(pRoot->BF)
{
case LH:// 原本左侧高，插在了右侧，登高
pRoot->BF = EH;
taller = false;
break;
case EH:
pRoot->BF = RH;
taller = true;
break;
case RH:;
RightBalance(pRoot);
taller = false;
break;
}
}
}
}
return true;
}
// 左旋，以pRoot为根节点的树进行左旋处理，并调整好父子连接
void LeftRotation(AVLTreeNode* &pRoot)
{
// pRoot现在为失衡节点，pRitht为pRoot的右子节点，pRoot,pRitht进行左旋处理
AVLTreeNode* pRight = pRoot->rchild;

pRoot->rchild = pRight->lchild;
pRight->lchild = pRoot;

pRoot = pRight;
}
// 右旋，以pRoot为根节点的树进行右旋处理，并调整好父子连接
void RightRotation(AVLTreeNode* &pRoot)
{
// pRoot现在为失衡节点，pleft为pRoot的左子节点，对pRoot和pLeft进行右旋
AVLTreeNode *pLeft = pRoot->lchild;
pRoot->lchild = pLeft->rchild;
pLeft->rchild = pRoot;

pRoot = pLeft;
}
// 对左边的失衡部分进行平衡处理
void LeftBalance(AVLTreeNode* &pRoot)
{
AVLTreeNode *pLeft,*pLeftRight;
pLeft = pRoot->lchild;
switch(pLeft->BF)
{
case LH: // LL型
pRoot->BF = EH;
pLeft->BF = EH;
RightRotation(pRoot);
break;
case RH: // LR型 
pLeftRight = pLeft->rchild;
switch(pLeftRight->BF)
{
case LH:
pRoot->BF = RH;
pLeft->BF = EH;
break;
case EH:
pRoot->BF = EH;
pLeft->BF = EH;
break;
case RH:
pRoot->BF = EH;
pLeft->BF = LH;
break;
}
pLeftRight->BF = EH;
LeftRotation(pRoot->lchild);
RightRotation(pRoot);// 这里不能写出pleft
break;
}
}
void RightBalance(AVLTreeNode* &pRoot)
{
AVLTreeNode* pRight,*pRightLeft;
pRight = pRoot->rchild;
switch(pRight->BF)
{
case RH: // RR型
pRoot->BF = pRight->BF = EH;
LeftRotation(pRoot);
break;
case LH: // RL型
pRightLeft = pRight->lchild;
switch(pRightLeft->BF)
{
case LH:
pRoot->BF = EH;
pRight->BF = RH;
break;
case EH:
pRoot->BF = EH;
pRight->BF = EH;
break;
case RH:
pRoot->BF = LH;
pRight->BF = EH;
break;
}
pRightLeft->BF = EH;
RightRotation(pRoot->rchild);
LeftRotation(pRoot);
break;
}
} 

 

原文地址：https://blog.csdn.net/atm7758258/article/details/136483133

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！