Ir para o conteúdo
msmvs

AVL TREE - ONI 2014 Qualificação Problema A (Para 100 Pontos)

Mensagens Recomendadas

msmvs    1
msmvs

Boas, estou aqui de volta de uma AVL tree à umas horas mas acho que não estou a conseguir pegar na sua maior eficiência. O meu grande problema aqui é ao imprimir (usando a função PER), pois acho que não é a maneira mais correta de fazer. Podem dar aqui uma ajuda?

Este código da Run Time no mooshak com 44 pontos. Eu já tenho uma solução de 60 O(N^2), mas queria evoluir para 100.

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

// An AVL tree node
struct node
{
   int key;
   struct node *left;
   struct node *right;
   int height;
};
// A utility function to get maximum of two integers
int max(int a, int b);
// A utility function to get height of the tree
int height(struct node *N)
{
   if (N == NULL)
    return 0;
   return N->height;
}
// A utility function to get maximum of two integers
int max(int a, int b)
{
   return (a > b)? a : b;
}
/* Helper function that allocates a new node with the given key and
   NULL left and right pointers. */
struct node* newNode(int key)
{
   struct node* node = (struct node*)
				    malloc(sizeof(struct node));
   node->key   = key;
   node->left   = NULL;
   node->right  = NULL;
   node->height = 1;  // new node is initially added at leaf
   return(node);
}
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
struct node *rightRotate(struct node *y)
{
   struct node *x = y->left;
   struct node *T2 = x->right;
   // Perform rotation
   x->right = y;
   y->left = T2;
   // Update heights
   y->height = max(height(y->left), height(y->right))+1;
   x->height = max(height(x->left), height(x->right))+1;
   // Return new root
   return x;
}
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
struct node *leftRotate(struct node *x)
{
   struct node *y = x->right;
   struct node *T2 = y->left;
   // Perform rotation
   y->left = x;
   x->right = T2;
   //  Update heights
   x->height = max(height(x->left), height(x->right))+1;
   y->height = max(height(y->left), height(y->right))+1;
   // Return new root
   return y;
}
// Get Balance factor of node N
int getBalance(struct node *N)
{
   if (N == NULL)
    return 0;
   return height(N->left) - height(N->right);
}
struct node* insert(struct node* node, int key)
{
   /* 1.  Perform the normal BST rotation */
   if (node == NULL)
    return(newNode(key));
   if (key < node->key)
    node->left  = insert(node->left, key);
   else
    node->right = insert(node->right, key);
   /* 2. Update height of this ancestor node */
   node->height = max(height(node->left), height(node->right)) + 1;
   /* 3. Get the balance factor of this ancestor node to check whether
   this node became unbalanced */
   int balance = getBalance(node);
   // If this node becomes unbalanced, then there are 4 cases
   // Left Left Case
   if (balance > 1 && key < node->left->key)
    return rightRotate(node);
   // Right Right Case
   if (balance < -1 && key > node->right->key)
    return leftRotate(node);
   // Left Right Case
   if (balance > 1 && key > node->left->key)
   {
    node->left =  leftRotate(node->left);
    return rightRotate(node);
   }
   // Right Left Case
   if (balance < -1 && key < node->right->key)
   {
    node->right = rightRotate(node->right);
    return leftRotate(node);
   }
   /* return the (unchanged) node pointer */
   return node;
}
/* Given a non-empty binary search tree, return the node with minimum
  key value found in that tree. Note that the entire tree does not
  need to be searched. */
