2021秋季《数据结构》_EOJ 1071.平衡二叉树

题目

思路

搜到了template但已经忘了怎么用了…（好罪恶
照着书上的代码大概复原了一下

代码

#include<bits/stdc++.h>
using namespace std;int a[201] = {
     0 };typedef struct AVLTree
{
    int data;struct AVLTree* lchild;struct AVLTree* rchild;int height;
}AVLNode;int Height(AVLNode* root)
{
    if (!root)return -1;else return root->height;
}// LL
AVLNode* singleRotateWithLeft(AVLNode* k2)
{
    AVLNode* k1 = k2->lchild;k2->lchild = k1->rchild;k1->rchild = k2;k2->height = max(Height(k2->lchild), Height(k2->rchild)) + 1;k1->height = max(Height(k1->lchild), k2->height) + 1;return k1;
}// RR
AVLNode* singleRotateWithRight(AVLNode* k1)
{
    AVLNode* k2 = k1->rchild;k1->rchild = k2->lchild;k2->lchild = k1;k1->height = max(Height(k1->lchild), Height(k1->rchild)) + 1;k2->height = max(Height(k2->rchild), k1->height) + 1;return k2;
}// LR
AVLNode* doubleRotataWithLeft(AVLNode* k3)
{
    k3->lchild = singleRotateWithRight(k3->lchild);return singleRotateWithLeft(k3);
}// RL
AVLNode* doubleRotateWithRight(AVLNode* k1)
{
    k1->rchild = singleRotateWithLeft(k1->rchild);return singleRotateWithRight(k1);
}AVLNode* Insert(AVLNode* root, int x)
{
    if (!root){
    root = new AVLNode;root->data = x;root->height = 0;root->lchild = NULL;root->rchild = NULL;}else if (x < root->data){
    root->lchild = Insert(root->lchild, x);if (Height(root->lchild) - Height(root->rchild) == 2){
    if (x < root->lchild->data)root = singleRotateWithLeft(root);elseroot = doubleRotataWithLeft(root);}}else if (x > root->data){
    root->rchild = Insert(root->rchild, x);if (Height(root->rchild) - Height(root->lchild) == 2){
    if (x > root->rchild->data)root = singleRotateWithRight(root);elseroot = doubleRotateWithRight(root);}}root->height = max(Height(root->lchild), Height(root->rchild)) + 1;return root;
}AVLNode* buildAVL(int a[], int n)
{
    AVLNode* root = NULL;for (int i = 1; i <= n; i++){
    root = Insert(root, a[i]);}return root;
}int main()
{
    int n; cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];AVLNode* root = buildAVL(a, n);cout << root->data << ' ' << root->height + 1 << endl;return 0;
}