1066 root of AVL tree (25 points)

maxmin

1066 Root of AVL Tree (25 branch )

The question

Give a set of numbers , Insert them into the balanced binary search tree , Find the root node .

Ideas

Board question , structure avl A tree will do .
structure avl Trees
avl On the basis of binary sort tree, the tree changes the root node by left-right rotation so that the height difference between the left and right subtrees of the tree does not exceed 1.
structure avl Trees
Some column functions ：

Building a structure includes ： Node height , Node weights , Left and right subtrees

typedef struct node{
    
	int data,height;
	node *lchild,*rchild;
}node;

Create new nodes , The left and right Subtrees Are NULL, The height is 1

node* newNode(int v)
{
    
	node* p=new node;
	p->data=v;
	p->height=1;
	p->lchild=p->rchild=NULL;
	return p;
}

Get node height

int getHeight(node* root)
{
    
	if(root==NULL){
    
		return 0;
	}else{
    
		return root->height;
	}
}

Update node height

void updateHeight(node* root)
{
    
	root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1;
}

Get the height difference between the left and right subtrees of the node （ Balance factor ）

int getBalanceFactor(node* root)
{
    
	return getHeight(root->lchild)-getHeight(root->rchild);
}

left-handed

Left rotation is required because the right subtree is higher than the left subtree by more than 1, At this point, set the right child of the root node as the root node , The left child of the right child of the root node is set as the right child of the root node . Update node height .

void L(node* &root)
{
    
	node* temp=root->rchild;
	root->rchild=temp->lchild;
	temp->lchild=root;
	updateHeight(root);
	updateHeight(temp);
	root=temp;
}

Right hand

And left-handed symmetry （ Just turn left and right ）

void R(node* &root)
{
    
	node* temp=root->lchild;
	root->lchild=temp->rchild;
	temp->rchild=root;
	updateHeight(root);
	updateHeight(temp);
	root=temp;
}

Insert node

There are four situations that require left-right rotation
1. The left subtree of the root node is higher than the right subtree , The left subtree lchild Left subtree ratio of lchild The right tree is tall （LL)
2. The left subtree of the root node is higher than the right subtree , The left subtree lchild Left subtree ratio of lchild Right subtree low (LR)
3. The left subtree of the root node is lower than the right subtree , Right subtree rchild Left subtree ratio of rchild The right tree is tall (RL)
4. The left subtree of the root node is lower than the right subtree , Right subtree rchild Left subtree ratio of rchild Right subtree low (RR)

void insert(node* &root,int v)
{
    
	if(root==NULL){
    
		root=newNode(v);
		return ;	
	}
	if(root->data>v){
    
		insert(root->lchild,v);
		updateHeight(root);
		if(getBalanceFactor(root)==2){
    
			if(getBalanceFactor(root->lchild)==1){
    	//LL type 
				R(root);
			}else if(getBalanceFactor(root->lchild)==-1){
    	//LR type 
				L(root->lchild);
				R(root);
			}
		}
	}else{
    
		insert(root->rchild,v);
		updateHeight(root);
		if(getBalanceFactor(root)==-2){
    
			if(getBalanceFactor(root->rchild)==-1){
    	//RR type 
				L(root);
			}else if(getBalanceFactor(root->rchild)==1){
    		//RL type 
				R(root->rchild);
				L(root);
			}
		}
	}
}

Code

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef struct node{
    
	int data,height;
	node *lchild,*rchild;
}node;
node* newNode(int v)	
{
    
	node* p=new node;
	p->data=v;
	p->height=1;
	p->lchild=p->rchild=NULL;
	return p;
}
int getHeight(node* root)
{
    
	if(root==NULL){
    
		return 0;
	}else{
    
		return root->height;
	}
}
int getBalanceFactor(node* root)
{
    
	return getHeight(root->lchild)-getHeight(root->rchild);
}
void updateHeight(node* root)
{
    
	root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1;
}
void L(node* &root)
{
    
	node* temp=root->rchild;
	root->rchild=temp->lchild;
	temp->lchild=root;
	updateHeight(root);
	updateHeight(temp);
	root=temp;
}
void R(node* &root)
{
    
	node* temp=root->lchild;
	root->lchild=temp->rchild;
	temp->rchild=root;
	updateHeight(root);
	updateHeight(temp);
	root=temp;
}
void insert(node* &root,int v)
{
    
	if(root==NULL){
    
		root=newNode(v);
		return ;	
	}
	if(root->data>v){
    
		insert(root->lchild,v);
		updateHeight(root);
		if(getBalanceFactor(root)==2){
    
			if(getBalanceFactor(root->lchild)==1){
    
				R(root);
			}else if(getBalanceFactor(root->lchild)==-1){
    
				L(root->lchild);
				R(root);
			}
		}
	}else{
    
		insert(root->rchild,v);
		updateHeight(root);
		if(getBalanceFactor(root)==-2){
    
			if(getBalanceFactor(root->rchild)==-1){
    
				L(root);
			}else if(getBalanceFactor(root->rchild)==1){
    
				R(root->rchild);
				L(root);
			}
		}
	}
}
int main()
{
    
	int n,x;
	node *root=NULL;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
    
		scanf("%d",&x);
		insert(root,x);
// printf("###\n");
	}
	printf("%d\n",root->data);
}