Análise de Poder Discriminativo Através de Curvas ROC

contingencia_thumb-5B1-5D

Quando desenvolvemos sistemas, métodos ou testes que envolvem a detecção, diagnósticos ou previsão de resultados, é importante validar seus resultados de forma a quantificar seu poder discriminativo e identificar um procedimento ou método como bom ou não para determinada análise. No entanto, devemos levar em conta que a simples quantificação de acertos num grupo de teste não necessariamente reflete o quão eficiente um sistema é, pois essa quantificacao dependerá fundamentalmente da qualidade e distribuição dos dados neste grupo de teste.

 

Para exemplificar, tomemos o exemplo de um sistema para detecção de diabetes em pacientes, cuja saída é 1 ou 0 indicando se o paciente possui a condição ou não.  Agora, suponha que ao aplicamos este sistema num grupo de teste contendo 100 pacientes, dos quais já sabemos quais tem diabetes ou não, o sistema acerta 90% dos diagnósticos. Parece muito bom, não?

Não exatamente. O que não levamos em conta foi a distribuição da condição no grupo de teste. Revelamos agora que, no grupo de teste, 90% dos pacientes, na verdade, tinham a condição. O sistema, portanto, poderia simplesmente ter dito “1” a qualquer entrada apresentada, e mesmo assim, ainda conseguiria 90% de acerto já que os restantes 10% eram saudáveis. A esta altura, já não podemos ter a certeza de que o tal sistema seria tão bom assim.

 

contingencia
Tabela de Contingência (matriz de confusão)

Para casos como este, outras medidas foram criadas a fim de desconsiderar eventuais desbalanceamentos nos grupos de teste. Antes de entrar nestas medidas, apresento-lhe a chamada tabela de contingência (ou matriz de confusão), que servirá de base para as demais medidas apresentadas. Seu funcionamento é simples: consideramos valores positivos que o sistema julgou positivos como verdadeiros positivos (acerto), valores positivos que o sistema julgou negativos como falso negativo (erro), valores negativos que o sistema julgou como negativos como verdadeiros negativos (acerto), e valores negativos que o sistema julgou positivos como falso positivos (erro).

 

A seguir, apresentamos algumas medidas dela derivadas.

Acurácia

    A proporção de predições corretas, sem levar em consideração o que é positivo e o que é negativo. Esta medida é altamente suscetivel a desbalanceamentos do conjunto de dados e pode facilmente induzir a uma conclusão errada sobre o desempenho do sistema.

    ACC = TOTAL DE ACERTOS / TOTAL DE DADOS NO CONJUNTO

            = (VP + VN) / (P + N)

Sensibilidade

    A proporção de verdadeiros positivos: a capacidade do sistema em predizer corretamente a condição para casos que realmente a têm.

    SENS = ACERTOS POSITIVOS / TOTAL DE POSITIVOS

             = VP / (VP + FN)

Especificidade

    A proporção de verdadeiros negativos: a capacidade do sistema em predizer corretamente a ausência da condição para casos que realmente não a têm.

    SPEC = ACERTOS NEGATIVOS / TOTAL DE NEGATIVOS

             = VN / (VN + FP)

Eficiência

    A média aritmética da Sensibilidade e Especificidade. Na prática, a sensibilidade e a especificidade variam em direções opostas. Isto é, geralmente, quando um método é muito sensível a positivos, tende a gerar muitos falso-positivos, e vice-versa. Assim, um método de decisão perfeito (100 % de sensibilidade e 100% especificidade) raramente é alcançado, e um balanço entre ambos deve ser atingido.

    EFF = (SENS + ESPEC) / 2

Preditividade Positiva

Preditividade Negativa

