Search Tree implementation
Enviado por haroldalexitop • 26 de Noviembre de 2012 • Tesis • 1.042 Palabras (5 Páginas) • 325 Visitas
import java.util.Collection;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Iterator;
import weiss.nonstandard.BinarySearchTreeWithRank;
public final class Josephus
{
/**
* Return the winner in the Josephus problem.
* Linked list implementation.
* (Can replace with ArrayList or TreeSet).
*/
public static int jos1( int people, int passes )
{
Collection theList = new LinkedList( );
// Construct the list
for( int i = 1; i <= people; i++ )
theList.add( new Integer( i ) );
// Play the game;
Iterator itr = theList.iterator( );
while( people-- != 1 )
{
for( int i = 0; i <= passes; i++ )
{
if( !itr.hasNext( ) )
itr = theList.iterator( );
itr.next( );
}
itr.remove( );
}
itr = theList.iterator( );
return ( (Integer) itr.next( ) ).intValue( );
}
/**
* Recursively construct a perfectly balanced BinarySearchTreeWithRank
* by repeated insertions in O( N log N ) time.
* t should be empty on the initial call.
*/
public static void buildTree( BinarySearchTreeWithRank t,
int low, int high )
{
int center = ( low + high ) / 2;
if( low <=
...