04-树4. 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 <iostream>
using namespace std;

struct BinNode
{
    int val;
    int height;
    BinNode *left, *right;
    BinNode(int val) : val(val), left(NULL), right(NULL) {};
};

const int MAX_SIZE = 20;
class AVL
{
public:
    AVL(int N);
    ~AVL();
    void Insert(int val);                       //外部调用接口
    void ReleaseAVL(BinNode *bn);               //释放内存
    void InsertBST(BinNode *&bn, int val);      //构造BST树(binary search tree)
    BinNode *InsertAVL(BinNode *bn, int val);   //构造AVL树
    int GetH(BinNode *bn);                      //计算高度的内部实现
    int GetHeight(int val);                     //计算值=val的结点的高度，外部接口，供用户调用
    BinNode *FindNode(BinNode *bn, int val);    //寻找值=val的结点
    bool IsEmpty(BinNode *bn);  //判断结点是否为空
    BinNode *RR(BinNode *bn);   //RR旋转
    BinNode *RL(BinNode *bn);   //RL旋转
    BinNode *LL(BinNode *bn);   //LL旋转
    BinNode *LR(BinNode *bn);   //LR旋转
    void LevelOrder();          //层次遍历外部接口，供用户调用
    void LevelOrderTraserval(BinNode *bn);  //层次遍历内部实现
    void printRoot();
private:
    BinNode *root;
};

AVL::AVL(int N)
{
    root = NULL;
    for(int i = 0; i < N; ++i)
    {
        int inputVal = 0;
        cin >> inputVal;
        Insert(inputVal);
    }
}

AVL::~AVL()
{
    ReleaseAVL(root);
}

void AVL::ReleaseAVL(BinNode *bn)
{
 //   static int i = 0, j = 0;
    if(bn != NULL)
    {

        ReleaseAVL(bn->left);
        ReleaseAVL(bn->right);
//                cout << "xigou " << i++ << " " << endl;
        delete bn;
    }
    //递归调用不return函数在执行到结尾时，会自动return；
}


void AVL::Insert(int val)
{
    root = InsertAVL(root,val);
//    InsertBST(root,val);
}
void AVL::InsertBST(BinNode *&bn, int val)
{
    if(bn == NULL)
    {
        bn = new BinNode(val);
    }
    else if(val > bn->val)
    {
        InsertAVL(bn->right, val);
    }
    else if(val < bn->val)
    {
        InsertAVL(bn->left, val);
    }
    else
    {
        cout << "duplicated element" << endl;
    }
}

BinNode *AVL::InsertAVL(BinNode *bn, int val)
{
    if(bn == NULL)
    {
        bn = new BinNode(val);
 //       return bn;
    }
    else if(bn->val > val)
    {
        bn->left = InsertAVL(bn->left, val);
        if(GetH(bn->left) - GetH(bn->right) == 2)
        {
            if(val < bn->left->val)
            {
                bn = LL(bn);
            }
            else //if(val > bn->left->val)
            {
                bn = LR(bn);
            }
        }
    }
    else if(bn->val < val)
    {
        bn->right = InsertAVL(bn->right, val);
        if(GetH(bn->left) - GetH(bn->right) == -2)
        {
            if(val < bn->right->val)
            {
                bn = RL(bn);
            }
            else //if(val > bn->right->val)
            {
                bn = RR(bn);
            }
        }
    }
    bn->height = max(GetH(bn->left), GetH(bn->right)) + 1;
    return bn;
}



BinNode *AVL::RR(BinNode *bn)
{
    BinNode *B = bn->right;
    bn->right = B->left;
    B->left = bn;
    bn->height = max(GetH(bn->left), GetH(bn->right)) + 1;
    B->height = max(bn->height,GetH(B->right)) + 1;

    return B;
}

BinNode *AVL::RL(BinNode *bn)
{
//    BinNode *B = bn->right;     //bn 为发现者结点
//    BinNode *C = B->left;       //C 破坏者结点
//    bn->right = C->left;
//    B->left = C->right;
//    C->left = bn;
//    C->right = B;
//    B->height = max(GetH(B->left), GetH(B->right)) + 1;
//    C->height = max(GetH(bn), GetH(B)) + 1;
//    bn->height = max(GetH(bn->left), GetH(bn->right)) + 1;
//    return C;

    //分析可知，RL旋转其实可以转换成LL旋转和RR旋转，代码如下
    bn->right = LL(bn->right);      //B和C做LL旋转
    return RR(bn);           //A和C做RR旋转，返回C
}

BinNode *AVL::LL(BinNode *bn)
{
    BinNode *B = bn->left;
    bn->left = B->right;
    B->right = bn;
    bn->height = max(GetH(bn->left), GetH(bn->right)) + 1;
    B->height = max(GetH(B->left), bn->height) + 1;
    return B;
}

BinNode *AVL::LR(BinNode *bn)
{
//    BinNode *B = bn->left;
//    BinNode *C = B->right;
//    B->right = C->left;
//    bn->left = C->right;
//    C->left = B;
//    C->right = bn;
//    bn->height = max(GetH(bn->left), GetH(bn->right)) + 1;
//    B->height = max(GetH(B->left), GetH(B->right)) + 1;
//    C->height = max(GetH(B), GetH(bn)) + 1;
//    return C;
    //同样的，LR旋转可以转换成RR旋转和LL旋转，代码如下
    bn->left = RR(bn->left);
    return LL(bn);
}

void AVL::LevelOrderTraserval(BinNode *bn)
{
    if(bn == NULL)
    {
        return;
    }
    BinNode *tmp, *Q[20];
    int rear = -1, front = -1;
    Q[++rear] = bn;
    while(rear != front)
    {
        tmp = Q[++front];
        cout << "val is: " << tmp->val << endl;//<<" height is " << tmp->height << endl;
        if(tmp->left != NULL)
        {
            Q[++rear] = tmp->left;
        }
        if(tmp->right != NULL)
        {
            Q[++rear] = tmp->right;
        }
    }
}
void AVL::LevelOrder()
{
    LevelOrderTraserval(root);
}

bool AVL::IsEmpty(BinNode *bn)
{
    if(bn == NULL)
    {
        return true;
    }
    return false;
}
BinNode *AVL::FindNode(BinNode *bn, int val)
{
    if(bn->val == val)
    {
        return bn;
    }
    else if(bn->val < val)
    {
        if(bn->right != NULL)
        {
            FindNode(bn->right, val);
        }
        else
        {
            return NULL;
        }

    }
    else
    {
        if(bn->left != NULL)
        {
            FindNode(bn->left, val);
        }
        else
        {
            return NULL;
        }
    }
}
int AVL::GetHeight(int val)
{
    BinNode *dst = FindNode(root, val);
    if(dst != NULL)
    {
        return GetH(dst);
    }
    else
    {
        cout << "No element : " << val << endl;
        return -1;
    }

}
int AVL::GetH(BinNode *bn)
{
    if(bn != NULL)
    {
        return max(1 + GetH(bn->left), 1 + GetH(bn->right));
    }
    else
    {
        return -1;
    }
}

void AVL::printRoot()
{
    cout << root->val << endl;
}
int main(){


    int N = 0;      //the number of nodes
    cin >> N;
    AVL AvlTree(N);
    AvlTree.printRoot();
//    AvlTree.LevelOrder();
//    cout << AvlTree.GetHeight(5);
    return 0;
}

在我原有代码基础上加了个printRoot(),其他的懒得改了，就放上面没去了。又是一个放pat上测试一遍通过的，不过在放pat测试之前自己电脑上调了很久。源代码