RandomizedTree (Crater Dog Java Collection Framework 3.6 API)

java.lang.Object
- java.util.AbstractCollection<E>
- - craterdog.collections.primitives.RandomizedTree<E>

Type Parameters:

E - The type of the elements in the tree.

All Implemented Interfaces:

java.lang.Cloneable, java.lang.Iterable<E>, java.util.Collection<E>
```
public final class RandomizedTree<E>
extends java.util.AbstractCollection<E>
implements java.lang.Cloneable
```
This class provides an implementation of the randomized binary search tree (RBST). The approach was defined by CONRADO MART ́INEZ And SALVADOR ROURA in their paper published in Journal of the ACM, Vol. 45, No. 2, March 1998, pp. 288–323. It implements a standard binary search tree but uses random choices to keep the tree statically balanced after each insertion or deletion. All nodes in the tree have an equal probability of being the root node. This implementation is configurable such that it allows the programmer to specify whether or not duplicate entities are allowed in the tree. Since this is a binary tree it implements an ordered collection.

Author:

Derk Norton

Constructor Summary

Constructors
Constructor and Description
`RandomizedTree()` This default constructor creates an instance of a tree that does not allow duplicate elements and uses the default comparison mechanism.
`RandomizedTree(boolean duplicatesAllowed)` This constructor creates an instance of a tree that uses the default comparison mechanism and allows the caller to specify whether duplicates are allowed.
`RandomizedTree(boolean duplicatesAllowed, java.util.Comparator<? super E> comparator)` This constructor creates an instance of a tree that uses the specified comparator for ordering the elements in the tree and allows the caller to specify whether duplicates are allowed.
`RandomizedTree(java.util.Collection<? extends E> elements)` This constructor creates an instance of a tree that does not allow duplicate elements and uses the default comparison mechanism.
`RandomizedTree(java.util.Collection<? extends E> elements, boolean duplicatesAllowed)` This constructor creates an instance of a tree that uses the default comparison mechanism and allows the caller to specify whether duplicates are allowed.
`RandomizedTree(java.util.Collection<? extends E> elements, boolean duplicatesAllowed, java.util.Comparator<? super E> comparator)` This constructor creates an instance of a tree that uses the specified comparator for ordering the elements in the tree and allows the caller to specify whether duplicates are allowed.
`RandomizedTree(java.util.Collection<? extends E> elements, java.util.Comparator<? super E> comparator)` This constructor creates an instance of a tree that does not allow duplicate elements and uses the specified comparator for ordering the elements in the tree.
`RandomizedTree(java.util.Comparator<? super E> comparator)` This constructor creates an instance of a tree that does not allow duplicate elements and uses the specified comparator for ordering the elements in the tree.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`boolean`	`add(E newElement)`
`void`	`clear()`
`java.lang.Object`	`clone()`
`java.util.Comparator<? super E>`	`comparator()` This method returns the comparator that is used to order the elements in this collection.
`boolean`	`contains(java.lang.Object element)`
`boolean`	`equals(java.lang.Object object)`
`E`	`get(int index)` This method returns the element with the specified index.
`int`	`hashCode()`
`int`	`indexOf(E element)` This method returns the index of the specified element or -1 if the element does not exist in the collection.
`java.util.ListIterator<E>`	`iterator()`
`java.util.ListIterator<E>`	`listIterator()` This method returns an iterator for the collection which is currently pointing at the slot right before the first element.
`java.util.ListIterator<E>`	`listIterator(int index)` This method returns an iterator for the collection which is currently pointing at the slot right before the specified index.
`boolean`	`remove(java.lang.Object oldElement)`
`int`	`size()`

Methods inherited from class java.util.AbstractCollection
addAll, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection
parallelStream, removeIf, spliterator, stream

Methods inherited from interface java.lang.Iterable
forEach

- Constructor Detail
  - RandomizedTree
```
public RandomizedTree()
```
    This default constructor creates an instance of a tree that does not allow duplicate elements and uses the default comparison mechanism.
  - RandomizedTree
```
public RandomizedTree(boolean duplicatesAllowed)
```
    This constructor creates an instance of a tree that uses the default comparison mechanism and allows the caller to specify whether duplicates are allowed.
    
    Parameters:
    
    duplicatesAllowed - Whether or not duplicate elements are allowed in the tree.
  - RandomizedTree
```
public RandomizedTree(java.util.Comparator<? super E> comparator)
```
    This constructor creates an instance of a tree that does not allow duplicate elements and uses the specified comparator for ordering the elements in the tree.
    
    Parameters:
    
    comparator - The comparator to be used to order the elements in the tree.
  - RandomizedTree
```
public RandomizedTree(boolean duplicatesAllowed,
                      java.util.Comparator<? super E> comparator)
```
    This constructor creates an instance of a tree that uses the specified comparator for ordering the elements in the tree and allows the caller to specify whether duplicates are allowed.
    
    Parameters:
    
    duplicatesAllowed - Whether or not duplicate elements are allowed in the tree.
    
    comparator - The comparator to be used to order the elements in the tree.
  - RandomizedTree