struct node * minValueNode(struct node* node)
{
   struct node* current = node;
   /* loop down to find the leftmost leaf */
   while (current->left != NULL)
    current = current->left;
   return current;
}
struct node* apagaNode(struct node* root, int key)
{
   // STEP 1: PERFORM STANDARD BST DELETE
   if (root == NULL)
    return root;
   // If the key to be deleted is smaller than the root's key,
   // then it lies in left subtree
   if ( key < root->key )
    root->left = apagaNode(root->left, key);
   // If the key to be deleted is greater than the root's key,
   // then it lies in right subtree
   else if( key > root->key )
    root->right = apagaNode(root->right, key);
   // if key is same as root's key, then This is the node
   // to be deleted
   else
   {
    // node with only one child or no child
    if( (root->left == NULL) || (root->right == NULL) )
    {
	    struct node *temp = root->left ? root->left : root->right;
	    // No child case
	    if(temp == NULL)
	    {
		    temp = root;
		    root = NULL;
	    }
	    else // One child case
		 *root = *temp; // Copy the contents of the non-empty child
	    free(temp);
    }
    else
    {
	    // node with two children: Get the inorder successor (smallest
	    // in the right subtree)
	    struct node* temp = minValueNode(root->right);
	    // Copy the inorder successor's data to this node
	    root->key = temp->key;
	    // Delete the inorder successor
	    root->right = apagaNode(root->right, temp->key);
    }
   }
   // If the tree had only one node then return
   if (root == NULL)
  return root;
   // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
   root->height = max(height(root->left), height(root->right)) + 1;
   // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
   //  this node became unbalanced)
   int balance = getBalance(root);
   // If this node becomes unbalanced, then there are 4 cases
   // Left Left Case
   if (balance > 1 && getBalance(root->left) >= 0)
    return rightRotate(root);
   // Left Right Case
   if (balance > 1 && getBalance(root->left) < 0)
   {
    root->left =  leftRotate(root->left);
    return rightRotate(root);
   }
   // Right Right Case
   if (balance < -1 && getBalance(root->right) <= 0)
    return leftRotate(root);
   // Right Left Case
   if (balance < -1 && getBalance(root->right) > 0)
   {
    root->right = rightRotate(root->right);
    return leftRotate(root);
   }
   return root;
}

int imprime(struct node *root,int targetPos,int curPos)
{
   if(root != NULL)
   {
    int newPos = imprime(root->left, targetPos, curPos);
    newPos++;
    if (newPos == targetPos)
    {
	    printf("%d\n", root->key);
    }
    return imprime(root->right, targetPos, newPos);
   }
   else
   {
    return curPos;
   }
}

int main()
{
 struct node *root = NULL;
 int total=0;
 int n,b;
 string a;
 cin >> n;
 for (int i=0; i<n; i++)
 {
  cin >> a >> b;
  if(a=="INS")
	  {root = insert(root, b);total=total+1;}
  else
  if(a=="REM")
	   {root = apagaNode(root, b);total=total-1;}
  else
	  imprime(root, total-b+1, 0);
 }
   return 0;
}

Esta foi a maneira que arranjei para imprimir.

int imprime(struct node *root,int targetPos,int curPos)
{
   if(root != NULL)
   {
    int newPos = imprime(root->left, targetPos, curPos);
    newPos++;
    if (newPos == targetPos)
    {
	    printf("%d\n", root->key);
    }
    return imprime(root->right, targetPos, newPos);
   }
   else
   {
    return curPos;
   }
}

O problema aqui é que nao consigo arranjar uma maneira para imprimir, mantendo a complexidade O(log n).

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
msmvs    1
msmvs

Porque nao usas um set de C++ em vez de implementar a arvore de inicio?

E será que dá 100 pontos? Não é a mesma coisa que implementar Buckets?

Na minha solução de 60 pontos usei uma multiset (por causa dos valores repetidos)

Editado por msmvs

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
msmvs    1
msmvs

Ok ;) vou experimentar.

Problema A: http://www.dcc.fc.up.pt/oni/problemas/2014/qualificacao/probA.html

Não estou a conseguir implementar o set, porque não deixa adicionar valores repetidos, o que acontece neste problema.

Aqui está a minha solução com multiset (60 Pontos)

#include <iostream>
#include <set>
#include <string.h>
using namespace std;
int main ()
{
 std::multiset<int> values;
 int fa=-1;
 std::multiset<int>::iterator it;
 int n,b;
 unsigned int ii=-1;
 string a;
 cin >> n;
 for (int i=0; i<n; i++)
 {
  cin >> a >> b;
  if(a=="INS")
	  values.insert(b);
  else
  if(a=="REM")
	   values.erase (values.find(b));
  else
  {
	  fa=fa+1;
	  for (it=values.begin(); it!=values.end(); ++it)
	  {
		  ii+=1;
		  if(ii==values.size()-b)
		  {cout << *it << endl;break;}
	  }
	  ii=-1;

  }
 }
 return 0;
}

Se calhar eu não percebi o que querias dizer com set. Seria Implementar a árvore com um set?

Talvez seja o facto de colocar aquele FOR para imprimir que faz com que a solução fica em O(N^2). Da para evitar?

