RosettaCodeData/Task/AVL-tree/FreeBASIC/avl-tree-1.basic

#define max(a, b) iif((a > b), a, b)

Enum
    _KEY
    _RIGHT
    _LEFT
    _HEIGHT
End Enum

Dim Shared As Integer root = 0
Dim Shared As Integer ramas = 5, indice = 0
Dim Shared As Integer arbol(ramas, 4)

Function height(current As Integer) As Integer
    Return Iif(current = 0, 0, arbol(current, _HEIGHT))
End Function

Function Balance(current As Integer) As Integer
    Return height(arbol(current, _LEFT)) - height(arbol(current, _RIGHT))
End Function

Function rotateRight(y As Integer) As Integer
    Dim As Integer x, T2

    x = arbol(y, _LEFT)
    T2 = arbol(x, _RIGHT)
    arbol(x, _RIGHT) = y
    arbol(y, _LEFT) = T2
    arbol(y, _HEIGHT) = max(height(arbol(y, _LEFT)), height(arbol(y, _RIGHT))) + 1
    arbol(x, _HEIGHT) = max(height(arbol(x, _LEFT)), height(arbol(x, _RIGHT))) + 1
    Return x
End Function

Function rotateLeft(x As Integer) As Integer
    Dim As Integer y, T2

    y = arbol(x, _RIGHT)
    T2 = arbol(y, _LEFT)
    arbol(y, _LEFT) = x
    arbol(x, _RIGHT) = T2
    arbol(x, _HEIGHT) = max(height(arbol(x, _LEFT)), height(arbol(x, _RIGHT))) + 1
    arbol(y, _HEIGHT) = max(height(arbol(y, _LEFT)), height(arbol(y, _RIGHT))) + 1
    Return y
End Function

Function insert(current As Integer, key As Integer) As Integer
    Dim As Integer balanceo

    If current = 0 Then
        indice += 1
        If indice > ramas Then
            ramas += 5
            Redim Preserve arbol(ramas, 4)
        End If
        arbol(indice, _KEY) = key
        arbol(indice, _HEIGHT) = 1
        Return indice
    End If

    If key < arbol(current, _KEY) Then
        arbol(current, _LEFT) = insert(arbol(current, _LEFT), key)
    Elseif key > arbol(current, _KEY) Then
        arbol(current, _RIGHT) = insert(arbol(current, _RIGHT), key)
    Else
        Return current
    End If

    arbol(current, _HEIGHT) = max(height(arbol(current, _LEFT)), height(arbol(current, _RIGHT))) + 1
    balanceo = Balance(current)

    If balanceo > 1  And key < arbol(arbol(current, _LEFT), _KEY) Then Return rotateRight(current)
    If balanceo < -1 And key > arbol(arbol(current, _RIGHT), _KEY) Then Return rotateLeft(current)
    If balanceo > 1  And key > arbol(arbol(current, _LEFT), _KEY) Then
        arbol(current, _LEFT) = rotateLeft(arbol(current, _LEFT))
        Return rotateRight(current)
    End If
    If balanceo < -1 And key < arbol(arbol(current, _RIGHT), _KEY) Then
        arbol(current, _RIGHT) = rotateRight(arbol(current, _RIGHT))
        Return rotateLeft(current)
    End If

    Return current
End Function

Function minValueNode(current As Integer) As Integer
    While arbol(current, _LEFT) '<> 0
        current = arbol(current, _LEFT)
    Wend
    Return current
End Function

Function deleteNode(root As Integer, key As Integer) As Integer
    Dim As Integer temp, balanceo
    ' Find the node and delete it
    If root = 0 Then Return root

    If key < arbol(root, _KEY) Then
        arbol(root, _LEFT) = deleteNode(arbol(root, _LEFT), key)
    Elseif key > arbol(root, _KEY) Then
        arbol(root, _RIGHT) = deleteNode(arbol(root, _RIGHT), key)
    Else
        If arbol(root, _LEFT) = 0 Or arbol(root, _RIGHT) = 0 Then
            temp = max(arbol(root, _LEFT), arbol(root, _RIGHT))
            If temp = 0 Then
                temp = root
                root = 0
            Else
                root = temp
            End If
        Else
            temp = minValueNode(arbol(root, _RIGHT))
            arbol(root, _KEY) = arbol(temp, _KEY)
            arbol(root, _RIGHT) = deleteNode(arbol(root, _RIGHT), arbol(temp, _KEY))
        End If
    End If

    If root = 0 Then Return root

    ' Update the balance factor of each node and balance the tree
    arbol(root, _HEIGHT) = 1 + max(height(arbol(root, _LEFT)), height(arbol(root, _RIGHT)))

    balanceo = Balance(root)
    If balanceo > 1 And Balance(arbol(root, _LEFT)) >= 0 Then Return rotateRight(root)
    If balanceo > 1 And Balance(arbol(root, _LEFT)) < 0  Then
        arbol(root, _LEFT) = rotateLeft(arbol(root, _LEFT))
        Return rotateRight(root)
    End If
    If balanceo < -1 And Balance(arbol(root, _RIGHT)) <= 0 Then Return rotateLeft(root)
    If balanceo < -1 And Balance(arbol(root, _RIGHT)) > 0  Then
        arbol(root, _RIGHT) = rotateRight(arbol(root, _RIGHT))
        Return rotateLeft(root)
    End If

    Return root
End Function

Sub preOrder(temp As Integer)
    If temp <> 0 Then
        Print arbol(temp, _KEY); arbol(temp, _HEIGHT); Balance(temp)
        preOrder(arbol(temp, _LEFT))
        preOrder(arbol(temp, _RIGHT))
    End If
End Sub

root = insert(root, 2)
root = insert(root, 1)
root = insert(root, 7)
root = insert(root, 4)
root = insert(root, 5)
root = insert(root, 3)
root = insert(root, 8)

preOrder(root)

root = deleteNode(root, 3)

Print !"\nAfter deletion: "
preOrder(root)

Sleep