Coeficiente de Correlação de Matthews – ou Coeficiente φ (phi)

    O coeficiente de correlação de Matthews é uma medida de qualidade de duas classificações binárias que pode ser usada mesmo se as classes possuem tamanhos bastante diferentes. Retorna um valor entre −1 e +1, em que um coeficiente de +1 representa uma predicao perfeita, 0 uma predicao aleatoria media, e –1 uma predicao inversa. Esta estatistica é equivalente ao coeficiente phi, e tenta, assim como a eficiência, resumir a qualidade da tabela de contingência em um único valor numérico passivel de ser comparado.

    MCC = φ = (VP*VN – FP*FN) / sqrt((VP + FP)*(VP + FN)*(VN + FP)*(VN + FN))

    Note que, se qualquer uma das somas no denominador for igual a zero, o denominador pode ser considerado 1, resutando num MCC igual a 0 que seria o limite correto para esta situação.

 

A Curva de Receiver Operating Characteristic (ROC)

A curva ROC (ou curva de ROC) foi desenvolvida por engenheiros elétricos e engenheiros de sistemas de radar durante a Segunda Guerra Mundial para detecter objetos inimigos em campos de batalha, tambem conhecida como teoria de detecção de sinais. A análise ROC tem sido utilizada em medicina, radiologia, psicologia e outras areas por muitas décadas e, mais recentemente, foi introduzida à áreas como aprendizado de máquina e mineracao de dados.

 

example-roc-curves
Curvas ROC de diferentes classificadores

Como o resultado de sistemas de classificação em classes geralmente são contínuos, ou seja, produzem um valor situado dentro de um determinado intervalo contínuo, como [0;1], é necessário definir um ponto de corte, ou um limiar de decisão, para se classificar e contabilizar o número de predições positivas e negativas (como diagnósticos verdadeiros e falsos no caso de ocorrência de uma patologia). Como este limiar pode ser selecionado arbitrariamente, a melhor prática para se comparar o desempenho de diversos sistemas é estudar o efeito de seleção de diversos limiares sobre a saída dos dados.

Para cada ponto de corte são calculados valores de sensibilidade e especificidade, que podem então serem dispostos em um gráfico denominado curva ROC, que apresenta no eixo das ordenadas os valores de sensibilidade e nas abscissas o complemento da especificidade, ou seja, o valor (1-especificidade).

 

Um classificador perfeito corresponderia a uma linha horizontal no topo do gráfico, porém esta dificilmente será alcançada. Na prática, curvas consideradas boas estarão entre a linha diagonal e a linha perfeita, onde quanto maior a distância da linha diagonal, melhor o sistema. A linha diagonal indica uma classificação aleatória, ou seja, um sistema que aleatoriamente seleciona saídas como positivas ou negativas, como jogar uma moeda para cima e esperar cara ou coroa. Definitivamente, não é o tipo de sistema mais confiável possível. No entanto, um sistema cuja curva ROC esteja localizada abaixo da diagonal ainda pode ser convertido num bom sistema – basta inverter suas saídas e então sua curva também será invertida.

Uma medida padrão para a comparacao de sistemas é a área sob a curva (AUC), que pode ser obtida por métodos de integração numérica, como por exemplo, o método dos trapézios. Teoricamente, quanto maior a AUC, melhor o sistema.

 

Exemplo de como fazer uma curva ROC no Excel.

 

Calculando a área de uma curva ROC no Microsoft Excel®

    Coloque os pares sensibilidade e (1-especificidade) nas colunas A e B, respectivamente. Caso sejam 10 pontos (de A1 a B10), utilize a seguinte fórmula:

    =SUMPRODUCT((A6:A15+A5:A14)*(B5:B14-B6:B15))*0,5

Determinando o melhor ponto de corte

Finalmente, a partir de uma curva ROC, devemos poder selecionar o melhor limiar de corte para obtermos o melhor desempenho possível. Para isto, podemos utilizar como parâmetro de comparação a medida de eficiência apresentada acima ou o valor φ (phi). Assim, podemos obter o limiar que apresente a melhor combinação de valores de especificidade e sensibilidade para o sistema.

Determinando o erro padrão no cálculo da área

O erro padrão de uma curva ROC se refere ao desvio padrão assumido ao aplicarmos nosso sistema a uma amostra da população do que se aplicássemos a população inteira. Esta medida parte do fato que, dependendo de quais amostras de uma população tomemos os valores para produzir nossa análise ROC, a área sob a curva poderá variar de acordo com a distribuição particular desta amostra.

