Mki's Blog

数据结构(五):平衡二叉树

题目描述

题目要求

04-树5 Root of AVL Tree (25 分)
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. Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

输入格式:

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.

输出格式:

For each test case, print the root of the resulting AVL tree in one line.

输入样例1:

5 88 70 61 96 120

输出样例1:

70

输入样例2:

7 88 70 61 96 120 90 65

输出样例2:

88

涉及的知识

基础

平衡二叉树,又名AVL树,顾名思义,是在二叉树的根本上添加“平衡”的属性,也就是说他不能一路左节点到底,也不能奇形怪状——它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。

旋转

但是,随着节点的增加,二叉树的节点难免会“失去平衡”,因此我们需要对这时的二叉树进行旋转,使其保持左右两个子树的高度差的绝对值不超过1。

那么,要如何旋转呢?

1.右单旋

如图,在A节点的右节点的右节点发生了失衡(添加的意思是在此处添加节点)。此时我们需要对树进行右单旋。 IMG_20180930_204409.jpg

2.左单旋

和前一个同理。 IMG_20180930_204147.jpg

3.右左单旋

如图,在A节点的左节点的右节点发生了失衡。这个时候要分两步操作,首先对B节点进行右单旋,再对A节点进行左单旋。 IMG_20180930_205853.jpg

4.左右单旋

不给你图了,自己想,哼。其实是懒得画图。

旋转的代码实现

1.右单旋

AVLTree SingleRightRotation(AVLTree A) {
    AVLTree B = A->Right;
    A->Right = B->Left;
    B->Left = A;
    A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->Height = Max(GetHeight(B->Left), A->Height) + 1;

    return B;
}

2.左单旋

AVLTree SingleLeftRotation(AVLTree A) {
    AVLTree B = A->Left;
    A->Left = B->Right;
    B->Right = A;
    A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->Height = Max(GetHeight(B->Left), A->Height) + 1;

    return B;
}

3.右左单旋

AVLTree DoubleRightLeftRotation(AVLTree A) {
    A->Right = SingleLeftRotation(A->Right);
    return SingleRightRotation(A);
}

4.完整代码

#include<stdio.h>
#include<stdlib.h>
typedef int ElementType;
typedef struct AVLNode *Position;
typedef Position AVLTree;
struct AVLNode {
    ElementType Data;
    AVLTree Left;
    AVLTree Right;
    int Height;
};
/*比较最大值*/
int Max(int a, int b) {
    return a > b ? a : b;
}

/*获取树的高度*/
int GetHeight(AVLTree A) {
    if (A == NULL) {
        return -1;
    }
    else {
        int BLHeight = GetHeight(A->Left);
        int BRHeight = GetHeight(A->Right);
        if (BLHeight >= BRHeight) {
            return BLHeight + 1;
        }
        else {
            return BRHeight + 1;
        }
    }
}

/*左单旋*/
AVLTree SingleLeftRotation(AVLTree A) {
    AVLTree B = A->Left;
    A->Left = B->Right;
    B->Right = A;
    A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->Height = Max(GetHeight(B->Left), A->Height) + 1;

    return B;
}
/*右单旋*/
AVLTree SingleRightRotation(AVLTree A) {
    AVLTree B = A->Right;
    A->Right = B->Left;
    B->Left = A;
    A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
    B->Height = Max(GetHeight(B->Left), A->Height) + 1;

    return B;
}


/*左右单旋*/
AVLTree DoubleLeftRightRotation(AVLTree A) {
    A->Left = SingleRightRotation(A->Left);
    return SingleLeftRotation(A);
}


/*右左单旋*/
AVLTree DoubleRightLeftRotation(AVLTree A) {
    A->Right = SingleLeftRotation(A->Right);
    return SingleRightRotation(A);
}


/*添加节点*/
AVLTree Insert(AVLTree T, ElementType X) {
    if (!T) {
        T = (AVLTree)malloc(sizeof(struct AVLNode));  //假如是个空的节点就把它变成树根
        T->Data = X;
        T->Height = 0;
        T->Left = T->Right = NULL;
    }
    else if (X < T->Data) {         //数值比树根小就插到左边去
        T->Left = Insert(T->Left, X);  //这里会递归插入,直到合适的位置
        if (GetHeight(T->Left) - GetHeight(T->Right) == 2) {  //判断是否失衡
            if (X < T->Left->Data)          //单边失衡
                T = SingleLeftRotation(T);
            else                            //左右失衡
                T = DoubleLeftRightRotation(T);
        }
    }
    else if (X > T->Data) {
        T->Right = Insert(T->Right, X);
        if (GetHeight(T->Left) - GetHeight(T->Right) == -2) { //这里-2是因为前面插到右边,所以自然是右边要深
            if (X > T->Right->Data)
                T = SingleRightRotation(T);
            else
                T = DoubleRightLeftRotation(T);
        }
    }

    T->Height = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;   
    return T;
}

int main() {
    int N, temp;
    scanf_s("%d", &N);
    AVLTree T = NULL;
    for (int i = 0; i < N; i++) {
        scanf_s("%d", &temp);
        T = Insert(T, temp);
    }
    printf("%d", T->Data);
    getchar();
}

写在最后

平衡二叉树这里的旋转,让我自己写肯定想不出来,和之前2048的转置一样,超级巧妙。
别人的代码写得又美又巧妙,我的代码。。。复杂晦涩。
要是什么时候也能写出很优美的代码就好了。
(垃圾小米居然自动给我手写的图美颜了。。。)