Editado por msmvs

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1132
HappyHippyHippo

presumo que estejas a tentar fazer a leitura da posição k ...

se queres obter vantagens do uso de uma árvore para esse processo, terás de guardar o número de elementos da subárvore em cada nó, caso contrário, o processo será sempre O(n) porque necessitas de percorrer todos os elementos de Tree(0) até Tree(k)

struct node
{
   int key;
   struct node *left;
   struct node *right;
   int height;
   int n_nodes;
};

Agora, sempre que inseres ao removas um nó, terás de actualizar também este valor que guarda o número de nós da subárvore.

depois dessa alteração, podes fazer:

int imprime(struct node *root, int targetPos, int curPos)
{
   // elemento não encontrado
   if (root == NULL)
      return curPos;

   // verificar se existe o nó à esquerda
   if (root->left) {
       // verificar se a posição targetPos se encontra na subárvore da esquerda
       if (targetPos < curPos + root->left->n_nodes)
           return imprime(root->left, targetPos, curPos)
       else
           // actualizar a posição actual (contabilizar o número de nós à esquerda)
           curPos += root->left->n_nodes;
   }

   // verificar se o nó actual é o nó procurado
   ++curPos;
   if (targetPos == curPos) {
       printf("%d\n", root->key);
       return targetPos;
   }

   // procurar no nó da esquerda
   return imprime(root->right, targetPos, curPos);
}

Editado por HappyHippyHippo

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

Nao da para evitar sem reescrever o codigo do set, tens razao. Na maior parte dos problemas podemos substituir uma AVL manual por um set, este e' um daqueles casos excepcionais. Desculpa ter sugerido o set, mas ja so me lembrava vagamente do enunciado.

A unica solucao e' mesmo corrigindo o codigo da AVL ou implementando buckets.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
msmvs    1
msmvs

presumo que estejas a tentar fazer a leitura da posição k ...

se queres obter vantagens do uso de uma árvore para esse processo, terás de guardar o número de elementos da subárvore em cada nó, caso contrário, o processo será sempre O(n) porque necessitas de percorrer todos os elementos de Tree(0) até Tree(k)

struct node
{
int key;
struct node *left;
struct node *right;
int height;
int n_nodes;
};

Agora, sempre que inseres ao removas um nó, terás de actualizar também este valor que guarda o número de nós da subárvore.

depois dessa alteração, podes fazer:

int imprime(struct node *root, int targetPos, int curPos)
{
// elemento não encontrado
if (root == NULL)
   return curPos;

// verificar se existe o nó à esquerda
if (root->left) {
	// verificar se a posição targetPos se encontra na subárvore da esquerda
	if (targetPos < curPos + root->left->n_nodes)
		return imprime(root->left, targetPos, curPos)
	else
		// actualizar a posição actual (contabilizar o número de nós à esquerda)
		curPos += root->left->n_nodes;
}

// verificar se o nó actual é o nó procurado
++curPos;
if (targetPos == curPos) {
	printf("%d\n", root->key);
	return targetPos;
}

// procurar no nó da esquerda
return imprime(root->right, targetPos, curPos);
}

Tentei aplicar, mas acho que há alguma coisa que não bate certo.

  1. Comecei por alterar a struct para aquela que deste.
  2. Depois Adicionei a linha de codigo:

node->n_nodes = 1;

À estrutura.

struct node* newNode(int key)
{
   struct node* node = (struct node*)
									    malloc(sizeof(struct node));
   node->key   = key;
   node->left   = NULL;
   node->right  = NULL;
   node->height = 1;  // new node is initially added at leaf
   node->n_nodes = 1;
   return(node);
}

Depois accionei +1 por cada inserção

