Q:

AVL tree how to balance tree on insert

I want to make a insert function for a avl tree. However the insert function has to be recursive and must be balanced.
I have a method to pivot the tree left PivoterAGauche and a method to pivot the tree right PivoterADroite. 
    'Pivot left
    Private Function PivoterAGauche(leNoeud As NoeudAVL) As NoeudAVL
        If leNoeud Is Nothing Then
            Return Nothing
        ElseIf leNoeud.FilsDroit Is Nothing AndAlso leNoeud.FilsGauche Is Nothing Then
            Return leNoeud
        ElseIf leNoeud.FilsDroit Is Nothing Then
            Return leNoeud
            ' ElseIf leNoeud.FilsGauche Is Nothing Then

        Else 'Le leNoeud.FilsGauche existe.
            Dim pivot As NoeudAVL = leNoeud.FilsGauche
            leNoeud.FilsGauche = pivot.FilsDroit
            pivot.FilsDroit = leNoeud
            leNoeud = pivot
            Return leNoeud
        End If
    End Function

    'pivot rigth
    Private Function PivoterADroite(leNoeud As NoeudAVL) As NoeudAVL
        If leNoeud Is Nothing Then
            Return Nothing
        ElseIf leNoeud.FilsDroit Is Nothing AndAlso leNoeud.FilsGauche Is Nothing Then
            Return leNoeud
        ElseIf leNoeud.FilsDroit Is Nothing Then
            Return leNoeud
            ' ElseIf leNoeud.FilsGauche Is Nothing Then

        Else 'Le leNoeud.FilsGauche existe.
            Dim pivot As NoeudAVL = leNoeud.FilsDroit
            leNoeud.FilsDroit = pivot.FilsGauche
            pivot.FilsGauche = leNoeud
            leNoeud = pivot
            Return leNoeud
        End If
    End Function

Here is the insert method I made. I am usure when to use the pivots left and rigth.
    Private Function Inserer(leElement As T, leNoeudCourant As NoeudAVL) As NoeudAVL

        Dim intBalance As Integer
        'If the node does not existes
        If leNoeudCourant Is Nothing Then
            m_blnOperationOK = True
            Return New NoeudAVL(leElement)
            'If the node already existes.
        ElseIf leElement.CompareTo(leNoeudCourant.Element) = 0 Then
            m_blnOperationOK = False
            Return leNoeudCourant
        ElseIf leElement.CompareTo(leNoeudCourant.Element) < 0 Then
            intBalance = Hauteur(leNoeudCourant.FilsGauche) - Hauteur(leNoeudCourant.FilsDroit)
            If (intBalance = 2) Then
                leNoeudCourant = PivoterAGauche(leNoeudCourant)
            End If
            leNoeudCourant.FilsGauche = Inserer(leElement, leNoeudCourant.FilsGauche)

        ElseIf leElement.CompareTo(leNoeudCourant.Element) > 0 Then
            intBalance = Hauteur(leNoeudCourant.FilsGauche) - Hauteur(leNoeudCourant.FilsDroit)
            If (intBalance = 2) Then
                leNoeudCourant = PivoterADroite(leNoeudCourant)
            End If
            leNoeudCourant.FilsDroit = Inserer(leElement, leNoeudCourant.FilsDroit)
        End If

        'Return current node that will become the root.
        Return leNoeudCourant

If you have more questions I will gladly answer your questions thank you for your help.

A:

Let's remember something very basic: when using recursion in a task like a binary tree, your workspace is one node. It means that this one node must own everything it needs to be able to do the task you want it to do.
You have to understand that, from it's own point of view, every node is the root of it's own tree, a little bit like if the whole binary tree was built of many many smaller binary trees. O node knows it's children, but not it's ancestors.
To be able to build a balanced binary tree, your nodes must be able to "know" these things:

Their height (how many nodes are underneath them).
If they are becoming unbalanced (when, under the currently evaluated node, both children have a height difference higher than 1 level).

The magic here is formidable: once implemented right, the binary tree will always keep it's balance without having to re-evaluate itself entirely. This is big brain time.
First, let's do the height thing:
Every node must have a height value. This value must be stored as a modal variable inside the node class. Make it a public property, because the node's parent will have to be able to access it.
Private _height As Integer = 0

Public ReadOnly Property Height As Integer
    Get
        Return _height
    End Get
End Property

When you insert the first node (the root), it's height is zero. There's nothing underneath. This is true for every new node you create.
When you insert another node, you usually "give" the value to be inserted to the root and let recursion do it's magic. Now there's something else to think about during this operation: update the height, and correct the balance.
Private Function insert(ByVal key As Integer, Optional node As Node = Nothing, ) As Node
    'if you are creating the root, node is nothing
    If (node Is Nothing) Then
        Return New Node(key)
    End If

    'creating new nodes when needed
    If (key < node.key) Then
        node.FilGauche = insert(key, node.FilGauche)
    ElseIf (key > node.key) Then
        node.FilDroit = insert(key, node.FilDroit)
    Else
        Return node
    End If

    're-evaluating height (accounting for null pointers) and then balancing the tree
    node._height = (1 + max(If(node.FilGauche.Height IsNot Nothing, node.FilGauche.Height, 0), node.FilDroit.Height IsNot Nothing, node.FilDroit.Height))
    Dim balance As Integer = If(node.FilGauche.Height IsNot Nothing, node.FilGauche.Height, 0) - If(node.FilDroit.Height IsNot Nothing, node.FilDroit.Height, 0)
    ' If this node becomes unbalanced, then there 
    ' are 4 cases Left Left Case 
    If ((balance > 1) AndAlso (key < node.FilGauche.key)) Then
        Return rightRotate(node)
    End If

    ' Right Right Case 
    If ((balance < -1) AndAlso (key > node.FilDroit.key)) Then
        Return leftRotate(node)
    End If

    ' Left Right Case 
    If ((balance > 1) AndAlso (key > node.FilGauche.key)) Then
        node.FilGauche = leftRotate(node.FilGauche)
        Return rightRotate(node)
    End If

    ' Right Left Case 
    If ((balance < -1) AndAlso (key < node.FilDroit.key)) Then
        node.FilDroit = rightRotate(node.FilDroit)
        Return leftRotate(node)
    End If

    Return node
End Function

Of course, you'll have to adapt these ideas to your exact situation, but that's not the only thing: I'm working from another langugage's references and out of IDE so I have to type directly into my browser, which means that I may have done some mistakes writing this. Let me know if this makes no sense and I'll double-check in better conditions. Good luck!

