1066. Root of AVL Tree.md

pat 甲级 1066 Root of AVL Tree

题意概述

向 AVL 树插入多个关键字，给出最终得到的 AVL 树的根。

输入输出格式

输入第一行都包含一个正整数 N，它是要插入的关键字的总数。然后在下一行中给出 N 个不同的整数键。一行中的所有数字都用空格分隔。

在一行中打印 AVL 树的根。

数据规模

$$N<=20$$

算法设计

AVL 树的代码模板可见AVL 树代码模板

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
//与根结点数据域相等时，一律插入到右子树
struct AVLTreeNode {
    gg data, height, num;  //关键字、高度
    AVLTreeNode *left, *right;
    AVLTreeNode(gg v, AVLTreeNode* l = nullptr, AVLTreeNode* r = nullptr,
                gg h = 0) :
        data(v),
        height(h), left(l), right(r) {}
};
gg getHeight(AVLTreeNode* r) { return r ? r->height : 0; }
AVLTreeNode* findAVL(AVLTreeNode* root, gg data) {
    if (not root or root->data == data) {
        return root;
    } else if (data < root->data) {
        return findAVL(root->left, data);
    } else {
        return findAVL(root->right, data);
    }
}
// LL：左左对应的情况(左单旋转),返回旋转后的根节点
AVLTreeNode* leftLeftRotation(AVLTreeNode* k2) {
    AVLTreeNode* k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2->height = max(getHeight(k2->left), getHeight(k2->right)) + 1;
    k1->height = max(getHeight(k1->left), k2->height) + 1;
    return k1;
}
// RR：右右对应的情况(右单旋转),返回旋转后的根节点
AVLTreeNode* rightRightRotation(AVLTreeNode* k1) {
    AVLTreeNode* k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1->height = max(getHeight(k1->left), getHeight(k1->right)) + 1;
    k2->height = max(getHeight(k2->right), k1->height) + 1;
    return k2;
}
// LR：左右对应的情况(左双旋转),返回旋转后的根节点
AVLTreeNode* leftRightRotation(AVLTreeNode* k3) {
    k3->left = rightRightRotation(k3->left);
    return leftLeftRotation(k3);
}
// RL：右左对应的情况(右双旋转),返回旋转后的根节点
AVLTreeNode* rightLeftRotation(AVLTreeNode* k1) {
    k1->right = leftLeftRotation(k1->right);
    return rightRightRotation(k1);
}
//将结点插入到AVL树中，并返回根节点
AVLTreeNode* insertNode(AVLTreeNode*& root, gg data) {
    if (not root) {
        root = new AVLTreeNode(data);
    } else if (data < root->data) {
        root->left = insertNode(root->left, data);
        // 插入节点后，若AVL树失去平衡，则进行相应的调节。
        if (getHeight(root->left) - getHeight(root->right) == 2) {
            if (data < root->left->data) {
                root = leftLeftRotation(root);
            } else {
                root = leftRightRotation(root);
            }
        }
    } else {  // 应该将data插入到"root的右子树"的情况
        root->right = insertNode(root->right, data);
        // 插入节点后，若AVL树失去平衡，则进行相应的调节。
        if (getHeight(root->right) - getHeight(root->left) == 2) {
            if (data > root->right->data) {
                root = rightRightRotation(root);
            } else {
                root = rightLeftRotation(root);
            }
        }
    }
    root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
    return root;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, ai;
    cin >> ni;
    AVLTreeNode* root = nullptr;
    while (ni--) {
        cin >> ai;
        root = insertNode(root, ai);
    }
    cout << root->data;
    return 0;
}