04 - 나무 5 Root of AVL Tree
6567 단어 데이터 구조 - 진 월하 흠 명
AVL 트 리 를 만들어 뿌리 노드 의 값 을 출력 합 니 다.
참조 코드
#include <bits/stdc++.h>
using namespace std;
typedef struct Node{
int v,h;
struct Node *l,*r;
}*tree;
int GetHigh(tree t){
if (t==NULL) return 0;
return max(GetHigh(t->l),GetHigh(t->r))+1;
}
tree RotateLL(tree &A){
tree B=A->l;
A->l=B->r;
B->r=A;
B->h=max(GetHigh(B->l),GetHigh(B->r))+1;
A->h=max(GetHigh(A->l),GetHigh(B->r))+1;
return B;
}
tree RotateRR(tree &A){
tree B=A->r;
A->r=B->l;
B->l=A;
B->h=max(GetHigh(B->l),GetHigh(B->r))+1;
A->h=max(GetHigh(A->l),GetHigh(B->r))+1;
return B;
}
tree RotateLR(tree &A){
A->l=RotateRR(A->l);
return RotateLL(A);
}
tree RotateRL(tree &A){
A->r=RotateLL(A->r);
return RotateRR(A);
}
tree Insert(tree &t,int x){
if (t==NULL){
t=new Node;
t->v=x;
t->h=0;
t->l=t->r=NULL;
return t;
}
if (x<t->v){
t->l=Insert(t->l,x);
if (GetHigh(t->l)-GetHigh(t->r)==2){
if (x<t->l->v) t=RotateLL(t);
else t=RotateLR(t);
}
}
else{
t->r=Insert(t->r,x);
if (GetHigh(t->l)-GetHigh(t->r)==-2){
if (x>t->r->v) t=RotateRR(t);
else t=RotateRL(t);
}
}
t->h=max(GetHigh(t->l),GetHigh(t->r))+1;
return t;
}
int main(){
int n,x;
cin>>n;
tree t=NULL;
for (int i=0;i<n;i++){
cin>>x;
Insert(t,x);
}
cout<<t->v<<endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
04 - 나무 5 Root of AVL Tree제목 AVL 트 리 를 만들어 뿌리 노드 의 값 을 출력 합 니 다. 참조 코드...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.