Package dsa
Class RedBlackBinarySearchTreeST<Key extends Comparable<Key>,Value>
- java.lang.Object
-
- dsa.RedBlackBinarySearchTreeST<Key,Value>
-
- All Implemented Interfaces:
OrderedST<Key,Value>
public class RedBlackBinarySearchTreeST<Key extends Comparable<Key>,Value> extends Object implements OrderedST<Key,Value>
This data type provides an implementation of the ordered symbol table (OrderedST) API, using a red-black binary search tree (RBBST) as the underlying data structure.
-
-
Constructor Summary
Constructors Constructor Description RedBlackBinarySearchTreeST()
Constructs an empty symbol table.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description Key
ceiling(Key key)
Returns the smallest key in this symbol table that is larger than or equal tokey
.boolean
contains(Key key)
Returnstrue
if this symbol table containskey
, andfalse
otherwise.void
delete(Key key)
Deleteskey
and the associated value from this symbol table.void
deleteMax()
Deletes the largest key and the associated value from this symbol table.void
deleteMin()
Deletes the smallest key and the associated value from this symbol table.Key
floor(Key key)
Returns the largest key in this symbol table that is smaller than or equal tokey
.Value
get(Key key)
Returns the value associated withkey
in this symbol table, ornull
.boolean
isEmpty()
Returnstrue
if this symbol table is empty, andfalse
otherwise.Iterable<Key>
keys()
Returns all the keys in this symbol table in sorted order.Iterable<Key>
keys(Key lo, Key hi)
Returns the keys in this symbol table that are in the interval[lo, hi]
in sorted order.static void
main(String[] args)
Unit tests the data type.Key
max()
Returns the largest key in this symbol table.Key
min()
Returns the smallest key in this symbol table.void
put(Key key, Value value)
Inserts thekey
andvalue
pair into this symbol table.int
rank(Key key)
Returns the number of keys in this symbol table that are strictly smaller thankey
.Key
select(int k)
Returns the key in this symbol table with the rankk
.int
size()
Returns the number of key-value pairs in this symbol table.int
size(Key lo, Key hi)
Returns the number of keys in this symbol table that are in the interval[lo, hi]
.String
toString()
Returns a string representation of this symbol table.
-
-
-
Method Detail
-
isEmpty
public boolean isEmpty()
Description copied from interface:OrderedST
Returnstrue
if this symbol table is empty, andfalse
otherwise.
-
size
public int size()
Description copied from interface:OrderedST
Returns the number of key-value pairs in this symbol table.
-
put
public void put(Key key, Value value)
Description copied from interface:OrderedST
Inserts thekey
andvalue
pair into this symbol table.
-
get
public Value get(Key key)
Description copied from interface:OrderedST
Returns the value associated withkey
in this symbol table, ornull
.
-
contains
public boolean contains(Key key)
Description copied from interface:OrderedST
Returnstrue
if this symbol table containskey
, andfalse
otherwise.
-
delete
public void delete(Key key)
Description copied from interface:OrderedST
Deleteskey
and the associated value from this symbol table.
-
keys
public Iterable<Key> keys()
Description copied from interface:OrderedST
Returns all the keys in this symbol table in sorted order.
-
min
public Key min()
Description copied from interface:OrderedST
Returns the smallest key in this symbol table.
-
max
public Key max()
Description copied from interface:OrderedST
Returns the largest key in this symbol table.
-
deleteMin
public void deleteMin()
Description copied from interface:OrderedST
Deletes the smallest key and the associated value from this symbol table.
-
deleteMax
public void deleteMax()
Description copied from interface:OrderedST
Deletes the largest key and the associated value from this symbol table.
-
floor
public Key floor(Key key)
Description copied from interface:OrderedST
Returns the largest key in this symbol table that is smaller than or equal tokey
.
-
ceiling
public Key ceiling(Key key)
Description copied from interface:OrderedST
Returns the smallest key in this symbol table that is larger than or equal tokey
.
-
rank
public int rank(Key key)
Description copied from interface:OrderedST
Returns the number of keys in this symbol table that are strictly smaller thankey
.
-
select
public Key select(int k)
Description copied from interface:OrderedST
Returns the key in this symbol table with the rankk
.
-
size
public int size(Key lo, Key hi)
Description copied from interface:OrderedST
Returns the number of keys in this symbol table that are in the interval[lo, hi]
.
-
keys
public Iterable<Key> keys(Key lo, Key hi)
Description copied from interface:OrderedST
Returns the keys in this symbol table that are in the interval[lo, hi]
in sorted order.
-
toString
public String toString()
Returns a string representation of this symbol table.
-
main
public static void main(String[] args)
Unit tests the data type.- Parameters:
args
- the command-line arguments.
-
-