public class BST<Key extends java.lang.Comparable<Key>,Value> extends java.lang.Object
Esta é uma implementação de tabela de símbolos cujas são comparáveis. As chaves (e os valores) são mantidos m uma árvore binária de busca (BST) não necessariamente balanceada. Seguindo a convenção usual para tabelas de símbolos, as chaves são distintas duas a duas.
For additional documentation, see Section 3.2 of "Algorithms, 4th Edition" (p.396 of paper edition), by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
BST() |
Modifier and Type | Method and Description |
---|---|
Key |
ceiling(Key key) |
boolean |
contains(Key key)
Does this symbol table contain a (key,value) pair
with the given key?
|
void |
delete(Key key)
Deletes from this symbol table
the given key (and the corresponding value).
|
void |
deleteMax()
Deletes the largest key (and the corresponding value)
from this symbol table.
|
void |
deleteMin()
Deletes the smallest key (and the corresponding value)
from this symbol table.
|
Key |
floor(Key key)
Returns the largest key in the symbol table that is
smaller than or equal to the given key.
|
Value |
get(Key key)
Returns the value associated with the given key.
|
int |
height()
Returns the height of this BST
(a one-node tree has height 0).
|
boolean |
isEmpty()
Is this symbol table empty?
|
java.lang.Iterable<Key> |
keys()
Range count and range search.
|
java.lang.Iterable<Key> |
keys(Key lo,
Key hi) |
java.lang.Iterable<Key> |
levelOrder() |
static void |
main(java.lang.String[] args)
Teste client.
|
Key |
max()
Returns the largest key in the symbol table
(or null if the table is empty).
|
Key |
min()
Returns the smallest key in the symbol table
(or null if the table is empty).
|
void |
put(Key key,
Value val)
Inserts (key,value) pair into the BST representing this symbol table.
|
int |
rank(Key key)
Returns the rank of the given key.
|
Key |
select(int k)
Returns the key whose rank is k.
|
int |
size()
Returns the number of (key,value) pairs in this symbol table
(i.e., the number of node os the tree).
|
int |
size(Key lo,
Key hi) |
public boolean isEmpty()
Esta tabela de símbolos está vazia?
public int size()
Devolve o número de pares (chave,valor) nesta tabela de símbolos (ou seja, o número de nós da árvore).
public boolean contains(Key key)
Esta tabela de símbolos tem um par (chave,valor) cuja chave é key?
public Value get(Key key)
Devolve o valor associado com a chave key (se key não estiver na tabela, devolve null).
public void put(Key key, Value val)
Insere o par (key,val) na BST que representa esta tabela de símbolos. Se a chave key já está na tabela de símbolos, muda o correspondente valor para val.
public void deleteMin()
Remove a menor chave (e seu valor associado) da tabela de símbolos. A tabela de símbolos deve ser não vazia.
public void deleteMax()
public void delete(Key key)
Remove desta tabela de símbolos a chave key (e o correspondente valor). Se a tabela estiver vazia, não faz nada.
public Key min()
Devolve a menor chave da tabela de símbolos (ou null se a table estiver vazia).
public Key max()
Devolve a maior chave da tabela de símbolos (ou null se a table estiver vazia).
public Key floor(Key key)
Devolve a maior chave na tabela de símbolos que é menor que ou igual a key. Devolve null se todas as chaves da tabela forem maiores que key.
public Key select(int k)
Devolve a chave cujo posto é k, ou seja, a chave tal que há k chaves menores na tabela de símbolos. Devolve null se k for negativo ou maior que size-1.
public int rank(Key key)
Devolve o posto da chave key, isto é, o número de chaves que são estritamente menores que key.
public java.lang.Iterable<Key> keys()
public int height()
Devolve a altura desta BST (uma árvore com apenas um nó tem altura 0).
public java.lang.Iterable<Key> levelOrder()
public static void main(java.lang.String[] args)
Lê strings da entrada padrão e associa valor i à i-ésima string lida. Insere os pares (chave,valor) numa BST inicialmente vazia. Exaurida a entrada padrão, imprime os nós da BST por níveis.