student_classes

Class DenseSearchTree<T extends java.lang.Comparable<T>>

java.lang.Object

student_classes.DenseSearchTree<T>

Type Parameters:

T -

All Implemented Interfaces:

java.lang.Iterable<T>

public class DenseSearchTree<T extends java.lang.Comparable<T>>
extends java.lang.Object
implements java.lang.Iterable<T>

Non-Standard interpretation of a Binary Search Tree data-structure. Rather than inserting duplicate values along the left or right branches, this version maintains a count (int) (defaults to 1) that indicates how many "copies" of the key are available on this node. Should the count go to 0, then the node is physically removed from the tree. This simplifies our remove logic in that we don't have to account for duplicate keys.

Author:

UMD CS Dept.

Constructor Summary

Constructors

Constructor and Description
DenseSearchTree()

Method Summary

Modifier and Type	Method and Description
void	add(T element) Note: our trees follow a slightly different convention regarding both our ordering relation and the placement of duplicates, viz:
java.util.Set<T>	asSet() Returns the set representation of this Tree.
boolean	contains(T target) Returns true if at least instance of target is found in tree.
int	count(T target) Returns an int greater than or equal to 0, indicating how many occurrences of target reside in the tree.
T	getMax() Returns the max value (of type T), or throws an IllegalStateException if this function is called on an empty tree.
T	getMin() Returns a value of type T or throws an IllegalStateException if this function is called on an empty tree.
java.util.Iterator<T>	iterator() Returns an iterator over the DenseSearchTree.
void	remove(T target) Somewhat streamlined or simplified version of the classic BST remove algorithm.
int	size() Returns "inflated" size of tree, meaning a count of all keys in the tree.
java.lang.String	toString() For sanity's sake ...

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

DenseSearchTree

public DenseSearchTree()

Method Detail

add

public void add(T element)

Note: our trees follow a slightly different convention regarding both our ordering relation and the placement of duplicates, viz:

• Left branch contains all elements less than tree.value;
• Right branch contains all elements greater than tree.value.

Rather than place duplicate elements on the right branch, each Tree Node maintains a count of copies. For example, if we had a tree of Integers containing two instances of the number 1, our Tree Node would logically appear as

[ left-branch 1:2 right-branch ],

where 1:2 means 2 copies of the integer 1.

Thus, your add logic will either make a new node and insert it in the correct position in the tree, or it will find a node with the value (key) equal to the value you are adding, and increment its count.

This simplifies your remove logic: if the node's count is greater than 0, then decrement by 1, otherwise invoke the remove logic to physically remove the node and replace it with a Binary Search Tree.

Finally, the "price you pay" for this simplification is that your Iterator (which presents an "in-order" view of the tree), needs to "inflate" or "expand" each node. That is, if you have a node

[ left 3:4 right ]

then 4 instances of the integer 3 need to be created and put into the iteration.

Parameters:

element -

contains

public boolean contains(T target)

Returns true if at least instance of target is found in tree.

Parameters:

target -

Returns:

count

public int count(T target)

Returns an int greater than or equal to 0, indicating how many occurrences of target reside in the tree. Note, this function returns 0 when the item is not found in tree.

Parameters:

target -

Returns:

size

public int size()

Returns "inflated" size of tree, meaning a count of all keys in the tree.

Returns:

asSet

public java.util.Set<T> asSet()

Returns the set representation of this Tree. In this case, the set will contain unique elements (i.e., it should omit multiple instances) that comprise the tree.

Note: sets are unordered collections, but trees are partial orderings. This means, among other things, that your set may reflect an internal ordering, such as pre-, in- or post-ordering, but it need not.

Returns:

remove

public void remove(T target)

Somewhat streamlined or simplified version of the classic BST remove algorithm. Because we're maintaining counts of keys on each node, many times this method finds the node whose value (key) equals the target and decrements the counter by 1. If that would result in the counter going to 0, however, then the remove logic finds the greatest in order successor and replaces the node to be removed with that, and then continues to remove the in order successor whose value was used to re-label the node to be removed.
Note: throws an IllegalStateException if the target is not found in the tree.

Parameters:

target -

getMin

public T getMin()

Returns a value of type T or throws an IllegalStateException if this function is called on an empty tree.

Returns:

getMax

public T getMax()

Returns the max value (of type T), or throws an IllegalStateException if this function is called on an empty tree.

Returns:

toString

public java.lang.String toString()

For sanity's sake ... please feel free to implement whatever makes sense to you here ... this method is NOT tested.

Overrides:

toString in class java.lang.Object

iterator

public java.util.Iterator<T> iterator()

Returns an iterator over the DenseSearchTree.

Note, this iterator must present an "in order" view of the keys in the tree.

Specified by:

iterator in interface java.lang.Iterable<T extends java.lang.Comparable<T>>