PAT-Advanced-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

1 2	5 88 70 61 96 120

Sample Output 1:

70

Sample Input 2:

7
88 70 61 96 120 90 65

1 2	7 88 70 61 96 120 90 65

Sample Output 2:

88

偷懒写了递归版……

代码如下：

#include<stdio.h>
#include<stdlib.h>
#define AVL_BALANCED 0
#define AVL_LEFT_HEAVY 1
#define AVL_RIGHT_HEAVY -1
typedef struct bistree_node
{
	int data;
	int factor;
	struct bistree_node *left;
	struct bistree_node *right;
} bistree_node;
typedef struct bistree
{
	bistree_node *root;
} bistree;
bistree_node *roate_left(bistree_node *root)
{
	bistree_node *left,*grandchild;
	left=root->left;
	if(left->factor==AVL_LEFT_HEAVY)
	{
		root->left=left->right;
		left->right=root;
		root->factor=AVL_BALANCED;
		left->factor=AVL_BALANCED;
		return left;
	}
	grandchild=left->right;
	root->left=grandchild->right;
	grandchild->right=root;
	left->right=grandchild->left;
	grandchild->left=left;
	switch(grandchild->factor)
	{
		case AVL_LEFT_HEAVY:
			left->factor=AVL_BALANCED;;
			root->factor=AVL_RIGHT_HEAVY;
			break;
		case AVL_BALANCED:
			left->factor=AVL_BALANCED;
			root->factor=AVL_BALANCED;
			break;
		case AVL_RIGHT_HEAVY:
			left->factor=AVL_LEFT_HEAVY;;
			root->factor=AVL_BALANCED;
			break;
	}
	grandchild->factor=AVL_BALANCED;
	return grandchild;
}
bistree_node *roate_right(bistree_node *root)
{
	bistree_node *right,*grandchild;
	right=root->right;
	if(right->factor==AVL_RIGHT_HEAVY)
	{
		root->right=right->left;
		right->left=root;
		root->factor=AVL_BALANCED;
		right->factor=AVL_BALANCED;
		return right;
	}
	grandchild=right->left;
	root->right=grandchild->left;
	grandchild->left=root;
	right->left=grandchild->right;
	grandchild->right=right;
	switch(grandchild->factor)
	{
		case AVL_LEFT_HEAVY:
			right->factor=AVL_RIGHT_HEAVY;
			root->factor=AVL_BALANCED;
			break;
		case AVL_BALANCED:
			right->factor=AVL_BALANCED;
			root->factor=AVL_BALANCED;
			break;
		case AVL_RIGHT_HEAVY:
			right->factor=AVL_BALANCED;
			root->factor=AVL_LEFT_HEAVY;
			break;
	}
	grandchild->factor=AVL_BALANCED;
	return grandchild;
}
bistree_node *insert(bistree_node *root,int data,int *balance)
{
	if(root==NULL)
	{
		root=(bistree_node *)malloc(sizeof(bistree_node));
		root->left=NULL;
		root->right=NULL;
		root->factor=AVL_BALANCED;
		root->data=data;
		*balance=0;
		return root;
	}
	if(root->data>=data)
	{
		root->left=insert(root->left,data,balance);
		if(*balance==0)
		{
			switch(root->factor)
			{
				case AVL_LEFT_HEAVY:
					root=roate_left(root);
					*balance=1;
					break;
				case AVL_BALANCED:
					root->factor=AVL_LEFT_HEAVY;
					break;
				case AVL_RIGHT_HEAVY:
					root->factor=AVL_BALANCED;
					*balance=1;
					break;
			}
		}
	}
	else
	{
		root->right=insert(root->right,data,balance);
		if(*balance==0)
		{
			switch(root->factor)
			{
				case AVL_LEFT_HEAVY:
					root->factor=AVL_BALANCED;
					*balance=1;
					break;
				case AVL_BALANCED:
					root->factor=AVL_RIGHT_HEAVY;
					break;
				case AVL_RIGHT_HEAVY:
					root=roate_right(root);
					*balance=1;
					break;
			}	
		}
	}
	return root;
}
int main()
{
	int n,i,temp,balance=0;
	bistree *tree;
	scanf("%d",&n);
	tree=(bistree *)malloc(sizeof(bistree));
	tree->root=NULL;
	for(i=0;i<n;i++)
	{
		scanf("%d",&temp);
		balance=0;
		tree->root=insert(tree->root,temp,&balance);
	}
	printf("%d\n",tree->root->data);
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

#include<stdio.h>

#include<stdlib.h>

#define AVL_BALANCED 0

#define AVL_LEFT_HEAVY 1

#define AVL_RIGHT_HEAVY -1

typedef struct bistree_node

{

int data;

int factor;

struct bistree_node *left;

struct bistree_node *right;

} bistree_node;

typedef struct bistree

{

bistree_node *root;

} bistree;

bistree_node *roate_left(bistree_node *root)

{

bistree_node *left,*grandchild;

left=root->left;

if(left->factor==AVL_LEFT_HEAVY)

{

root->left=left->right;

left->right=root;

root->factor=AVL_BALANCED;

left->factor=AVL_BALANCED;

return left;

}

grandchild=left->right;

root->left=grandchild->right;

grandchild->right=root;

left->right=grandchild->left;

grandchild->left=left;

switch(grandchild->factor)

{

case AVL_LEFT_HEAVY:

left->factor=AVL_BALANCED;;

root->factor=AVL_RIGHT_HEAVY;

break;

case AVL_BALANCED:

left->factor=AVL_BALANCED;

root->factor=AVL_BALANCED;

break;

case AVL_RIGHT_HEAVY:

left->factor=AVL_LEFT_HEAVY;;

root->factor=AVL_BALANCED;

break;

}

grandchild->factor=AVL_BALANCED;

return grandchild;

}

bistree_node *roate_right(bistree_node *root)

{

bistree_node *right,*grandchild;

right=root->right;

if(right->factor==AVL_RIGHT_HEAVY)

{

root->right=right->left;

right->left=root;

root->factor=AVL_BALANCED;

right->factor=AVL_BALANCED;

return right;

}

grandchild=right->left;

root->right=grandchild->left;

grandchild->left=root;

right->left=grandchild->right;

grandchild->right=right;

switch(grandchild->factor)

{

case AVL_LEFT_HEAVY:

right->factor=AVL_RIGHT_HEAVY;

root->factor=AVL_BALANCED;

break;

case AVL_BALANCED:

right->factor=AVL_BALANCED;

root->factor=AVL_BALANCED;

break;

case AVL_RIGHT_HEAVY:

right->factor=AVL_BALANCED;

root->factor=AVL_LEFT_HEAVY;

break;

}

grandchild->factor=AVL_BALANCED;

return grandchild;

}

bistree_node *insert(bistree_node *root,int data,int *balance)

{

if(root==NULL)

{

root=(bistree_node *)malloc(sizeof(bistree_node));

root->left=NULL;

root->right=NULL;

root->factor=AVL_BALANCED;

root->data=data;

*balance=0;

return root;

}

if(root->data>=data)

{

root->left=insert(root->left,data,balance);

if(*balance==0)

{

switch(root->factor)

{

case AVL_LEFT_HEAVY:

root=roate_left(root);

*balance=1;

break;

case AVL_BALANCED:

root->factor=AVL_LEFT_HEAVY;

break;

case AVL_RIGHT_HEAVY:

root->factor=AVL_BALANCED;

*balance=1;

break;

}

else

{

root->right=insert(root->right,data,balance);

if(*balance==0)

{

switch(root->factor)

{

case AVL_LEFT_HEAVY:

root->factor=AVL_BALANCED;

*balance=1;

break;

case AVL_BALANCED:

root->factor=AVL_RIGHT_HEAVY;

break;

case AVL_RIGHT_HEAVY:

root=roate_right(root);

*balance=1;

break;

}

return root;

}

int main()

{

int n,i,temp,balance=0;

bistree *tree;

scanf("%d",&n);

tree=(bistree *)malloc(sizeof(bistree));

tree->root=NULL;

for(i=0;i<n;i++)

{

scanf("%d",&temp);

balance=0;

tree->root=insert(tree->root,temp,&balance);

}

printf("%d\n",tree->root->data);

}

Lnyan's Blog

Stand out to be outstanding

PAT-Advanced-1066. Root of AVL Tree

2 评论

发表评论取消回复

2 评论

发表评论 取消回复

发表评论取消回复