INF1010 3WB – T2: Reimplementação do Dicionário utilizando uma Red-Black Tree.

Enunciado:

Implemente uma classe Dicionario de elementos chave-valor formados por textos (strings), em C++, respeitando o seguinte:

1. Cada chave é única, ou seja, não devem existir elementos com chave repetida. Se o mesmo elemento for inserido mais de uma vez apenas a primeira vez modifica o dicionário. Ao tentar editar ou remover um elemento que não existe, nada acontece. Ao tentar obter um elemento que não existe, a string retornada é vazia.
2. Utilize uma árvore rubro-negra (Red-Black Tree) para armazenar os elementos utilizando a ordem alfabética das chaves.
3. Utilize a interface mostrada no arquivo t2_dicionario_rbt.h para sua classe.
4. É permitido criar funções ou variáveis membro privadas, para facilitar a implementação.

t2_dicionario_rbt.h

#ifndef T2_DICIONARIO_RBT_H
#define T2_DICIONARIO_RBT_H

#include <string>

class DicionarioRbt
{
public:
    //Cria um dicionario vazio
    DicionarioRbt();

    //Cria um dicionario com um primeiro elemento
    DicionarioRbt(const std::string& chave, const std::string& valor);

    //Cria um dicionario a partir de outro
    DicionarioRbt(const DicionarioRbt& orig);

    //Destroi o dicionario
    virtual ~DicionarioRbt();

    //Insere um elemento no dicionario
    void insere(const std::string& chave, const std::string& valor);

    //Obtém o valor de um elemento, dada a sua chave
    std::string obtemValor(const std::string& chave);

    //Remove um elemento no dicionario, dada a sua chave
    bool remove(const std::string& chave);

    //Retorna o numero de elementos do conjunto
    unsigned int tamanho();

    //Exibe os elementos do dicionario na ordem lexografica das suas chaves
    void mostra();

    //Exibe a arvore que armazena o dicionario no formato
    //( raiz (sub-arvore a esquerda) (sub arvore a direita) )
    void mostraRbt();

    //Retorna a altura da arvore que armazena o dicionario
    int altura();

private:
    enum Cor
    {
        VERMELHO,
        PRETO
    };

    struct RbtNo
    {
        std::string _chave;
        std::string _valor;

        RbtNo* _pai;  // no pai
        RbtNo* _esq;  // sub-arvore a esquerda
        RbtNo* _dir;  // sub-arvore da direita

        Cor _cor;
    };

    RbtNo* _raiz;

    /* Funcoes e membros privados que julgar necessarios */
};

#endif // T2_DICIONARIO_RBT_H