public class RedBlackBST<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 em uma árvore binária de busca (BST) rubro-negra esquerdista (todos os links vermelhos inclinados para a esquerda). Seguindo a convenção usual para tabelas de símbolos, as chaves são distintas duas a duas.
For additional documentation, see Section 3.3 of "Algorithms, 4th Edition" (p.424 of paper edition), by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
RedBlackBST() |
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) |
void |
deleteMax() |
void |
deleteMin()
Red-black deletion
|
Key |
floor(Key key) |
Value |
get(Key key)
Returns the value associated with the given key.
|
int |
height()
Utility functions
|
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) |
static void |
main(java.lang.String[] args)
Test client
|
Key |
max() |
Key |
min()
Ordered symbol table methods.
|
void |
put(Key key,
Value val)
Red-black insertion
|
int |
rank(Key key) |
Key |
select(int k) |
int |
size()
Returns the number of (key,value) pairs in this symbol table.
|
int |
size(Key lo,
Key hi) |
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 isEmpty()
Esta tabela de símbolos está vazia?
public Value get(Key key)
Devolve o valor associado com a chave key (se key não estiver na tabela, devolve null).
public boolean contains(Key key)
Esta tabela de símbolos tem um par (chave,valor) cuja chave é key?
public void deleteMin()
public void deleteMax()
public void delete(Key key)
public int height()
public Key min()
public Key max()
public Key select(int k)
public int rank(Key key)
public java.lang.Iterable<Key> keys()
public static void main(java.lang.String[] args)