```
public RandomizedTree(java.util.Collection<? extends E> elements)
```
    This constructor creates an instance of a tree that does not allow duplicate elements and uses the default comparison mechanism. The specified elements are used to seed the tree.
    
    Parameters:
    
    elements - The elements that should be used to seed the tree.
  - RandomizedTree
```
public RandomizedTree(java.util.Collection<? extends E> elements,
                      boolean duplicatesAllowed)
```
    This constructor creates an instance of a tree that uses the default comparison mechanism and allows the caller to specify whether duplicates are allowed. The specified elements are used to seed the tree.
    
    Parameters:
    
    elements - The elements that should be used to seed the tree.
    
    duplicatesAllowed - Whether or not duplicate elements are allowed in the tree.
  - RandomizedTree
```
public RandomizedTree(java.util.Collection<? extends E> elements,
                      java.util.Comparator<? super E> comparator)
```
    This constructor creates an instance of a tree that does not allow duplicate elements and uses the specified comparator for ordering the elements in the tree. The specified elements are used to seed the tree.
    
    Parameters:
    
    elements - The elements that should be used to seed the tree.
    
    comparator - The comparator to be used to order the elements in the tree.
  - RandomizedTree
```
public RandomizedTree(java.util.Collection<? extends E> elements,
                      boolean duplicatesAllowed,
                      java.util.Comparator<? super E> comparator)
```
    This constructor creates an instance of a tree that uses the specified comparator for ordering the elements in the tree and allows the caller to specify whether duplicates are allowed. The specified elements are used to seed the tree.
    
    Parameters:
    
    elements - The elements that should be used to seed the tree.
    
    duplicatesAllowed - Whether or not duplicate elements are allowed in the tree.
    
    comparator - The comparator to be used to order the elements in the tree.
- Method Detail
  - size
```
public int size()
```
    Specified by:
    
    size in interface java.util.Collection<E>
    
    Specified by:
    
    size in class java.util.AbstractCollection<E>
  - contains
```
public boolean contains(java.lang.Object element)
```
    Specified by:
    
    contains in interface java.util.Collection<E>
    
    Overrides:
    
    contains in class java.util.AbstractCollection<E>
  - get
```
public E get(int index)
```
    This method returns the element with the specified index.
    
    Parameters:
    
    index - The index of the element to be returned.
    
    Returns:
    
    The element at the specified index.
  - indexOf
```
public int indexOf(E element)
```
    This method returns the index of the specified element or -1 if the element does not exist in the collection.
    
    Parameters:
    
    element - The element to be searched for.
    
    Returns:
    
    The index of the element or -1 if it was not found.
  - add
```
public boolean add(E newElement)
```
    Specified by:
    
    add in interface java.util.Collection<E>
    
    Overrides:
    
    add in class java.util.AbstractCollection<E>
  - remove
```
public boolean remove(java.lang.Object oldElement)
```
    Specified by:
    
    remove in interface java.util.Collection<E>
    
    Overrides:
    
    remove in class java.util.AbstractCollection<E>
  - clear
```
public void clear()
```
    Specified by:
    
    clear in interface java.util.Collection<E>
    
    Overrides:
    
    clear in class java.util.AbstractCollection<E>
  - iterator
```
public java.util.ListIterator<E> iterator()
```
    Specified by:
    
    iterator in interface java.lang.Iterable<E>
    
    Specified by:
    
    iterator in interface java.util.Collection<E>
    
    Specified by:
    
    iterator in class java.util.AbstractCollection<E>
  - listIterator
```
public java.util.ListIterator<E> listIterator()
```
    This method returns an iterator for the collection which is currently pointing at the slot right before the first element.
    
    Returns:
    
    A list iterator pointing at the slot before the first element.
  - listIterator
```
public java.util.ListIterator<E> listIterator(int index)
```
    This method returns an iterator for the collection which is currently pointing at the slot right before the specified index.
    
    Parameters:
    
    index - The index before the next element in the collection to be returned by the iterator.
    
    Returns:
    
    A list iterator pointing at the slot before the element referenced by the specified index.
  - comparator
```
public java.util.Comparator<? super E> comparator()
```
    This method returns the comparator that is used to order the elements in this collection.
    
    Returns:
    
    The comparator that is used to order the elements in this collection.
  - equals
```
public boolean equals(java.lang.Object object)
```
    Specified by:
    
    equals in interface java.util.Collection<E>
    
    Overrides:
    
    equals in class java.lang.Object
  - hashCode
```
public int hashCode()
```
    Specified by:
    
    hashCode in interface java.util.Collection<E>
    
    Overrides:
    
    hashCode in class java.lang.Object
  - clone
```
public java.lang.Object clone()
```
    Overrides:
    
    clone in class java.lang.Object

Class RandomizedTree<E>

Constructor Summary

Method Summary

Methods inherited from class java.util.AbstractCollection

Methods inherited from class java.lang.Object

Methods inherited from interface java.util.Collection

Methods inherited from interface java.lang.Iterable

Constructor Detail

RandomizedTree

RandomizedTree

RandomizedTree

RandomizedTree

RandomizedTree

RandomizedTree

RandomizedTree

RandomizedTree

Method Detail

size

contains

get

indexOf

add

remove

clear

iterator

listIterator

listIterator

comparator

equals

hashCode

clone