Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

PAT 1066. Root of AVL Tree

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.


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 N distinct 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 ythe root of the resulting AVL tree in one line.

Sample Input 1

5
88 70 61 96 120

Sample Output 1

70

Sample Input 2

7
88 70 61 96 120 90 65

Sample Output 2

88

解答

#include <cstdio>
#include <algorithm>
using namespace std;

struct Node 
{
	int key, height;
	Node *left, *right, *parent;
	Node (int val) : key(val), height(0), left(NULL), right(NULL), parent(NULL) {}
};

struct Tree 
{
	Node *root;
	Tree () : root(NULL) {}
};

void updateHeight (Node *x)
{
	Node *l = x->left, *r = x->right; 
	if (l && r) x->height = max(l->height, r->height) + 1;
	else if (l) x->height = l->height + 1;
	else if (r) x->height = r->height + 1;
	else x->height = 0;
}

int getBalance (Node *x)
{
	Node *l = x->left, *r = x->right;
	if (l && r) return l->height - r->height;
	else if (l) return l->height + 1;
	else if (r) return -r->height - 1;
	else return 0;
}

void leftRotate (Tree *tree, Node *x)
{
	//x的右儿子不能为空
	if (x->right == NULL) return;

	//记录图中标识的y节点
	Node *y = x->right;

	//修正x和y的左儿子b之间的链接
	x->right = y->left;
	if (y->left != NULL) y->left->parent = x;

	//修正x的父亲和y之间的链接
	y->parent = x->parent;
	if (x->parent == NULL)   //x为树根
		tree->root = y;
	else if(x == x->parent->left) //x为左儿子
		x->parent->left = y;
	else                          //x为右儿子
		x->parent->right = y;

	//修正x和y之间的链接
	y->left = x;
	x->parent = y;

	updateHeight(x); 
	updateHeight(y);
}

void rightRotate (Tree *tree, Node *x)
{
	//x的左儿子不能为空
	if (x->left == NULL) return;

	//记录图中标识的y节点
	Node *y = x->left;

	//修正x和y的右儿子b之间的链接
	x->left = y->right;
	if (y->right != NULL) y->right->parent = x;

	//修正x的父亲和y之间的链接
	y->parent = x->parent;
	if (x->parent == NULL)   //x为树根
		tree->root = y;
	else if(x == x->parent->left) //x为左儿子
		x->parent->left = y;
	else                          //x为右儿子
		x->parent->right = y;

	//修正x和y之间的链接
	y->right = x;
	x->parent = y;

	updateHeight(x); 
	updateHeight(y);
}

void balanceNode (Tree *tree, Node *x)
{
	int balance = getBalance(x);
	if (balance > 1)
	{
		if (getBalance(x->left) < 0) leftRotate(tree, x->left);
		rightRotate(tree, x);
	}
	else if (balance < -1)
	{
		if (getBalance(x->right) > 0) rightRotate(tree, x->right);
		leftRotate(tree, x);
	}
}

void insertNode (Tree *tree, int key)
{
	Node *z = new Node(key);

	// 向下查找待插入的位置,x为当前节点(最终为空节点),y为其父亲
	Node *x = tree->root, *y = NULL;
	while (x != NULL)
	{
		y = x;
		if (z->key == x->key) return;
		else if (z->key < x->key) x = x->left;
		else x = x->right;
	}

	z->parent = y;
	if (y == NULL) tree->root = z;
	else if (z->key < y->key) y->left = z;
	else y->right = z;

	while (z)
	{
		updateHeight(z); 
		balanceNode(tree, z);
		z = z->parent;
		
	}	
}

void preorder(Tree *tree, Node *x)
{
	if (x == NULL) return;

	printf("%-2d  left:%2d  right:%2d\n", x->key, x->left ? x->left->key: -1, x->right ? x->right->key : -1); //根节点
	preorder(tree, x->left);      //左子树
	preorder(tree, x->right);     //右子树
}

int main()
{
	Tree avl;
	int n, t; scanf("%d", &n);
	while (n--) scanf("%d", &t), insertNode(&avl, t);
	printf("%d\n", avl.root->key);
	return 0;
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论