Estou tentando resolver este problema em um judge online.
O problema fornece N inteiros que devem ser inseridos, na ordem dada, em um algoritmo de inserção de uma arvore binaria de busca. Depois Q consultas são realizadas. Para cada consulta o código deve dizer quem é o pai do elemento que é fornecido na entrada.
A entrada sera da seguinte forma:
N (quantidade de valores)
N1 N2 ... NN (Sao os valores que devem ser inseridos na arvore)
Q (a quantidade de consultas)
Q1 Q2 ... QQ (o inteiro que representa a posição do valor dado na entrada)
Para o seguinte exemplo de entrada seguindo a especificação acima:
5 3 1 4 2 5 2 2 5
O algoritmo deve formar a seguinte arvore:
E com essa arvore deve responder quem é o pai do segundo elemento dado na entrada (o pai de 1) e do 5 elemento da entrada (o pai de 5) separados por um espaço (não ha espaços apos o ultimo valor da saída)
Exemplo da saída esperada para a entrada do exemplo:
3 4
Para resolver esse problema usei o algoritmo trivial de inserção em arvores binarias (O que leva uma complexidade de pior caso de O(n2)). Durante a inserção, ja salvo o pai de cada nó em um mapa.
Mas, o código foi julgado como tempo limite excedido. Existe algum algoritmo de inserção mais rápido que o trivial (que mantenha a ordem dada na entrada ... arvores AVL vão alterar os pais de cada no...)?
#include <cstdio>
#include <cstdlib>
#include <unordered_map>
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
void insertAndBuildFather(node **tree, int data, std::unordered_map<int, int> &father){
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
struct node *root = *tree;
if(root == NULL){
root = tempNode;
father[root->data] = -1; //raiz nao tem pai
*tree = root;
return;
}
struct node *current = root;
struct node *parent = NULL;
while(1){
parent = current;
if(data < parent->data){
current = current->leftChild;
if(current == NULL){
father[tempNode->data] = parent->data;
parent->leftChild = tempNode;
return;
}
}
else{
current = current->rightChild;
if(current == NULL){
father[tempNode->data] = parent->data;
parent->rightChild = tempNode;
return;
}
}
}
}
int main ( void ) {
int n;
scanf("%d", &n);
struct node* tree = NULL;
std::unordered_map<int, int> father; //guarda os pais de cada valor
int in[n + 1];
for (int i = 1; i <= n; ++i) {
scanf("%d", &in[i]);
insertAndBuildFather(&tree, in[i], father);
}
int q, qi;
scanf("%d", &q);
for (int i = 1; i < q; ++i) {
scanf("%d", &qi);
printf("%d ", father[in[qi]]);
}
scanf("%d", &qi);
printf("%d\n", father[in[qi]]);
}
Agradeço qualquer ajuda =)