struct node* insert(struct node* node, int key)
{
   /* 1.  Perform the normal BST rotation */
   if (node == NULL)
	    return(newNode(key));
   if (key < node->key)
	    {node->left  = insert(node->left, key);node->left->n_nodes +=1;}
   else
	   {node->right = insert(node->right, key);node->right->n_nodes +=1; }

No entanto no codigo que me deste verificas se existe o nó à esquerda, mas nao tens nada sobre se há à direita. Não é necessário?

Aqui fazes referencia a procurar no no da esquerda, mas apontas para root->right, é correto?

// procurar no nó da esquerda
   return imprime(root->right, targetPos, curPos);

Desculpa as duvidas mas não domino bem esta Árvore. Aqui não considerei nada no Remover ainda., ou seja não decrementei nos n_nodes.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
HappyHippyHippo    1132
HappyHippyHippo

estás a actualizar essa informação tantoi na inserção como na remoção ?

estás a actualizar nas rotações ?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
msmvs    1
msmvs

estás a actualizar essa informação tantoi na inserção como na remoção ?

estás a actualizar nas rotações ?

Nas remoções não testei porque primeiro queria só testar as inserções para ver se dava. Vou ver as rotações.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
msmvs    1
msmvs

Não estou a conseguir contabilizar o numero de elementos que vao passando nas rotações, e fica fora do meu controlo. Vou ver se consigo resolver isto com Buckets.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

Outra solução para 100 pontos e precisa de pouco código é usar uma Binary Indexed Tree (Fenwick Tree) - http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

Podemos usar esta árvore para armazenar o número de ocorrências de cada valor entre 1 e 1000000. Depois fazemos pesquisa binária na solução - "quantas cartas existem até X?"

Editado por mogers

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
msmvs    1
msmvs

Outra solução para 100 pontos e precisa de pouco código é usar uma Binary Indexed Tree (Fenwick Tree) - http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

Podemos usar esta árvore para armazenar o número de ocorrências de cada valor entre 1 e 1000000. Depois fazemos pesquisa binária na solução - "quantas cartas existem até X?"

Será que nao da para usar o mesmo processo mas com uma AVL Tree. Por exemplo usar a binary tree com a AVL.

Estive a ver e as Fenwick são utilizadas para fazer uma somatório de números, e ainda nao consegui enquadrar bem para inserir e remover, mas ainda estou a ver melhor. Podias so detalhar melhor o processo com a binary search?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

Com a Fenwick tree, nós fazemos a seguinte pergunta: "quantos valores existem até x?"

const int MAX = 1 << 20;  //  2**20
int tree[MAX], size;

int ReadAccumulado(int k) {  // quantas cartas até K?
int sum = 0;
for (; k; k -= k & -k)
	sum += tree[k];
return sum;
}

Assim, para determinar qual é a K-ésima carta, podemos fazer pesquisa binária na solução (é-nos dito que os valores das cartas estão entre 1 e 1 000 000. O que eu faço é transformar o K-ésima mais alta para o correspondente valor mais baixa (numero de cartas - K + 1).


left = 1, right = MAX, k = size - k + 1;
		while (left <= right) {	 // log MAX
			mid = (left + right) >> 1;
			if (ReadAccumulado(mid) >= k) {  // vezes log MAX
				res = mid;
				right = mid-1;
			}
			else
				left = mid+1;
		}
		printf("%d\n", res);

Com uma Fenwick, a complexidade seria O(log^2 max).

Uma árvore binária de pesquisa funciona de forma diferente. Uma árvore binária de pesquisa permite fazer as operações pedidas no problema em O(log n), mas é muito mais complicada de implementar "de cabeça".

Editado por mogers

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

Entao posso implementar isto mesmo com uma multiset?

Não porque precisavas de poder percorrer a árvore manualmente, escolhendo ir para o filho esquerdo ou direito dependendo do tamanho da sub-árvore. As classes da STL não permitem este tipo de acesso ou extensão (tamanho da sub-árvore).

Nas ONI, penso que usar buckets ou a Fenwick tree era mais prático. Uma estrutura de dados talvez mais útil para investir tempo (do que AVL) é uma segment tree (topcoder, e-maxx.ru (usa google translate))

Uma alternativa interessante a BST são as Treaps (http://e-maxx.ru/algo/treap) cuja implementação é relativamente curta.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
msmvs    1
msmvs

Bem ao fim de semanas de volta disto Eis ao que chego e agora peço uma grande ajuda.

  1. Peguei na minha AVL
  2. Adaptei-a conforme as sugestões do HHH
  3. Agora acho que consegui acertar com isto, mas estou com Runtime 36 Pontos

Eis as minhas mudanças:

Alterei a Estrutura e a inicialização do Node.

struct node
{
int key;
struct node *left;
struct node *right;
int height;
int subTreeSize;
};

struct node* newNode(int key)
{
struct node* node = (struct node*)
										malloc(sizeof(struct node));
node->key   = key;
node->left   = NULL;
node->right  = NULL;
node->height = 1;  // new node is initially added at leaf
node->subTreeSize=1;
return(node);
}

Depois inicializo duas novas funções. A função getSubTreeSize e a função Update.

int getSubTreeSize(struct node *N) {
if (N != NULL)
	return N->subTreeSize;
else
	return 0;
}
void update(struct node *N) {
if (N != NULL) {
	N->subTreeSize = getSubTreeSize(N->left) +
						getSubTreeSize(N->right) + 1;
}
}

Estas funções vão ser chamadas no final das funções Insert,Remove,RightRotation e Left Rotation, que é quando ocorre a mudança.

struct node *leftRotate(struct node *x)
{
struct node *y = x->right;
struct node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
// Return new root
update(y->left);
update(x->right);
return y;
}
struct node *rightRotate(struct node *y)
{
struct node *x = y->left;
struct node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
update(y->left);
update(x->right);
// Return new root
return x;
}

Depois Insert (fim do codigo da função)

...
// Right Left Case
if (balance < -1 && key < node->right->key)
{
	   node->right = rightRotate(node->right);
		return leftRotate(node);
}
/* return the (unchanged) node pointer */
update(node->left); update(node->right); update(node);
return node;
}

E por fim Remove (fim do código da função)

...
if (balance < -1 && getBalance(root->right) > 0)
{
		root->right = rightRotate(root->right);
		return leftRotate(root);
}
update(root->left); update(root->right); update(root);
return root;
}

Depois fiz uma pequena alteração na função imprime do HHH. Alterei o < para <= em -> if (targetPos <= curPos + root->left->subTreeSize)

Os outputs do enunciado dao bem e tenho 36 Pontos Runtime. O que pode ser?

Código todo:

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
// An AVL tree node
struct node
{
int key;
struct node *left;
struct node *right;
int height;
int subTreeSize;
};
int getSubTreeSize(struct node *N) {
if (N != NULL)
	return N->subTreeSize;
else
	return 0;
}
void update(struct node *N) {
if (N != NULL) {
	N->subTreeSize = getSubTreeSize(N->left) +
						getSubTreeSize(N->right) + 1;
}
}
// A utility function to get maximum of two integers
int max(int a, int b);
// A utility function to get height of the tree
int height(struct node *N)
{
if (N == NULL)
		return 0;
return N->height;
}
// A utility function to get maximum of two integers
int max(int a, int b)
{
return (a > b)? a : b;
}
/* Helper function that allocates a new node with the given key and
NULL left and right pointers. */
struct node* newNode(int key)
{
struct node* node = (struct node*)
										malloc(sizeof(struct node));
node->key   = key;
node->left   = NULL;
node->right  = NULL;
node->height = 1;  // new node is initially added at leaf
node->subTreeSize=1;
return(node);
}
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
struct node *rightRotate(struct node *y)
{
struct node *x = y->left;
struct node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
update(y->left);
update(x->right);
// Return new root
return x;
}
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
struct node *leftRotate(struct node *x)
{
struct node *y = x->right;
struct node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
//  Update heights
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
// Return new root
update(y->left);
update(x->right);
return y;
}
// Get Balance factor of node N
int getBalance(struct node *N)
{
if (N == NULL)
		return 0;
return height(N->left) - height(N->right);
}
struct node* insert(struct node* node, int key)
{
/* 1.  Perform the normal BST rotation */
if (node == NULL)
		return(newNode(key));
if (key < node->key)
		node->left  = insert(node->left, key);
else
		node->right = insert(node->right, key);
/* 2. Update height of this ancestor node */
node->height = max(height(node->left), height(node->right)) + 1;
/* 3. Get the balance factor of this ancestor node to check whether
	   this node became unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && key < node->left->key)
		return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node->right->key)
		return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node->left->key)
{
		node->left =  leftRotate(node->left);
		return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node->right->key)
{
	   node->right = rightRotate(node->right);
		return leftRotate(node);
}
/* return the (unchanged) node pointer */
update(node->left); update(node->right); update(node);
return node;
}
/* Given a non-empty binary search tree, return the node with minimum
  key value found in that tree. Note that the entire tree does not
  need to be searched. */
struct node * minValueNode(struct node* node)
{
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL)
		current = current->left;
return current;
}
struct node* apagaNode(struct node* root, int key)
{
// STEP 1: PERFORM STANDARD BST DELETE
if (root == NULL)
		return root;
// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if ( key < root->key )
		root->left = apagaNode(root->left, key);
// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if( key > root->key )
		root->right = apagaNode(root->right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
		// node with only one child or no child
		if( (root->left == NULL) || (root->right == NULL) )
		{
				struct node *temp = root->left ? root->left : root->right;
				// No child case
				if(temp == NULL)
				{
						temp = root;
						root = NULL;
				}
				else // One child case
					 *root = *temp; // Copy the contents of the non-empty child
				free(temp);
		}
		else
		{
				// node with two children: Get the inorder successor (smallest
				// in the right subtree)
				struct node* temp = minValueNode(root->right);
				// Copy the inorder successor's data to this node
				root->key = temp->key;
				// Delete the inorder successor
				root->right = apagaNode(root->right, temp->key);
		}
}
// If the tree had only one node then return
if (root == NULL)
	  return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root->height = max(height(root->left), height(root->right)) + 1;
// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
//  this node became unbalanced)
int balance = getBalance(root);
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && getBalance(root->left) >= 0)
		return rightRotate(root);