O calculo do erro é, em certo ponto, simples, pois parte de apenas três valores conhecidos: a área A sob a curva ROC, o número Na de casos da amostra que apresentam a condição investigada (por exemplo, com diabetes) e o número Nn de casos que não a apresentam (sem).

ERRO = sqrt((A*(1 – A) + (Na– 1)*(Q1 – A²)+(Nn– 1)(Q2 – A²))/(Na * Nn))

em que:

    Q1 = A/(2 – A)
    Q2 = 2*A²/(1 + A)

 

Código

Na segunda parte da versão em inglês deste artigo está disponível uma implementação de curvas ROC em C#, incluindo código-fonte e aplicativos de demonstração.

 

Guias Recomendados

Receiver Operating Curves: An Introduction – Excelente página sobre curvas ROC e suas aplicações. Inclui excelentes applets que permitem brincar com as curvas, compreender melhor seu funcionamento e seu significado. Direcionado tanto a quem busca uma rápida introdução ao tema quanto a pesquisadores já familiarizados com a área.

 

Referências

WIKIPEDIA, The Free Encyclopedia, “Receiver Operating Characteristic”, Disponível em: <http://en.wikipedia.org/wiki/Receiver_operating_characteristic> Acesso em: 07 jul. 2009.

SABATTINI, R. M. E.; “Um Programa para o Cálculo da Acurácia, Especificidade e Sensibilidade de Testes Médicos”; Revista Informédica, 2 (12): 19-21, 1995. Disponível em: <http://www.informaticamedica.org.br/informed/sensib.htm> Acesso em: 07 jul. 2009.

ANAESTHESTIST.COM, “Receiver Operating Curves: An Introduction”, Disponível em: <http://www.anaesthetist.com/mnm/stats/roc/Findex.htm> Acesso em: 13 jul. 2009.

 

Notícias Interessantes

BBC NEWS MAGAZINE, A scanner to detect terrorists; Artigo muito interessante sobre como estatísticas são mal interpretadas quando divulgadas pela mídia. “To find one terrorist in 3000 people, using a screen that works 90% of the time, you’ll end up detaining 300 people, one of whom might be your target”. Escrito por Michael Blastland.

I am my own Grandpa!

The following is a (probably buggy) solution for the problem "I am my own grandfather" presented in many Prolog courses. I know it is buggy because some queries produces infinite loops, and some ended up crashing SWI-Prolog – after all, I’ve started learning Prolog today. But at least it answers the ultimate question correctly:

?- grandfather_in_law(i,i).
true .

 

erm.. Does the term "grandfather-in-law" even exist?

 

The Problem

The problem is stated as it follows (in english):

