// AVL-Tree C code, https://www.programiz.com/dsa/avl-tree
// Ported to Yabasic by Galileo 2022/07

KEY = 1 : LRIGHT = 2 : LLEFT = 3 : HEIGHT = 4

root = 0 : ramas = 5 : indice = 0

dim arbol(ramas, 4)


sub rotateRight(y)
    local x, T2

    x = arbol(y, LLEFT)
    T2 = arbol(x, LRIGHT)
    arbol(x, LRIGHT) = y
    arbol(y, LLEFT) = T2
    arbol(y, HEIGHT) = max(height(arbol(y, LLEFT)), height(arbol(y, LRIGHT))) + 1
    arbol(x, HEIGHT) = max(height(arbol(x, LLEFT)), height(arbol(x, LRIGHT))) + 1
    return x
end sub


sub rotateLeft(x)
    local y, T2

    y = arbol(x, LRIGHT)
    T2 = arbol(y, LLEFT)
    arbol(y, LLEFT) = x
    arbol(x, LRIGHT) = T2
    arbol(x, HEIGHT) = max(height(arbol(x, LLEFT)), height(arbol(x, LRIGHT))) + 1
    arbol(y, HEIGHT) = max(height(arbol(y, LLEFT)), height(arbol(y, LRIGHT))) + 1
    return y
end sub


sub Balance(current)
    return height(arbol(current, LLEFT)) - height(arbol(current, LRIGHT))
end sub


sub height(current)
    return arbol(current, HEIGHT)
end sub


sub insert(current, key)
    local balance

    if current = 0 indice = indice + 1 : if indice > ramas then ramas = ramas + 5 : redim arbol(ramas, 4) endif : arbol(indice, KEY) = key : arbol(indice, HEIGHT) = 1 : return indice
    if key < arbol(current, KEY) then
        arbol(current, LLEFT) = insert(arbol(current, LLEFT), key)
    elsif key > arbol(current, KEY) then
        arbol(current, LRIGHT) = insert(arbol(current, LRIGHT), key)
    else
        return current
    endif

    arbol(current, HEIGHT) = max(height(arbol(current, LLEFT)), height(arbol(current, LRIGHT))) + 1
    balance = Balance(current)
    if balance > 1 and key < arbol(arbol(current, LLEFT), KEY) return rotateRight(current)
    if balance < -1 and key > arbol(arbol(current, LRIGHT), KEY) return rotateLeft(current)
    if balance > 1 and key > arbol(arbol(current, LLEFT), KEY) then
        arbol(current, LLEFT) = rotateLeft(arbol(current, LLEFT))
        return rotateRight(current)
    endif
    if balance < -1 and key < arbol(arbol(current, LRIGHT), KEY) then
        arbol(current, LRIGHT) = rotateRight(arbol(current, LRIGHT))
        return rotateLeft(current)
    endif
    return current
end sub


sub minValueNode(current)
  while arbol(current, LLEFT)
    current = arbol(current, LLEFT)
  wend

  return current
end sub

// Delete a nodes
sub deleteNode(root, key)
    local temp, balance
  // Find the node and delete it
  if root = 0 return root

  if key < arbol(root, KEY) then
    arbol(root, LLEFT) = deleteNode(arbol(root, LLEFT), key)
  elsif key > arbol(root, KEY) then
    arbol(root, LRIGHT) = deleteNode(arbol(root, LRIGHT), key)
  else
    if arbol(root, LLEFT) = 0 or arbol(root, LRIGHT) = 0 then
      temp = max(arbol(root, LLEFT), arbol(root, LRIGHT))

      if temp = 0 then
        temp = root
        root = 0
      else
        root = temp
      endif
    else
      temp = minValueNode(arbol(root, LRIGHT))
      arbol(root, KEY) = arbol(temp, KEY)
      arbol(root, LRIGHT) = deleteNode(arbol(root, LRIGHT), arbol(temp, KEY))
    endif
  endif

  if root = 0 return root

  // Update the balance factor of each node and
  // balance the tree
  arbol(root, HEIGHT) = 1 + max(height(arbol(root, LLEFT)), height(arbol(root, LRIGHT)))

  balance = Balance(root)
  if balance > 1 and Balance(arbol(root, LLEFT)) >= 0 return rightRotate(root)
  if balance > 1 and Balance(arbol(root, LLEFT)) < 0 arbol(root, LLEFT) = leftRotate(arbol(root, LLEFT)) : return rightRotate(root)
  if balance < -1 and Balance(arbol(root, LRIGHT)) <= 0 return leftRotate(root)
  if balance < -1 and Balance(arbol(root, LRIGHT)) > 0 arbol(root, LRIGHT) = rightRotate(arbol(root, LRIGHT)) : return leftRotate(root)

  return root
end sub

sub preOrder(temp)
    if temp then
        print arbol(temp, KEY), " ", arbol(temp, HEIGHT), " ", Balance(temp)
        preOrder(arbol(temp, LLEFT))
        preOrder(arbol(temp, LRIGHT))
    endif
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)