Ir para o conteúdo
msmvs

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

Mensagens Recomendadas

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


Ligação para a mensagem
Partilhar noutros sites
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


Ligação para a mensagem
Partilhar noutros sites
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


Ligação para a mensagem
Partilhar noutros sites
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
  • Voto 1

IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
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


Ligação para a mensagem
Partilhar noutros sites
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


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

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

estás a actualizar nas rotações ?


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
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


Ligação para a mensagem
Partilhar noutros sites
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


Ligação para a mensagem
Partilhar noutros sites
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

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
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


Ligação para a mensagem
Partilhar noutros sites
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

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
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.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
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


Ligação para a mensagem
Partilhar noutros sites
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


Ligação 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. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.