// Left Right Case
if (balance > 1 && getBalance(root->left) < 0)
{
		root->left =  leftRotate(root->left);
		return rightRotate(root);
}
// Right Right Case
if (balance < -1 && getBalance(root->right) <= 0)
		return leftRotate(root);
// Right Left Case
if (balance < -1 && getBalance(root->right) > 0)
{
		root->right = rightRotate(root->right);
		return leftRotate(root);
}
update(root->left); update(root->right); update(root);
return root;
}
int imprime(struct node *root, int targetPos, int curPos)
{
// elemento não encontrado
if (root == NULL)
   return curPos;
// verificar se existe o nó à esquerda
if (root->left) {
	// verificar se a posição targetPos se encontra na subárvore da esquerda
	if (targetPos <= curPos + root->left->subTreeSize)
		return imprime(root->left, targetPos, curPos);
	else
		// actualizar a posição actual (contabilizar o número de nós à esquerda)
		curPos += root->left->subTreeSize;
}
// verificar se o nó actual é o nó procurado
++curPos;
if (targetPos == curPos) {
	printf("%d\n", root->key);
	return targetPos;
}
// procurar no nó da esquerda
return imprime(root->right, targetPos, curPos);
}
int main()
{
 struct node *root = NULL;
 int total=0;
 int n,b;
 string a;
 cin >> n;
 for (int i=0; i<n; i++)
 {
	  cin >> a >> b;
	  if(a=="INS")
			  {root = insert(root, b);total=total+1;}
	  else
	  if(a=="REM")
			   {root = apagaNode(root, b);total=total-1;}
	  else
			  imprime(root,total-b+1, 0);
 }
return 0;
}

