Java Reference
In-Depth Information
1
/**
2
* Recursively construct a perfectly balanced BinarySearchTreeWithRank
3
* by repeated insertions in O( N log N ) time.
4
* t should be empty on the initial call.
5
*/
6
public static void buildTree( BinarySearchTreeWithRank<Integer> t,
7
int low, int high )
8
{
9
int center = ( low + high ) / 2;
10
11
if( low <= high )
12
{
13
t.insert( center );
14
15
buildTree( t, low, center - 1 );
16
buildTree( t, center + 1, high );
17
}
18
}
19
20
/**
21
* Return the winner in the Josephus problem.
22
* Search tree implementation.
23
*/
24
public static int josephus( int people, int passes )
25
{
26
BinarySearchTreeWithRank<Integer> t =
27
new BinarySearchTreeWithRank<Integer>( );
28
29
buildTree( t, 1, people );
30
31
int rank = 1;
32
while( people > 1 )
33
{
34
rank = ( rank + passes ) % people;
35
if( rank == 0 )
36
rank = people;
37
38
t.remove( t.findKth( rank ) );
39
people--;
40
}
41
42
return t.findKth( 1 );
43
}
figure 13.3
An
O
(
N
log
N
)
solution of the Josephus problem
Search WWH ::
Custom Search