7-32 균형 두 갈래 나무의 뿌리

제목을 붙이기 전에 몇 가지 개념을 알아야 한다. 두 갈래 나무, 두 갈래 검색 나무, 균형 두 갈래 나무.네가 정말 할 수 있는지 없는지를 평가하려면 기본적인 조작이 스스로 실현될 수 있는지를 보아야 한다.두 갈래 나무, 지침역에 좌우 아이가 있다.두 갈래 검색 트리, 왼쪽 아이의 키 값이 오른쪽 아이보다 크다.균형 두 갈래 나무는 아이의 깊이를 좌우하는 절대치가 1보다 크지 않다.이 세 가지 개념은 층층이 전진한다.(전재:https://blog.csdn.net/qq_39825375/article/details/84778135)
제목은 다음과 같습니다.
7-32 균형 두 갈래 나무의 뿌리(25분)
주어진 일련의 숫자를 처음에 비어 있는 AVL 트리에 삽입합니다. 마지막으로 생성된 AVL 트리의 루트 결점 값을 출력하십시오.

형식 입력:

입력한 첫 번째 줄은 정수 N(≤20)을 주고 그 다음 줄은 공백으로 구분된 N개의 다른 정수를 줍니다.

출력 형식:

위의 정수를 처음에 비어 있는 AVL 트리에 한 줄의 출력 순서에 삽입하면 트리의 루트 끝점의 값이 됩니다.

샘플 입력 1:

5
88 70 61 96 120

샘플 내보내기 1:

70

샘플 2:

7
88 70 61 96 120 90 65

샘플 내보내기 2:

88

제목이 명확해서 균형 잡힌 두 갈래 나무의 삽입을 실현했다.1. 왼쪽 높이에서 회전, 2.오른쪽으로 높이 선회하다.먼저 왼쪽이 높고 오른쪽이 높으면 회전하고, 4.먼저 오른쪽이 높고 뒤에 왼쪽이 높으면 회전한다(주의! 이곳의 선후는 실행 시간의 선후가 아니라 두 갈래 나무의 공간의 선후를 균형 있게 하는 것이다). 코드는 다음과 같다.
 
80                                  100                                                     120                          100
\오른쪽 높이 회전/\/왼쪽 높이 회전/\
  100      ------------>      80    120                                        100    ------------->       80     120
       \                                                                                 /
          120                                                                       80

AVLNode SingleLeftRotation(AVLNode A);// 
AVLNode SingleLeftRotation(AVLNode A)
{
	AVLNode B=A->lchild;
	A->lchild=B->rchild;
	B->rchild=A;
	return B;
}
AVLNode SingleRightRotation(AVLNode A);// 
AVLNode SingleRightRotation(AVLNode A)
{
	AVLNode B=A->rchild;
	A->rchild=B->lchild;
	B->lchild=A;
	return B;
}

    80                                          80                                   90
/뒤 오른쪽 높이 회전/왼쪽 높이 회전/\
100   ----------------->             90     ---------------->         80        100
   \                                      /
    90                                  100
80                                           80                                            90
\뒤 왼쪽 높이 회전\먼저 오른쪽 높이 회전/\
     100   ----------------->             90     ---------------->         80        100
     /                                            \
    90                                           100

AVLNode DoubleLeftRightRotation(AVLNode A);// 
AVLNode DoubleLeftRightRotation(AVLNode A)
{
	A->rchild=SingleRightRotation(A->rchild);// 
	return SingleLeftRotation(A);// 
}
AVLNode DoubleRightLeftRotation(AVLNode A);// 
AVLNode DoubleRightLeftRotation(AVLNode A)
{
	A->lchild=SingleLeftRotation(A->lchild);// 
	return SingleRightRotation(A);// 
}

좌우로 회전하는 네 가지 상황(실제로는 두 가지 상황)을 알면 삽입 조작을 실현할 수 있고 비교적 간단하다.첫 번째 상황은 비어 있거나 비어 있는 트리로 귀속될 때 직접 삽입한다.두 번째 상황은 왼쪽 나무에 삽입되었는지 오른쪽 나무에 삽입되었는지 판단하고 다시 한 번 삽입한다. 이어서 불균형 여부를 판단한다. 만약에 구체적인 나무 구조를 판단하고 회전한다.세 번째 경우, 이 키 값은 트리에 있습니다. 삽입하지 않고 바로 되돌아옵니다.코드는 다음과 같습니다.

AVLNode InsertAVL(AVLNode A,int x);
AVLNode InsertAVL(AVLNode A,int x)
{
	if(!A)//1. ；2. 
	{
		A=new node;
		A->Data=x;
		A->lchild=A->rchild=NULL;
	}
	else if(A->Datarchild=InsertAVL(A->rchild,x);// 
		if(GetHeight(A->rchild)-GetHeight(A->lchild)==2)// 
		{
			if(A->rchild->DataData>x)// 
	{
		A->lchild=InsertAVL(A->lchild,x);// 
		if(GetHeight(A->lchild)-GetHeight(A->rchild)==2)// 
		{
			if(xlchild->Data)	A=SingleLeftRotation(A);// 
			else A=DoubleLeftRightRotation(A);// 
		}
	}
	return A;
//1. ， A；2.A-.Data==x ；3. ， 。
}

이로써 주 함수의 작성만 남았으니 대의해서는 안 된다.트리는 선언할 때 즉시 NULL로 초기화하여 와일드 포인터가 되지 않도록 해야 한다.2. InsertAVL의 반환 값은 트리 A에 즉시 반환되어야 합니다.코드는 다음과 같습니다.

int main()
{
	freopen("in.txt","r",stdin);
	int n,x;
	AVLNode A=NULL; //!!!
	scanf("%d",&n);
	for(int i=0;iData);
	return 0;
}

전체 코드는 다음과 같습니다.

#if 1 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include