Tipus de desequilibri a l'inserir una clau en un BST X29540

Statement

html

Donada la classe dicc que permet gestionar diccionaris on només hi guardem claus úniques usant arbres binaris de cerca (BST), cal implementar el mètode

pair<Clau, char> insereix(const Clau &k);

que insereix la clau k en el diccionari si no hi era, actualitza les altures del nodes i retorna la clau dels nodes visitats a on hi ha el desequilibri més proper a les fulles (si n’hi ha) i un caràcter amb el seu tipus de desequilibri:

’E’: Esquerre
’D’: Dret
’ ’: No s’ha trobat cap desequilibri

Un node està desequilibrat quan el factor d’equilibri és superior a 1.

ATENCIÓ: No cal equilibrar el BST tal com succeeix amb els AVL, sinó que, dels nodes visitats, només cal retorna el més proper a les fulles que està desequilibrat i el tipus de desequilibri que té.

Les claus són del tipus Clau que admet una relació d’ordre total, és a dir, tenim una operació de comparació < entre claus.

Cal enviar a jutge.org la següent especificació de la classe dicc i la implementació del mètode dins del mateix fitxer. Indica dins d’un comentari a la capçalera del mètode el seu cost en funció del nombre d’elements del diccionari en el cas mig i en el cas pitjor.

#include <iostream> #include <vector> using namespace std; typedef unsigned int nat; template <typename Clau> class dicc { public: dicc() : _arrel(NULL) {}; // Pre: Cert // Post: El resultat és un dicc sense cap element ~dicc(); // Pre: Cert // Post: El dicc ha estat destruït pair<Clau, char> insereix(const Clau &k); // Pre: Cert // Post: La clau k s’ha inserit en el diccionari si no hi era. Retorna la clau dels nodes // visitats a on hi ha el desequilibri més proper a les fulles i un caràcter amb el seu // tipus de desequilibri: ’E’: Esquerre, ’D’: Dret, ’ ’: No s’ha trobat cap desequilibri private: struct node { Clau _k; // Clau node* _esq; // fill esquerre node* _dret; // fill dret nat _h; // Altura del subarbre }; node *_arrel; static void esborra_nodes(node* m); // Aquí va l’especificació dels mètodes privats addicionals }; // Aquí va la implementació dels mètodes públics i privats

Degut a que jutge.org només permet l’enviament d’un fitxer amb la solució del problema, en el mateix fitxer hi ha d’haver l’especificació de la classe i la implementació del mètode insereix (el que normalment estarien separats en els fitxers .hpp i .cpp).

Per testejar la classe disposes d’un programa principal que llegeix i insereix enters a un diccionari amb claus enteres inicialment buit.

Entrada

L’entrada conté una seqüències d’enters, són els elements que s’insereixen a un diccionari inicialment buit.

Sortida

Per a cada enter d’entrada, escriu una línia amb el text "insereix", seguit de l’enter d’entrada, el separador ":" i l’enter a on s’ha produït el primer desequilibri i el seu tipus en cas que n’hi hagi.

Observació

Només cal enviar la classe requerida i la implementació del mètode insereix. Pots ampliar la classe amb mètodes privats. Segueix estrictament la definició de la classe de l’enunciat.

Has de visitar els nodes del BST estrictament necessaris per fer la inserció, per això et pots ajudar de l’atribut _h de cada node que guarda l’altura del seu subarbre. Aquest atribut l’has d’actualitzar quan insereixis una clau.

Indica dins d’un comentari a la capçalera del mètode el seu cost en funció del nombre d’elements del diccionari en el cas mig i en el cas pitjor.

Public test cases

Input

Output

insereix 6:
insereix 8:
insereix 9: 6 D
insereix 7: 6 D
insereix 4:

Input

Output

insereix 5:
insereix -3:
insereix 8:
insereix 2:
insereix -1: -3 D
insereix -3: -3 D
insereix 7:
insereix -7:
insereix 6: 8 E
insereix -2: 2 E
insereix 9:
insereix 0: 2 E
insereix -4:

Information

Author: Jordi Esteve
Language: Catalan
Official solutions: C++
User solutions: C++