Editado por msmvs

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
epolozero    14
epolozero

Boas, tentei resolver este problema com o conceito de buckets, seria algo como isto?

#include <stdio.h>
#define MAX_VALUE 1000000
#define MAX_BUCKET 1000 //sqrt(max_value)
unsigned long values[MAX_VALUE] = {0};
unsigned long bucket[MAX_VALUE];
unsigned long sum[MAX_BUCKET] = {0};

int main(void){
  unsigned long n, k, i, j, l, cnt, aux;
  char op[4];
  scanf("%lu", &n);

  //buckets
  for (i=0, j=0; i< MAX_VALUE; i++, j = i / MAX_BUCKET){
  bucket[i] = j;
  }


  while(n--){
  scanf("%s", op);
  scanf("%lu", &k);
  switch(op[0]){

	 //inserir
	 case 'I':
		values[k]++;
		sum[bucket[k]]++;
		break;

	 //remover
	 case 'R':
		values[k]--;
		sum[bucket[k]]--;
		break;

	 //k-esima melhor carta
	 case 'P':
		for (i=MAX_BUCKET-1, j=0; i>=0; i--){
		   j += sum[i];
		   if (j >= k){
			  for (  l = (i + 1) * MAX_BUCKET - 1 , cnt = j - sum[i] ; ; l--){
				 cnt += values[l];
				 if (cnt == k){
					printf("%lu\n", l);
					break;
				 }
			  }
			  break;
		   }
		}
	          break;  
  }
  }


  return 0;
}

Editado por epolozero

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade