/*
Implemente el TAD Multiset anterior de tal manera que el tiempo de ejecución de las operaciones
insertar, ocurrencias y eliminar sean O(log(n)) en el caso promedio, siendo n la cantidad de
elementos diferentes del multiset, y el de las operaciones crear, cantidad, min y max sea O(1) peor
caso. Concretamente, defina en C# la representación del TAD y escriba los códigos de las operaciones
insertar, ocurrencias y min. Omita el código del resto de las operaciones, que puede asumir están
implementadas.
*/
#include <iostream>

struct nodoArbol{
    int dato;
    int ocurrencias;
    nodoArbol *izq;
    nodoArbol *der;
}

typedef nodoArbol * ABB;

struct RepresentacionMultiset {
    int cantidad
    ABB min;
    ABB max;
    ABB arbol;
}
typedef RepresentacionMultiset * Multiset ;


// POS : Devuelve la cantidad de ocurrencias del elemento x del multiset m (0 si x no est á en m).
int ocurrencias ( Multiset m , int x ){
    return ocurrenciasAux(m->arbol, x);
}

int ocurrenciasAux(ABB arbolito, int x){
    if (arbolito==NULL){
        return 0;
    }else if (arbolito->dato==x){
        return arbolito->ocurrencias;
    }else if (arbolito->dato<x){
        return ocurrenciasAux(arbolito->der, x);
    }else{
        return ocurrenciasAux(arbolito->izq, x);
    }
}

// POS : Retorna el mí nimo elemento del multiset m ( independientemente del número de ocurrencias ). 
// PRE : m no vacío.
int min ( Multiset m ){
    return m->min->dato;
}

ABB insertarAux(ABB & arbolito, int x, int n){
    if (arbolito==NULL){
        ABB nuevo = new nodoArbol;
        nuevo->dato=x;
        nuevo->izq=NULL;
        nuevo->der=NULL;
        nuevo->ocurrencias=n;
        arbolito=nuevo;
        return arbolito;
    }else if (arbolito->dato==x){
        arbolito->ocurrencias+=n;
        return arbolito;
    }else if (arbolito->dato<x){
        return insertar(arbolito->der, x,n);
    }else{
        return insertar(arbolito->izq, x,n);
    }   
}

// POS : Agrega n ocurrencias del elemento x al multiset m. PRE : n >0.
void insertar ( Multiset & m , int x , int n ) {
    ABB arbolAux=insertarAux(m->arbol, x, n);
    if (m->min == NULL || x < m->min->dato){
        m->min=arbolAux;
    }
    if (m->max == NULL ||x > m->max->dato){
        m->max=arbolAux;
    }
    m->cantidad+=n;
}



int main()
{
    std::cout<<"Hello World";

    return 0;
}