Package dsa.lab07.exercises

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

java.lang.Object

dsa.lab07.exercises.BinarySearchTree.Node<Key,Value>

Type Parameters:

Key - the key type

Value - the value type

Enclosing class:

BinarySearchTree<Key extends Comparable<Key>,Value>

protected static class BinarySearchTree.Node<Key extends Comparable<Key>,Value>
extends Object

A node in a binary search tree.

Field Summary

Fields

Modifier and Type	Field	Description
MapItem<Key,Value>	item
BinarySearchTree.Node<Key,Value>	left
BinarySearchTree.Node<Key,Value>	parent
BinarySearchTree.Node<Key,Value>	right
BinarySearchTree<Key,Value>	tree

Constructor Summary

Constructors

Constructor	Description
Node(BinarySearchTree.Node<Key,Value> parent, BinarySearchTree<Key,Value> tree, BinarySearchTree.Node<Key,Value> left, MapItem<Key,Value> item, BinarySearchTree.Node<Key,Value> right)

Method Summary

Modifier and Type	Method	Description
BinarySearchTree.Node<Key,Value>	findNode(Key key)	Find the node containing the item with the given key within this subtree.
BinarySearchTree.Node<Key,Value>	insert(MapItem<Key,Value> item)	Insert the given item within this subtree.
MapItem<Key,Value>	max()	Get the item in this subtree with the greatest key.
BinarySearchTree.Node<Key,Value>	maxNode()	Get the node in this subtree with the greatest key.
MapItem<Key,Value>	min()	Get the item in this subtree with the least key.
BinarySearchTree.Node<Key,Value>	minNode()	Get the node in this subtree with the least key.
MapItem<Key,Value>	next(Key key)	Get the item within this subtree that would be the successor of one with the given key.
MapItem<Key,Value>	previous(Key key)	Get the item within this subtree that would be the predecessor of one with the given key.
BinarySearchTree.Node<Key,Value>	remove()	Remove the item that this node contains from the tree, and return the node removed.

Methods inherited from class java.lang.Object

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

Field Details

parent

public BinarySearchTree.Node<Key extends Comparable<Key>,Value> parent

tree

public BinarySearchTree<Key extends Comparable<Key>,Value> tree

left

public BinarySearchTree.Node<Key extends Comparable<Key>,Value> left

item

public MapItem<Key extends Comparable<Key>,Value> item

right

public BinarySearchTree.Node<Key extends Comparable<Key>,Value> right

Constructor Details

Node

public Node(BinarySearchTree.Node<Key,Value> parent,
 BinarySearchTree<Key,Value> tree,
 BinarySearchTree.Node<Key,Value> left,
 MapItem<Key,Value> item,
 BinarySearchTree.Node<Key,Value> right)

Method Details

findNode

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

Find the node containing the item with the given key within this subtree.

Parameters:

key - the key

Returns:

the node

Throws:

NoSuchElementException - if no node has key key

insert

public BinarySearchTree.Node<Key,Value> insert(MapItem<Key,Value> item)

Insert the given item within this subtree.

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

If instead there isn't already an item with the same key, a new node is inserted and returned.

Parameters:

item - the item

Returns:

the node containing the item, once inserted

remove

public BinarySearchTree.Node<Key,Value> remove()

Remove the item that this node contains from the tree, and return the node removed.

The removed node is only this node if this is a leaf.

If this node isn't a leaf, find a suitable leaf node (if this has a left subtree, then its maximum node, otherwise the right subtree's minimum), copy its item into this node, and remove and return that node.

Returns:

the removed node

previous

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

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

There may or may not be an item with the given key.

Parameters:

key - a key

Returns:

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

next

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

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

There may or may not be an item with the given key.

Parameters:

key - a key

Returns:

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

minNode

public BinarySearchTree.Node<Key,Value> minNode()

Get the node in this subtree with the least key.

Returns:

the minimum node (the leftmost descendant)

maxNode

public BinarySearchTree.Node<Key,Value> maxNode()

Get the node in this subtree with the greatest key.

Returns:

the maximum node (the rightmost descendant)

min

public MapItem<Key,Value> min()

Get the item in this subtree with the least key.

Returns:

the minimum item (by key)

max

public MapItem<Key,Value> max()

Get the item in this subtree with the greatest key.

Returns:

the maximum item (by key)