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;		
	}	
}