I married a widow (let’s call her w) who has grow-up daughter (call her d). My father (f), who visited us quite often, fell in love with my step-daughter and married her. Hence my father became my son-in-law and my step-daughter became my mother. Some months later, my wife gave birth to a son (s1), who became the brother-in-law of my father, as well as my uncle. The wife of my father, that is my step-daughter, also had a son (s2). Now I am my own grandfather. (aus N. Wirth, "Algorithms + data structures = programs"

In portuguese:

Eu me casei com uma viúva (W) que tem uma filha adulta (D). Meu pai (F), que nos visitava
freqüentemente, apaixonou-se por minha enteada e casou-se com ela. Logo, meu pai se tornou meu enteado e minha enteada tornou-se minha madrasta. Alguns meses depois, minha mulher teve um filho (S1), que se tornou cunhado do meu pai, assim como meu tio. A mulher do meu pai, isto é, minha enteada, também teve um filho (S2). Agora eu sou meu próprio avô.

And as a Youtube video:

 

The Proof

(Feel free to correct me if you wish)

    male(i).
    male(f).
    male(s1).
    male(s2).
    married(i,w).
    parent(w,d).
    parent(f,i).
    married(f,d).
    parent(w,s1).
    parent(i,s1).
    parent(f,s2).
    parent(d,s2).

    married(X,Y) :- tmarried(X,Y).
    tmarried(X, Y) :- married(Y,X).

    female(X) :- not(male(X)).

    %% Normal relationships
    father(Parent, Child) :-
        parent(Parent, Child),
        male(Parent).

    mother(Parent, Child) :-
        parent(Parent, Child),
        female(Parent).

    sibling(X,Y) :-
        parent(F, X),
        parent(F, Y), X = Y.

    uncle(Uncle, Nephew) :-
        parent(Parent, Nephew),
        sibling(Parent, Uncle),
        male(Uncle).

    grandparent(Grandfather, Grandchild) :-
        parent(X,Grandchild), parent(Grandfather,X).

    %% In-law relationships
    sibling_in_law(X,Y) :-
        parent(P,X),
        parent_in_law(P,Y),
        X = Y.

    sibling_in_law(X,Y) :-
        parent(P,Y),
        parent_in_law(P,X),
        X = Y.

    parent_in_law(Parent, Child) :-
        parent(Partner, Child),
        married(Parent, Partner).

    uncle_in_law(Uncle, Nephew) :-
        parent_in_law(Parent, Nephew),
        sibling(Parent, Uncle),
        male(Uncle).

    grandparent_in_law(Grandparent, Grandchild) :-
       ( parent_in_law(X, Grandchild), parent_in_law(Grandparent, X) );
       ( parent(X, Grandchild), parent_in_law(Grandparent, X) );
       ( parent_in_law(X, Grandchild), parent(Grandparent, X) ).

    grandfather_in_law(Grandfather, Grandchild) :-
        grandparent_in_law(Grandfather, Grandchild),
        male(Grandfather).

 

Now lets try and query grandfather_in_law(i,i). to see what if gives back.

And the answer is…

42 .

 

Now I know why everybody loves this language so much 🙂

Introducing System.Console.Forms

terminal

Some days ago I started a new project just for fun. System.Console.Forms is a extension to .NET framework to “port” as much as possible of System.Windows.Forms to a Console environment.

 

I know a lot of people think there is absolutely no reason for developing console programs nowadays, but they are just plain wrong. It obviously isn’t mainstream, but if you use ssh a lot and cannot afford a X connection, then working with console interfaces makes a lot of sense. Also, I know there are other known, well-tested and proven solutions for console user interfaces like the ncurses library, but they are not very object oriented and not very user-friendly if you came from a .NET WinForms or Java SWT/Swing world.

Thus this project was started.

 

I know accomplishing this task would consume a lot of time and effort, so I can’t promise it will ever be complete, or even if it will not die a few months from now. But if are interested and want to help, feel free to contact me. Much of the base code is almost done (it is already possible to create Forms and UserControls) but most of the default controls, like TextBoxes, RadioButtons and ToolStripMenus are still incomplete or missing.

nano#nano# - 2

As you can see, it currently lacks some visual enhancements (such as drop-shadow borders and a better default form design), but this is something scheduled only for future releases. The first milestone is to replicate only the basic functionality and interface of nano, and the second is to fully reproduce MS-DOS edit.exe. When this becomes possible, the library will be almost feature complete.

I don’t think I’ll ever be able to finish this by myself alone, so I licensed the project under the LGPL if anyone else gets interested. The project is being hosted at Google Code, and the project page is http://console-forms.googlecode.com.

Árvore B em Arquivo (em C++)

Novamente, outro post ecológico! Após a apresentação da Árvore AVL, porque não agora Árvores B?

Árvore de maior largura do mundo

Árvores B são estrutura de dados bastante utilizadas em sistemas de arquivos e bancos de dados. São geralmente mais densas em informação por nível em comparação com Árvores AVL, o que significa que possuem geralmente uma altura menor mesmo armazenando um mesmo número de elementos.

Em primeiro lugar, devo especificar que este artigo não se destina a explicar o funcionamento das Árvores B em detalhes. Para isto temos uma variedade de fontes e recursos à nossa disposição; descrições sobre o funcionamento de uma Árvore B são facilmente encontradas na internet.

Uma coisa, no entanto, infelizmente não é: Implementações compreensíveis que também sejam, ao mesmo tempo, completas e funcionais.

Como exemplo, não raro encontramos o mesmo problema que tivemos ao encontrar informações sobre Árvores AVL. É dada menos ênfase aos métodos de remoção destas estruturas. Ou então, por vezes encontramos a Árvore B implementada fora de seu contexto: em memória. Árvores B reais servem ao propósito de serem armazenadas em disco; por isso seus nós são geralmente denominados páginas.

Introdução

Imagine que uma Árvore AVL contenha tantos dados que já não caiba mais em memória. Tentando contornar esta situação, podemos definir uma estratégia em que cada nó da Árvore AVL (que armazena no máximo 1 elemento) ocupe uma posição diferente dentro de um mesmo arquivo de dados. Para acessar um filho de um nó, por exemplo, podemos ler em qual posição o filho se encontra, navegar até a posição determinada e o carregarmos em memória. É fácil ver que esta solução resolve o problema da memória, pois a cada vez iremos carregar apenas a informação com o qual queremos trabalhar, e nunca a árvore toda.

Porém, imagine agora que gostaríamos de percorrer a árvore em busca de um elemento qualquer. Imagine também que o elemento em questão não está contido na árvore e que esta árvore tem, em termos gerais, n níveis de altura. Utilizando o algoritmo de busca em árvore binária, teremos de fazer, no mínimo, n leituras em disco para buscar a informação que queremos. Ou melhor, para concluir que não pudemos encontrar a informação que queríamos. Apenas relembrando, não esqueça o fato de que memórias secundárias como o disco rígido são geralmente ordens de magnitude mais lentas do que a memória principal.

Para n pequeno, é evidente que isto não faz diferença – o tempo de acesso a um disco rígido é, geralmente, de alguns milisegundos. Mas lembrando que como estamos falando de árvores realmente grandes, o acesso ao disco pode tornar-se um gargalo considerável.

Nesse contexto, a estrutura AVL torna-se bastante ineficiente. Como então solucionar este problema?

R: Diminuindo o número de seeks necessários para se alcançar uma informação.

A Árvore B (ou B-Tree) emprega uma estrutura paginada ideal para minimizar o acesso em disco. Cada um de seus nós contem não um elemento, mas vários; quantos seu desenvolvedor quiser. A cada acesso, várias, e não apenas uma informação, são lidas de cada vez. Desta maneira a informação torna-se muito mais condensada nos primeiros níveis, e altura da árvore diminui consideravelmente.

 

Citando a Wikipedia:

Em ciência da computação, Árvore B ou B-Tree é uma estrutura de dados árvores que são muito utilizadas em banco de dados e sistema de arquivos.

Para inserir ou remover variáveis de um nó, o nó não poderá ultrapassar sua ordem e nem ser menor que sua ordem dividida por dois. Árvores B não precisam ser rebalanceadas como são freqüentemente as árvores de busca binária com Árvore AVL. Árvores B têm vantagens substanciais em relação a outros tipos de implementações quanto ao tempo de acesso e pesquisa aos nós.

 

Esta é uma apresentação bastante razoável. No entanto, certa cautela precisa ser tomada pois autores diferentes tratam a ordem da Árvore B de maneiras diferentes, como por exemplo no livro Algoritmos – Teoria e Prática. Neste livro, os autores se referem não à ordem da Árvore, mas à seu grau t, definido como o número mínimo de filhos que um nó não-raiz pode possuir. Como consequência, o número mínimo de elementos de uma Árvore poderá ser tomado como t-1 e o máximo como 2t-1. Com isso, acabam efetivamente definindo a ordem da árvore (a que me refiro como sendo o número máximo de filhos de um nó) como 2t e o número máximo de elementos como 2t-1. Apesar de se enquadrar dentro das regras enunciadas acima na definição da Wikipedia, a apresentação de Árvores B desta forma inclui um pequeno problema.

A ordem de das árvores ficará restrita a termos pares (que estejam na forma 2t), o que simplifica os algorítmos de inserção e remoção, mas acabam por não mais descrever à uma Árvore B de ordem geral.

Por esta razão, o código que apresentaremos e documentaremos a seguir se adequa à Árvores B de qualquer ordem.

Propósito

Como bem sabemos, o propósito de uma Árvore B é otimizar o acesso e a manipulação da informação armazenada em discos, servindo geralmente como estrutura de índice à outros arquivos de registros no qual o índice pode se tornar muito grande para caber em memória. Neste contexto, atuando como índice, a árvore armazenará uma chave e a posição relativa em arquivo (relative record number ou byte offset) em que o registro se encontra no arquivo de registros.

Definições

Antes de prosseguirmos, enunciaremos primeiro algumas definições para que não haja confusão no decorrer deste artigo:

A ordem m da árvore está definida como o número máximo de filhos que um único nó pode possuir;

Logo, o número máximo de elementos num nó e dado por m-1 e o máximo de filhos por m. Já o número mínimo de elementos que um nó pode possuir é dado pela fórmula floor((m-1) / 2).

A Árvore B está implementada em arquivo, então definimos “Offset” como um typedef para long int. Para representar o equivalente em arquivo para o ponteiro nulo (NULL) utilizaremos o valor constante NULLOFFSET como -1L (menos-um na forma de long int). Esta é uma prática comum pois a posição 0, em arquivo, é uma posição válida, ao contrário de seu equivalente em memória.

Implementação

O código que apresentamos e documentamos a seguir se adequa à Árvores B de quaisquer ordens. A implementação foi feita em C++ no Microsoft Visual Studio, sem utilizar as extensões .NET/CLI (apesar da solução, em si, possuir código misto pois estava atrelada à uma interface gráfica em WinForms).

Clique aqui para ver o código e a documentação completos da Árvore B (BTree) em Arquivo (em C++) gerados pela ferramenta Doxygen. O código é, claro, livre para quaisquer adaptações desde que permaneça sob a Licença MIT e suas informações autorais sejam mantidas. Mas lembre-se de que o código tem fins meramente educativos e não deve ser utilizado num ambiente onde a performance é um fator crítico. Ou, melhor, não deve ser utilizado em outro lugar fora um trabalho acadêmico simples.

Diagrama de Classes

 

O Nó (BTreeNode)

O nó da Árvore B, aqui chamado de BTreeNode, pode conter vários elementos, em contraste com a Árvore AVL, em que pode haver apenas um. A Árvore B pode ser vista como uma generalização da Árvore AVL para ordens superiores, ou a Árvore AVL como uma especialização da Árvore B para ordem 2 (m=2).

Assim, o nó deve conter um vetor de elementos e um vetor de filhos, onde estes filhos, ao invés de conter ponteiros em memória, contem ponteiros em arquivo (Offsets) para os próximos nós.

Representação de uma Árvore B [Wikipedia]

É nesta classe que estão contidos os métodos split() e merge(), que divide um nó em dois e intercala dois nós em um único nó, respectivamente. Estes métodos são chamados durante a operação de Inserção ou de Remoção pela classe principal BTree, que é a classe gerenciadora dos nós. Mais informações serão apresentadas à seguir.

A Lista de Disponíveis (DStack)

Como a estrutura da Árvore B é mantida em arquivo, não basta alocarmos/desalocarmos nós em memória utilizando new e delete como fazíamos na Árvore AVL. Temos que alocar uma posição no arquivo que acomoda a árvore e armazenar o nó nesta posição; ao deletarmos um nó temos que, de algum modo, avisar que a posição que antes acomodava o nó agora está vaga. Para isto, utilizamos outra estrutura em arquivo denominada lista de disponíveis, que é responsável por registrar, na forma de uma lista encadeada, onde estão os registros disponíveis e assim indicar qual a próxima posição vaga no arquivo. Para simplificação, esta lista é, na verdade, geralmente implementada como uma pilha.

Assim, suponha que a pilha está vazia (a posição inicial registrada é NULLOFFSET) e a posição 241 foi desocupada. Então ao chamar o método push(241) a lista de disponíveis deverá caminhar até a posição 241, escrever NULLOFFSET e então registrar que 241 é o começo da pilha.

Agora suponha que 340 foi desocupada. Então o método push(340) irá caminhar até a posição 340, escrever 240, que é o endereço do nó que antes era começo da pilha, e registrar que a pilha começa agora na posição 340. Assim por diante, push(500) caminhará até a posição 500, escreverá o endereço do começo anterior (340) e registrará que a posição inicial é, agora, 500. Assim, os nós vão se encadeando – cada posição disponível carrega uma referência a próxima posição disponível ou a NULLOFFSET se não há nada mais além daquele ponto.

Para remover, pop() simplesmente deverá ler quem é a posição inicial, e, caso seja diferente de NULLOFFSET, caminhar até esta posição, ler qual é o endereço do próximo nó (ou NULLOFFSET, caso não haja mais nós) e então registrar esta posição como a nova posição inicial.

Clique aqui para visualizar a implementação da lista de disponíveis em C++.

 

A Árvore (BTree)

A classe BTree, ou Árvore B, deve ser responsável por gerenciar seus nós, alocando, dealocando, carregando e descarregando, tentando o máximo possível minimizar a quantidade de nós carregados em memória de cada vez. É nela que estão contidos os métodos de inserção e remoção, que em nossa implementação são recursivos.

Abaixo está uma pequena descrição sobre o funcionamento da inserção e remoção, porém note que seus códigos correspondentes são, na verdade, bem mais elaborados que esta pequena introdução. Felizmente, há comentários no decorrer do código para auxiliar em seu entendimento.

Inserção / Split

O método de inserção da classe BTree pode cair no caso em que não é mais possível armazenar informação num nó pois este está cheio. Quando isto acontece, chama-se o método-membro Split do nó que está cheio, que dividirá o nó em dois e retornará uma referência em arquivo (Offset) ao novo nó criado durante a divisão. O método que controla a inserção está presente na classe BTree, enquanto o split pertence ao BTreeNode.

Remoção / Merge

Analogamente a inserção, o método de remoção da classe BTree poderá cair no caso em que seja necessário remover um elemento de um nó mas efetuar esta operação violaria a regra sobre o número mínimo de elementos que um nó deve conter. Neste caso, a árvore pode encontrar o elemento sucessor (imediatamente seguinte) ao elemento que estamos tentando remover, trocar os dois e então remover o substituto recursivamente, ou, caso não seja possível emprestar de ninguem, realizar uma intercalação entre dois nós mínimos formando um novo nó completo. Esta intercalação é conhecida como merge. O método que controla a remoção está presente na classe BTree, enquanto o merge pertence ao BTreeNode.

 

Código fonte em C++

O código fonte pode ser navegado na íntegra clicando-se aqui. Para fazer download de uma solução Visual Studio 2008 contendo o fonte, clique aqui.

Árvore AVL em C++

Aqui está um código em C++ para uma Árvore AVL visando fins mais educacionais do que práticos. Apesar da teoria ser muito importante, não adianta nada ler pseudo-algorítmos sem saber como a teoria pode ser, de fato, aplicada. Ainda mais quando a maioria dos livros-texto deixa o método de remoção como exercício. Que mania!

A Árvore apresentada abaixo utiliza apenas uma técnica que pode parecer estranha, a primeira vista, para quem está acostumado a tratar com árvores em algoritmo puro. As subárvores esquerda e direita, presentes em cada nó, estão dispostas em um vetor de dois elementos. Isto traz uma vantagem imensa na hora de rotacionar a árvore, pois corta a necessidade de métodos auxiliares pela metade. Ao invés de termos de implementar rotações à esquerda e depois a direita, por exemplo, aproveitamos um mesmo método para realizar a operação de rotação em ambas as direções.

Fora este recurso adicional, o restante da implementação é bem similar aos textbooks que encontramos por aí. O nó não precisa de uma referência adicional ao seu pai (que é desnecessária, por sinal) e guarda apenas seu fator de balancemento (outras implementações guardam sua altura). O código é orientado a objetos (nada de código C disfarçado), e não está sobrecarregado com templates, embora qualquer um possa modificar o código de forma a suportá-los facilmente.

Continue reading →