Implementação IntervalTree DeleteNode Java

Question

Eu preciso uma implementação IntervalTree ou RangeTree em Java e estou tendo uma descoberta problemas com apoio exclusão trabalho.

Há um built-in um em sun.jvm.hotspot.utilities.IntervalTree , mas o método deleteNode nos estados do RBTree superclasse:

/**
 * FIXME: this does not work properly yet for augmented red-black
 * trees since it doesn't update nodes. Need to figure out exactly
 * from which points we need to propagate updates upwards.
 */

Tentando eliminar nós de um fins de árvores até lançar a exceção:

endpoint máximo do Node não foi atualizado corretamente

Como difícil seria para implementar corretamente a funcionalidade delete em uma subclasse da sun.jvm.hotspot.utilities.IntervalTree? Ou existe outra aplicação Interval árvore que já implementa isso corretamente?

Atualmente eu estou acabando com a árvore e re povoando-lo cada vez que há uma exclusão, o que está longe de ser ideal. (Nota: a criação DEBUGGING = false na RBTree acelerou as coisas tremendamente)

Answer 1

acabei modificando a sun.jvm.hotspot.utilities.IntervalTree para manter um conjunto de nós excluídos. Ao fazer uma busca, eu excluir quaisquer itens neste conjunto. Não é o ideal, mas esta foi muito mais fácil do que obter "real" eliminação de trabalho. Assim que o grupo excluído fica muito grande, eu reconstruir a árvore.

Answer 2

Este projecto tem uma implementação RangeTree que pode ser mais útil para você. Os pacotes Sun pode ser ok para uso rápido e sujo, mas eu não recomendaria a construção de alguma coisa importante confiar neles. Sun não pode mantê-los estáveis.

Answer 3

Eu não sei suas necessidades exatas, mas um segmento da árvore de trabalho podem não estático para você. Se assim for, dê uma olhada no layout Gestão SW , especificamente o SegmentTree empacotar . Ele tem a função de remover você precisa.

Se você decidir lançar seu próprio, eu poderia sugerir código aberto é? Estou surpreso que não há um intervalo de árvore aberto e fácil já está disponível.

Answer 4

há ac # implementação baseada em uma árvore AVL aumentada @ http://code.google.com/ p / intervaltree / . tradução de java não deve ser muito difícil.

Answer 5

Eu encontrei uma implementação open-source com exclusão, mas neeeds algum esforço para torná-lo totalmente funcional.

É um módulo de maior projeto de código aberto Gephi , mas aqui são o fontes e javadoc . Se você quiser um frasco você pode instalar o Gephi, e está em:

/gephi/modules/org-gephi-data-attributes-api.jar

O método delete lá, remove todos os intervalos que se sobrepõem com o intervalo de entrada (em vez de apenas a entrada de um). No entanto eu encontrei nas soruces que existem métodos privados que remover um nó específico (que armazena um intervalo). Além disso, os métodos de pesquisa privadas voltar nós.

Então eu acho que com algum pouco de esforço é possível refatorar o código e ter esta - recurso 'específica de exclusão intervalo'. A maneira mais rápida e suja seria apenas para fazer a métodos público / privado classe Node. Mas já que é um projeto open source, talvez ele poderia evoluir no futuro em algum boa implementação padrão de árvore intervalo.