Package br.unip.aps.estruturas

Class ArvoreAVL<K,V>

java.lang.Object

br.unip.aps.estruturas.ArvoreAVL<K,V>

public final class ArvoreAVL<K,V>
extends Object

Arvore AVL (Adelson-Velsky e Landis, 1962): arvore binaria de busca balanceada por rotacoes.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final class	ArvoreAVL.No<K,V>	No da arvore; chaves repetidas acumulam valores no mesmo no.
static interface	ArvoreAVL.Ouvinte<K>	Recebe cada rotacao realizada (para a animacao da arvore).

Constructor Summary

Constructors

Constructor	Description
ArvoreAVL(Comparator<? super K> comparador, OperationCounter contador)

Method Summary

Modifier and Type	Method	Description
int	altura()
List<V>	buscar(K chave)	Valores associados a chave (lista vazia se ausente).
OperationCounter	contador()
void	emOrdem(BiConsumer<? super K,List<V>> visita)	Percurso em ordem (chaves crescentes).
void	inserir(K chave, V valor)
void	intervalo(K de, K ate, Consumer<? super V> destino)	Visita em ordem crescente os valores com chave em [de, ate], podando subarvores fora do intervalo.
int	nos()
ArvoreAVL.No<K,V>	raiz()
boolean	remover(K chave)	Remove a chave e todos os seus valores.
long	rotacoesDuplas()
long	rotacoesSimples()
void	setOuvinte(ArvoreAVL.Ouvinte<K> ouvinte)
boolean	valida()	Verifica as invariantes: ordem de busca e |fator de balanceamento| <= 1 em todos os nos.
long	valores()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

ArvoreAVL

public ArvoreAVL(Comparator<? super K> comparador,
 OperationCounter contador)

Method Details

setOuvinte

public void setOuvinte(ArvoreAVL.Ouvinte<K> ouvinte)

inserir

public void inserir(K chave,
 V valor)

remover

public boolean remover(K chave)

Remove a chave e todos os seus valores.

buscar

public List<V> buscar(K chave)

Valores associados a chave (lista vazia se ausente).

intervalo

public void intervalo(K de,
 K ate,
 Consumer<? super V> destino)

Visita em ordem crescente os valores com chave em [de, ate], podando subarvores fora do intervalo.

emOrdem

public void emOrdem(BiConsumer<? super K,List<V>> visita)

Percurso em ordem (chaves crescentes).

valida

public boolean valida()

Verifica as invariantes: ordem de busca e |fator de balanceamento| <= 1 em todos os nos.

raiz

public ArvoreAVL.No<K,V> raiz()

altura

public int altura()

nos

public int nos()

valores

public long valores()

rotacoesSimples

public long rotacoesSimples()

rotacoesDuplas

public long rotacoesDuplas()

contador

public OperationCounter contador()