04 - 树 5. Root of AVL Tree - 平衡查

作者: 戏之地 | 来源:发表于2016-05-14 16:59 被阅读316次

04 - 树 5. Root of AVL Tree - 平衡查
04-树5 Root of AVL Tree（25 分）
平衡二叉树
平衡二叉搜索树
Swift 数据结构 - AVL树(AVL Tree)
数据结构与算法-平衡二叉树
Linux内核红黑树算法的实现详解（含实例源码）
AVL树
平衡二叉树简介
图的应用[平衡二叉树以及散列查找]

<pre>
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.
</pre>

1

2

3

4
<pre>
Now given a sequence of insertions,
you are supposed to tell the root of the resulting AVL tree.
</pre>
<pre>
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.
</pre>
<pre>
Output Specification:
For each test case,
print ythe root of the resulting AVL tree in one line.
</pre>
<pre>
Sample Input 1:
5
88 70 61 96 120
</pre>
<pre>
Sample Output 1:
70
</pre>
<pre>
Sample Input 2:
7
88 70 61 96 120 90 65
</pre>
<pre>
Sample Output 2:
88
</pre>
<pre>

include <stdio.h>

include <stdlib.h>

typedef struct TreeNode *AvlTree;
typedef struct TreeNode *Position;
struct TreeNode
{
int Data;
AvlTree Left;
AvlTree Right;
int Height;
};
AvlTree Insert(int x, AvlTree T);
//插入新节点，必要时调整
Position SingleRotateWithLeft(Position a);
//左单旋
Position SingleRotateWithRight(Position b);
//右单旋
Position DoubleRotateWithLeft(Position a);
//左右旋
Position DoubleRotateWithRight(Position b);
//右左旋
int Max(int x1, int x2);
//返回两个int中较大的
int Height(Position P);
//返回一个节点的高度
</pre>
<pre>
int main()
{
int n, x;
AvlTree T = NULL;

scanf("%d", &n);
for (int i = 0; i < n; i++)
{
    scanf("%d", &x);
    T = Insert(x, T);
}
printf("%d\n", T->Data);    //打印根节点的值

return 0;

}
</pre>
<pre>
AvlTree Insert(int x, AvlTree T)
{
if (T == NULL)
{
T = (AvlTree)malloc(sizeof(struct TreeNode));
T->Data = x;
T->Left = T->Right = NULL;
T->Height = 0;
}
else if (x < T->Data) //向左子树插入
{
T->Left = Insert(x, T->Left);
if (Height(T->Left) - Height(T->Right) == 2) //需调整
{
if (x < T->Left->Data)
T = SingleRotateWithLeft(T);
else
T = DoubleRotateWithLeft(T);
}
}
else if (x > T->Data) //向右子树插入
{
T->Right = Insert(x, T->Right);
if (Height(T->Right) - Height(T->Left) == 2) //需调整
{
if (x > T->Right->Data)
T = SingleRotateWithRight(T);
else
T = DoubleRotateWithRight(T);
}
}
/else值为x的节点已经存在树中，无需插入/

/*更新节点高度*/
T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
return T;

}
</pre>
<pre>
Position SingleRotateWithLeft(Position a)
{
Position b = a->Left;
a->Left = b->Right;
b->Right = a;
//更新a, b节点高度
a->Height = Max(Height(a->Left), Height(a->Right)) + 1;
b->Height = Max(Height(b->Left), Height(b->Right)) + 1;

return b;      /*新的根节点*/

}

Position SingleRotateWithRight(Position b)
{
Position a = b->Right;
b->Right = a->Left;
a->Left = b;
//更新a,b节点高度
a->Height = Max(Height(a->Left), Height(a->Right)) + 1;
b->Height = Max(Height(b->Left), Height(b->Right)) + 1;
return a; /新的根节点/
}
</pre>
<pre>
Position DoubleRotateWithLeft(Position a)
{
a->Left = SingleRotateWithRight(a->Left);
return SingleRotateWithLeft(a);
}

Position DoubleRotateWithRight(Position b)
{
b->Right = SingleRotateWithLeft(b->Right);
return SingleRotateWithRight(b);
}
</pre>
<pre>
int Max(int x1, int x2)
{
return (x1 > x2) ? x1 : x2;
}

int Height(Position P)
{
if (P == NULL) //空节点高度为-1
return -1;
return P->Height;
}
</pre>