A linguagem L

A linguagem L é descrita da seguinte maneira:

Aritmética:

Da forma usual: "x - 2 / (3 + y)" etc.

Tipos de dados

Há tres tipos de dados: número, string e estrutura. Números e strings podem ser comparados com <, > e =.

Estruturas e seus campos:

Use o ponto para acessar campos de uma estrutura: x.nome, x.chave, etc. Quando houver busca de conteúdo por chave, use x,chave e x.conteudo

Condicional:

Cada função pode ter um único comando condicional, que é semelhante a um switch:

	cond1: retorno1
	cond2: retorno2
	---  : retornoN

Neste caso, o retorno da função será retorno1 quando cond1 for verdade, cond2 quando retorno2 for verdade, etc. Quando nenhum dos casos for verdade, a função retornará retornoN.

Definição de funções:

nome: (parametro1, parametro2, ...)
	corpo da função

Chamada de funções: da maneira usual:

func(par1, par2)

Exemplos:

Por exemplo, a função que calcula o n-ésimo número de Fibonacci é:

fib (n):
	n=0:  0
	n=1:  1
	---:  fib (n-1) + fib (n-2)

A função que faz busca em árvore binária é:

busca (no, c):
	no = NULL   : FALHA
	c = no.chave: no.conteudo
	c < no.chave: busca (no.esq, c)
	c > no.chave: busca (no.dir, c)

A linguagem L é puramente funcional: ao invés de alterar estruturas, ela permite que uma função retorne uma noa estrutura, alterada. Por exemplo, posso escrever uma função remove(no,c) que remove um elemento de uma árvore. Esta função retornará uma nova árvore, sem o elemento removido. Assim, não há na lingaugem L atribuição de valores a variáveis.

A linguagem L, apesar de muito diferente de C, Java e outras linguagens populares, é Turing-equivalente (o que significa que tudo o que pode ser feito em um computador também pode ser feito em L, tanto quanto em outras linguagens).

O exercício

Descreva o algoritmo de inserção em árvores B na linguagem L.