C++ AVL树失衡旋转问题

#include<iostream>
#include<sstream>
#include <string>
#include <algorithm>
using namespace std;

//create AVL tree
class Anode {
    //for save data and height

    int a;

    int h;

    //the leaves of right and left

    struct Anode* leftleaf;

    struct Anode* rightleaf;

    //max value function

    int MaxValue(int a, int b);

    //gain hight function
    int Gheight(Anode* node);

    //to get the balance of node

    int getbalance(Anode* BL);

    //min value function

    Anode* MinValue(Anode* node);

    //creat a new node to the AVL function
    Anode* newNode(int val);
    //
    Anode* Rrotate(Anode* tp);

    Anode* Lrotate(Anode* tp);


public:

    //create a function to add and delete a node

    Anode* addNode(Anode* node, int val);

    //the value is in the root

    Anode* delNode(Anode* root, int val);

    //print the tree by order in before and after form function

    void beforder(Anode* root);

    void aftorder(Anode* root);
    //order function
    void order(Anode* root);
};
//overload all of those function
// 
// get max value of Node funtion

int Anode::MaxValue(int a, int b) {
    return(a > b) ? a : b;
}
//get height of tree function
int Anode::Gheight(Anode* node) {
    //check the node whether is null , if so ,return 0
    if (node == NULL)
        return 0;
    return node->h;
}
Anode* Anode::newNode(int val) {
    Anode* node = new Anode;
    node->a = val;
    node->leftleaf = NULL;
    node->rightleaf = NULL;
    //becaue the new node has been added the height of tree needs to be changed
    node->h = 1;
    return(node);
}
//avl tree for rotation (left and right)
Anode* Anode::Rrotate(Anode* tp) {
    Anode* newRoot = tp->leftleaf;

    Anode* tp2 = newRoot->rightleaf;

    newRoot->rightleaf = tp;

    tp->leftleaf = tp2;

    //because the node has been changed, the height of tree needs to be changed
    tp->h = max(Gheight(tp->leftleaf), Gheight(tp->rightleaf)) + 1;

    newRoot->h = max(Gheight(newRoot->leftleaf), Gheight(newRoot->rightleaf)) + 1;

    return newRoot;
}
//familiar with Rrotate function
Anode* Anode::Lrotate(Anode* tp) {

    Anode* newRoot = tp->rightleaf;

    Anode* tp2 = newRoot->leftleaf;

    newRoot->leftleaf = tp;

    tp->rightleaf = tp2;

    tp->h = max(Gheight(tp->leftleaf), Gheight(tp->rightleaf)) + 1;

    newRoot->h = max(Gheight(newRoot->leftleaf), Gheight(newRoot->rightleaf)) + 1;

    return newRoot;
}

//get balance of node funciton
int Anode::getbalance(Anode* BL) {
    if (BL == NULL)
        return 0;
    //else return the balance of leftleaf and right rightleaf
    return Gheight(BL->leftleaf) - Gheight(BL->rightleaf);
}
//add a node function
Anode* Anode::addNode(Anode* node, int val) {
    if (node == NULL)

        return(newNode(val));

    if (val < node->a)

        node->leftleaf = addNode(node->leftleaf, val);

    else if (val > node->a)

        node->rightleaf = addNode(node->rightleaf, val);
    else

        return node;

    //because the node has been changed, the height of tree needs to be changed
    node->h = 1 + max(Gheight(node->leftleaf), Gheight(node->rightleaf));

    int bal = getbalance(node);

    if (bal > 1 && val < node->leftleaf->a)

        return Rrotate(node);

    if (bal < -1 && val > node->rightleaf->a)

        return Lrotate(node);

    if (bal > 1 && val > node->leftleaf->a) {

        node->leftleaf = Lrotate(node->leftleaf);

        return Rrotate(node);
    }
    if (bal < -1 && val < node->rightleaf->a) {

        node->rightleaf = Rrotate(node->rightleaf);

        return Lrotate(node);
    }
    return node;
}
Anode* Anode::MinValue(Anode* node) {
    Anode* M = node;
    while (M->leftleaf != NULL)
        M = M->leftleaf;
    return M;
}
Anode* Anode::delNode(Anode* root, int val) {
    if (root == NULL)
        return root;
    if (val < root->a)
        //recursion
        root->leftleaf = delNode(root->leftleaf, val);
    else if (val > root->a)
        //recursion
        root->rightleaf = delNode(root->rightleaf, val);
    else {
        if ((root->leftleaf == NULL) || (root->rightleaf == NULL)) {
            Anode* tp = root->leftleaf ? root->leftleaf : root->rightleaf;
            if (tp == NULL) {
                tp = root;
                root = NULL;
            }
            else
                *root = *tp;
            free(tp);
        }
        else {
            Anode* tp = MinValue(root->rightleaf);
            root->a = tp->a;
            root->rightleaf = delNode(root->rightleaf, tp->a);
        }
    }
    if (root == NULL)
        return root;
    root->h = 1 + max(Gheight(root->leftleaf), Gheight(root->rightleaf));

    int bal = getbalance(root);

    if (bal > 1 && getbalance(root->leftleaf) >= 0)

        return Rrotate(root);

    if (bal > 1 && getbalance(root->leftleaf) < 0) {

        root->leftleaf = Lrotate(root->leftleaf);

        return Rrotate(root);

    }
    if (bal < -1 && getbalance(root->rightleaf) <= 0)

        return Lrotate(root);

    if (bal < -1 && getbalance(root->rightleaf) > 0) {

        root->rightleaf = Rrotate(root->rightleaf);

        return Lrotate(root);
    }

    return root;
}
void Anode::beforder(Anode* root) {
    if (root != NULL) {

        cout << root->a << " ";

        beforder(root->leftleaf);

        beforder(root->rightleaf);

    }

}
void Anode::aftorder(Anode* root) {

    if (root != NULL) {

        aftorder(root->leftleaf);

        aftorder(root->rightleaf);

        cout << root->a << " ";
    }
}

