Can not insert nodes in an AVL Tree properly

Question

Can someone please help me with AVL Trees, I think I'm doing it wrong when computing the new balance in rotationRightLeft function. I'm not allowed to use max function so I'm trying this method..

template <class T>
void ArbreAVL<T>::insert(const T & e) {
    bool Issuccess = insert(racine, e);
    std::cout << e << " : "<< Issuccess << std::endl;
    std::cout.flush();
}

template <class T>
bool ArbreAVL<T>::insert(Node*& node, const T & e) {
    if(node== nullptr){
        node= new Node(e);
        return true;
    }
    if(e < node->content){
        if(insert(node->left, e)){
            node->balance++;
            
            if(node->balance== 0)
                return false;
            if(node->balance == 1)
                return true;
            assert(node->balance == 2);
            if(node->left->balance== -1)
                rotationRightLeft(node->left);
            rotationLeftRight(node);
        }
        return false;    
    }else if(e > node->content){
        if(insert(node->right, e)){
            node->balance++;
            
            if(node->balance == 0)
                return false;
            if(node->balance == -1)
                return true;
            assert(node->balance == -2);
            if(node->right->balance== 1)
                rotationLeftRight(node->right);
            rotationRightLeft(node);
        }
        return false;
    }else{
        node->content= e;
        return false;
    }
}

template <class T>
void ArbreAVL<T>::rotationRightLeft(Node*& rootChildTree) {
    Node* a = rootChildTree->right;
    Node* b = rootChildTree;
    int ea = a->balance;
    int eb = b->balance;
    
    int eap = - (eb < 0 ? eb : 0) - 1 + ea;
    int ebp = eb + (eap > 0 ? eap : 0) - 1;
    
    a->balance= eap;
    b->balance= ebp;
    b->right= a->left;
    a->left= b;
    rootChildTree= a;
}

I tested the insert method and here's the output. Can someone please tell me what's wrong with the balance computation. It seems to be working in the rotationLeftRight method since the node with the element 2 is inserted to the left of the node with element 4 (see the output image)

Computation I used in rotationLeftRight function :

int ebp = - (ea > 0 ? ea : 0) - 1 + eb;
int eap = ea + (ebp < 0 ? ebp : 0) - 1;

#include <iostream>
#include "arbreavl.h"

int main() {
    std::cout << "Test #1" << std::endl;
    int error= 0;
    ArbreAVL<int> A;
    A.insert(4);
    A.insert(2);
    A.insert(6);
    A.insert(1);
    A.insert(3);
    A.insert(5);
    A.insert(7);
    A.print();
    std::cout << A.size() << std::endl;
    if(A.size() != 7) {
        std::cerr << "ERROR- I" << std::endl;
        error++;
    }
    if(error == 0)
        std::cout << "\t==> OK"<< std::endl;
    return error;
}

output

Answer 1

Learning algorithms on the example of AVL trees is an interesting task.

Talking about existing code:
In your method insert(Node*& node, const T& e) there is an error in if: if(condition){} else if(the same condition). Also, the very operations that take place in the bodies of conditions look like failed copying from another if (++ instead of --, etc.).

Regarding the turnover functions, as far as I understand, they do not work at all. To turn, you have to change the value of the root and its children in a way, that will make the maximum death of left and right child equal(or rather their difference shouldn't be greater than 1). Simply changing the value of the balance will not work. More details about how to balance an AVL tree are described here on SO or on en.wikipedia.

Generally, your right turn should follow the next algorithm:

1. get your turn point(root), left son(left), right son(right) and right son of the left(grandson)
2. you make your left your new root
3. your old root become your new right(so it is now right son of old left)
4. your old grandson becomes new left child of your old root(so new left child of new right child of root)
5. chill

In code it will be something similar to this

void turnRight(Node*& root, Node* left, Node* right, Node* grandson)
{
    Node* old_root = root;
    root = left;
    left->right = old_root;
    old_root->left = grandson
}
turnRight(root, root->left, root->right, root->left->right);