Package dsa.lab07.solutions

Class BinarySearchTree<Key extends Comparable<Key>,Value>

java.lang.Object

dsa.lab07.solutions.BinarySearchTree<Key,Value>

Type Parameters:

Key - the key type

Value - the value type

All Implemented Interfaces:

Container<MapItem<Key,Value>>, Map<Key,Value>, OrderedMap<Key,Value>, Iterable<MapItem<Key,Value>>

Direct Known Subclasses:

AVLTree, AVLTree

public class BinarySearchTree<Key extends Comparable<Key>,Value>
extends Object
implements OrderedMap<Key,Value>

A binary search tree.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	BinarySearchTree.ItemIterator<Key extends Comparable<Key>,Value>
protected static class	BinarySearchTree.Node<Key extends Comparable<Key>,Value>	A node in a binary search tree.

Field Summary

Fields

Modifier and Type	Field	Description
protected BinarySearchTree.Node<Key,Value>	root	The root of the BST.
protected int	size	The number of nodes in the BST.

Constructor Summary

Constructors

Constructor	Description
BinarySearchTree()	Construct an empty binary search tree.
BinarySearchTree(DynamicArray<MapItem<Key,Value>> items)	Construct a binary search tree containing the given items.
BinarySearchTree(MapItem<Key,Value>... items)	Construct a binary search tree containing the given items.
BinarySearchTree(Iterable<MapItem<Key,Value>> items)	Construct a binary search tree containing the given items.
BinarySearchTree(Iterable<MapItem<Key,Value>> items, int size)	Construct a binary search tree containing the given items more efficiently than BinarySearchTree(Iterable).

Method Summary

Modifier and Type	Method	Description
MapItem<Key,Value>	find(Key key)	Find the item with the given key.
protected BinarySearchTree.Node<Key,Value>	findNode(Key key)	Find the node containing the item with the given key.
void	insert(MapItem<Key,Value> item)	Insert the given item.
Iterable<MapItem<Key,Value>>	items()	Get a forward iterable that yields each item once.
MapItem<Key,Value>	max()	Get the item with the greatest key.
MapItem<Key,Value>	min()	Get the item with the least key.
MapItem<Key,Value>	next(Key key)	Get the item that would be the successor of one with the given key.
MapItem<Key,Value>	previous(Key key)	Get the item that would be the predecessor of one with the given key.
MapItem<Key,Value>	remove(Key key)	Remove and return the item with the given key.
Iterable<MapItem<Key,Value>>	reversed()	Get a reverse iterable that yields each item once.
int	size()	Get the number of contained items.
String	toString()

Methods inherited from class java.lang.Object

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

Methods inherited from interface dsa.lab02.base.Container

contains, isEmpty, iterator

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface dsa.lab04.base.Map

containsKey, containsValue, get, insert, values

Methods inherited from interface dsa.lab05.base.OrderedMap

keys, reversedKeys

Field Details

root

protected BinarySearchTree.Node<Key extends Comparable<Key>,Value> root

The root of the BST. Null if empty.

size

protected int size

The number of nodes in the BST.

Constructor Details

BinarySearchTree

public BinarySearchTree()

Construct an empty binary search tree.

BinarySearchTree

public BinarySearchTree(Iterable<MapItem<Key,Value>> items)

Construct a binary search tree containing the given items.

Parameters:

items - the items

BinarySearchTree

public BinarySearchTree(Iterable<MapItem<Key,Value>> items,
 int size)

Construct a binary search tree containing the given items more efficiently than BinarySearchTree(Iterable).

Parameters:

items - the items

BinarySearchTree

@SafeVarargs
public BinarySearchTree(MapItem<Key,Value>... items)

Construct a binary search tree containing the given items.

Parameters:

items - the items

BinarySearchTree

public BinarySearchTree(DynamicArray<MapItem<Key,Value>> items)

Construct a binary search tree containing the given items.

Parameters:

items - the items

Method Details

size

public int size()

Description copied from interface: Container

Get the number of contained items.

Specified by:

size in interface Container<Key extends Comparable<Key>>

Returns:

the size

findNode

protected BinarySearchTree.Node<Key,Value> findNode(Key key)
                                             throws NoSuchElementException

Find the node containing the item with the given key.

Parameters:

key - the key

Returns:

the node

Throws:

NoSuchElementException - if no node has key key

find

public MapItem<Key,Value> find(Key key)
                        throws NoSuchElementException

Description copied from interface: Map

Find the item with the given key.

Specified by:

find in interface Map<Key extends Comparable<Key>,Value>

Parameters:

key - the item's key

Returns:

the item

Throws:

NoSuchElementException - if no item has key key

insert

public void insert(MapItem<Key,Value> item)

Description copied from interface: Map

Insert the given item.

If there's already an item with the same key, that item is replaced with this one.

This means that if the key was not already contained, the size is incremented, otherwise it isn't.

Specified by:

insert in interface Map<Key extends Comparable<Key>,Value>

Parameters:

item - the item

remove

public MapItem<Key,Value> remove(Key key)
                          throws NoSuchElementException

Description copied from interface: Map

Remove and return the item with the given key.

Decrements the size (assuming the item was actually in the map).

Specified by:

remove in interface Map<Key extends Comparable<Key>,Value>

Parameters:

key - the item's key

Returns:

the item

Throws:

NoSuchElementException - if key is not contained

previous

public MapItem<Key,Value> previous(Key key)

Description copied from interface: OrderedMap

Get the item that would be the predecessor of one with the given key.

The map may or may not contain an item with the given key.

Specified by:

previous in interface OrderedMap<Key extends Comparable<Key>,Value>

Parameters:

key - a key

Returns:

the previous item (by key), or null if there is none

next

public MapItem<Key,Value> next(Key key)

Description copied from interface: OrderedMap

Get the item that would be the successor of one with the given key.

The map may or may not contain an item with the given key.

Specified by:

next in interface OrderedMap<Key extends Comparable<Key>,Value>

Parameters:

key - a key

Returns:

the next item (by key), or null if there is none

min

public MapItem<Key,Value> min()

Description copied from interface: OrderedMap

Get the item with the least key.

Specified by:

min in interface OrderedMap<Key extends Comparable<Key>,Value>

Returns:

the minimum item (by key), or null if there is none

max

public MapItem<Key,Value> max()

Description copied from interface: OrderedMap

Get the item with the greatest key.

Specified by:

max in interface OrderedMap<Key extends Comparable<Key>,Value>

Returns:

the maximum item (by key), or null if there is none

toString

public String toString()

Overrides:

toString in class Object

items

public Iterable<MapItem<Key,Value>> items()

Description copied from interface: OrderedMap

Get a forward iterable that yields each item once.

The items are iterated over in least-to-greatest order (by key).

Specified by:

items in interface Container<Key extends Comparable<Key>>

Specified by:

items in interface OrderedMap<Key extends Comparable<Key>,Value>

Returns:

an iterable over the items

reversed

public Iterable<MapItem<Key,Value>> reversed()

Description copied from interface: OrderedMap

Get a reverse iterable that yields each item once.

The items are iterated over in greatest-to-least order (by key).

Specified by:

reversed in interface OrderedMap<Key extends Comparable<Key>,Value>

Returns:

an iterable over the items