void Anode::order(Anode* root) {

    if (root != NULL) {

        order(root->leftleaf);

        cout << root->a << " ";

        order(root->rightleaf);

    }
}

int main() {
    Anode* root = NULL;
    int i = 0;
    int    j = -1;
    char a[1000];
    int tp = 0;
    cin.getline(a, 1000);
    for (i = 0; a[i] != '\0'; i++) {
        j++;
        if (a[i] == ' ') {
            if (a[i - j] == 'A') {
                j--;
                while (j > 0) {
                    tp = tp * 10 + (a[i - j] - '0');
                    j--;
                }
                root = root->addNode(root, tp);
            }
            else if (a[i - j] == 'D') {
                j--;
                while (j > 0) {
                    tp = tp * 10 + (a[i - j] - '0');
                    j--;
                }
                root = root->delNode(root, tp);
            }
            j = -1;
            tp = 0;
        }
        else {
            if (a[i] == 'E') {
                root->beforder(root);
            }
            else if (a[i] == 'T') {
                root->aftorder(root);
            }
            else if (a[i] == 'N') {
                root->order(root);
            }
        }
    }
    if (root == NULL) {
        cout << "EMPTY";
    }
}

代码有时候是对的 但遇到如下情况就得不到正确的结果

输入 A88 D77 D95 A78 A71 A2 D9 A2 A60 D80 A85 A65 D11 A30 D8 A68 D87 A28 A88 A96 D29 D26 D88 D47 D68 A65 A86 A100 A61 D7 D76 D21 D24 A40 D94 A84 A16 D28 A45 A60 D34 D14 A68 A64 A74 A62 D99 D2 D34 D32 D60 D52 D19 A95 A28 A91 D24 A34 D22 D77 D7 D78 A3 A100 D95 D53 D82 D64 A55 A46 A17 A70 D4 A25 A75 D71 A30 D50 D44 A11 D39 A47 D77 A71 D1 A98 D51 A63 D15 A15 D75 A4 D14 D77 A9 D84 D70 A5 D67 A22 POST

得到的结果为：
3 5 4 15 11 9 22 17 28 25 16 34 45 40 47 55 46 30 62 65 63 74 71 68 91 86 98 100 96 85 61
正确的结果为：
3 5 4 15 11 9 22 17 28 25 16 34 40 46 55 47 63 62 61 45 30 71 68 85 74 91 98 100 96 86 65

请问我需要修改哪一块的代码呢？ 具体怎么修改？

插入65的时候没有考虑旋转，绿色的部分，导致左右子树深度相差2了。

我看了一下 ，你的运行结果3 5 4 15 11 9 22 17 28 25 16 34 45 40 47 55 46 30 62 65 63 74 71 68 91 86 98 100 96 85 61
没有什么问题呀！保证了avl树的平衡。

基本上没有问题，我在我的Devc++Devc++上运行结果为3 5 4 15 11 9 22 17 28 25 16 34 45 40 47 55 46 30 62 65 63 74 71 68 91 86 98 100 96 85 61。