Package dsa.lab07.exercises
Class BinarySearchTree<Key extends Comparable<Key>,Value>
java.lang.Object
dsa.lab07.exercises.BinarySearchTree<Key,Value>
- Type Parameters:
Key
- the key typeValue
- the value type
- All Implemented Interfaces:
Container<MapItem<Key,
,Value>> Map<Key,
,Value> OrderedMap<Key,
,Value> Iterable<MapItem<Key,
Value>>
public class BinarySearchTree<Key extends Comparable<Key>,Value>
extends Object
implements OrderedMap<Key,Value>
A binary search tree.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic 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 -
Constructor Summary
ConstructorsConstructorDescriptionConstruct 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 thanBinarySearchTree(Iterable)
. -
Method Summary
Modifier and TypeMethodDescriptionFind the item with the given key.protected BinarySearchTree.Node
<Key, Value> Find the node containing the item with the given key.void
Insert the given item.items()
Get a forward iterable that yields each item once.max()
Get the item with the greatest key.min()
Get the item with the least key.Get the item that would be the successor of one with the given key.Get the item that would be the predecessor of one with the given key.Remove and return the item with the given key.reversed()
Get a reverse iterable that yields each item once.int
size()
Get the number of contained items.toString()
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
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
-
size
protected int size
-
-
Constructor Details
-
BinarySearchTree
public BinarySearchTree()Construct an empty binary search tree. -
BinarySearchTree
Construct a binary search tree containing the given items.- Parameters:
items
- the items
-
BinarySearchTree
Construct a binary search tree containing the given items more efficiently thanBinarySearchTree(Iterable)
.- Parameters:
items
- the items
-
BinarySearchTree
Construct a binary search tree containing the given items.- Parameters:
items
- the items
-
BinarySearchTree
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 interfaceContainer<Key extends Comparable<Key>>
- Returns:
- the size
-
findNode
Find the node containing the item with the given key.- Parameters:
key
- the key- Returns:
- the node
- Throws:
NoSuchElementException
- if no node has keykey
-
find
Description copied from interface:Map
Find the item with the given key.- Specified by:
find
in interfaceMap<Key extends Comparable<Key>,
Value> - Parameters:
key
- the item's key- Returns:
- the item
- Throws:
NoSuchElementException
- if no item has keykey
-
insert
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.
-
remove
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 interfaceMap<Key extends Comparable<Key>,
Value> - Parameters:
key
- the item's key- Returns:
- the item
- Throws:
NoSuchElementException
- ifkey
is not contained
-
previous
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 interfaceOrderedMap<Key extends Comparable<Key>,
Value> - Parameters:
key
- a key- Returns:
- the previous item (by key), or
null
if there is none
-
next
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 interfaceOrderedMap<Key extends Comparable<Key>,
Value> - Parameters:
key
- a key- Returns:
- the next item (by key), or
null
if there is none
-
min
Description copied from interface:OrderedMap
Get the item with the least key.- Specified by:
min
in interfaceOrderedMap<Key extends Comparable<Key>,
Value> - Returns:
- the minimum item (by key), or
null
if there is none
-
max
Description copied from interface:OrderedMap
Get the item with the greatest key.- Specified by:
max
in interfaceOrderedMap<Key extends Comparable<Key>,
Value> - Returns:
- the maximum item (by key), or
null
if there is none
-
toString
-
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 interfaceContainer<Key extends Comparable<Key>>
- Specified by:
items
in interfaceOrderedMap<Key extends Comparable<Key>,
Value> - Returns:
- an iterable over the items
-
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 interfaceOrderedMap<Key extends Comparable<Key>,
Value> - Returns:
- an iterable over the items
-