1066 Root of AVL Tree (25 分) 构造平衡二叉树并输出根节点

今天药忘吃喽~ 2021-10-29 14:58 242阅读 0赞

1066 Root of AVL Tree (25 分)

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

![aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzMx][] ![aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzMy][]

![aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzMz][] ![aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzM0][]

Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

### Input Specification: ###

Each input file contains one test case. For each case, the first line contains a positive integer N (≤20) which is the total number of keys to be inserted. Then Ndistinct integer keys are given in the next line. All the numbers in a line are separated by a space.

### Output Specification: ###

For each test case, print the root of the resulting AVL tree in one line.

### Sample Input 1: ###

5
    88 70 61 96 120

### Sample Output 1: ###

### Sample Input 2: ###

7
    88 70 61 96 120 90 65

### Sample Output 2: ###

题意：构造平衡二叉树并输出根节点，四种旋转均有涉及

小梁bb：这道题是MOOC数据结构的练习题，然后我发现浙大数据结构教材的RR是右旋，和王道&模板代码的相反...

#include <iostream>
    using namespace std;
    struct node 
    {
        int val;
        struct node *left,*right;
    };
    node *Left(node *root) //左旋
    {
        node *t=root->right;
        root->right=t->left;
        t->left=root;
        return t;
    }
    node *Right(node *root) //右旋
    {
        node *t=root->left;
        root->left=t->right;
        t->right=root;
        return t;
    }
    node *LeftRight(node *root) //先左旋后右旋
    {
        root->left=Left(root->left);
        return Right(root);
    }
    node *RightLeft(node *root) //先右旋后左旋
    {
        root->right=Right(root->right);
        return Left(root);
    }
    int getHeight(node *root) 
    {
        if(root==NULL) return 0;
        return max(getHeight(root->left),getHeight(root->right))+1;
    }
    node *insert(node *root,int val) 
    {
        if(root==NULL) 
        {
            root=new node();
            root->val=val;
            root->left=root->right=NULL;
        } 
        else if(val<root->val) 
        {
            root->left=insert(root->left, val);
            if(getHeight(root->left)-getHeight(root->right)==2)
            root= val < root->left->val ? Right(root):LeftRight(root);
        } 
        else
        {
            root->right = insert(root->right, val);
            if(getHeight(root->left)-getHeight(root->right)==-2)
            root= val > root->right->val ? Left(root):RightLeft(root);
        }
        return root;
    }
    int main() 
    {
        int n,val,i;
        scanf("%d",&n);
        node *root=NULL;
        for(i=0;i<n;i++) 
        {
            scanf("%d",&val);
            root=insert(root,val);
        }
        printf("%d",root->val);
    }

浙大书本代码：

#include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef int ElementType;
    typedef struct AVLNode *Position;
    typedef Position AVLTree;
    typedef struct AVLNode{
    	ElementType Data;
    	AVLTree Left;
    	AVLTree Right;
    	int Height;
    };
    int GetHeight(AVLTree T)
    {
    	int l,r,maxh;
    	if(T)
    	{
    		l=GetHeight(T->Left);
    		r=GetHeight(T->Right);
    		maxh=l>r?l:r;
    		return (maxh+1);
    	}
    	else return 0;
    }
    AVLTree SingleLeftRotation(AVLTree A)
    {
    	AVLTree B=A->Left;
    	A->Left=B->Right;
    	B->Right=A;
    	A->Height=max(GetHeight(A->Left),GetHeight(A->Right))+1;
    	B->Height=max(GetHeight(B->Left),A->Height)+1;
    	return B;
    }
    AVLTree SingleRightRotation(AVLTree A)
    {
    	AVLTree B=A->Right;
    	A->Right=B->Left;
    	B->Left=A;
    	A->Height=max(GetHeight(A->Left),GetHeight(A->Right))+1;
    	B->Height=max(GetHeight(B->Right),A->Height)+1;
    	return B;
    }
    AVLTree DoubleLeftRightRotation(AVLTree A)
    {
    	A->Left=SingleRightRotation(A->Left);
    	return SingleLeftRotation(A);
    }
    AVLTree DoubleRightLeftRotation(AVLTree A)
    {
    	A->Right=SingleLeftRotation(A->Right);
    	return SingleRightRotation(A);
    }
    AVLTree Insert(AVLTree T,ElementType x)
    {
    	if(!T)
    	{
    		T=(AVLTree)malloc(sizeof(struct AVLNode));
    		T->Data=x;
    		T->Height=1;
    		T->Left=T->Right=NULL;
    	}
    	else if(x<T->Data)
    	{
    		T->Left=Insert(T->Left,x);
    		if(GetHeight(T->Left)-GetHeight(T->Right)==2)
    		{
    			if(x<T->Left->Data)
    			T=SingleLeftRotation(T);
    			else 
    			T=DoubleLeftRightRotation(T);
    		}
    	}
    	else if(x>T->Data)
    	{
    		T->Right=Insert(T->Right,x);
    		if(GetHeight(T->Left)-GetHeight(T->Right)==-2)
    		{
    			if(x>T->Right->Data)
    			T=SingleRightRotation(T);
    			else 
    			T=DoubleRightLeftRotation(T);
    		}
    	}
    	T->Height=max(GetHeight(T->Left),GetHeight(T->Right))+1;
    	return T;
    }
    int main()
    {
    	int n,i;
    	ElementType x;
    	AVLTree T;
    	T=NULL;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d",&x);
    		T=Insert(T,x);
    	}
    	printf("%d\n",T->Data);
    }

[aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzMx]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzMx
[aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzMy]: /images/20211029/34a13a33ac3741ab8ec8c66575e0aa4f.png
[aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzMz]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzMz
[aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzM0]: /images/20211029/aad2d348990d45099aeff3a2522203b0.png