/****************************/
/* 二分探索木 */
/* coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;
/********************/
/* クラスListの定義 */
/********************/
class List
{
int st;
List left, right;
// コンストラクタ
List ()
{
st = -1;
}
List (int s)
{
st = s;
}
/***************************************/
/* データの追加 */
/* dt : Listクラスのオブジェクト */
/* return : =1 : 追加 */
/* =0 : 同じデータが存在 */
/***************************************/
int add(List dt)
{
List lt = this;
int k, sw = -1;
// トップ
if (lt.st < 0) {
lt.st = dt.st;
sw = 1;
}
// トップでない
else {
while (sw < 0) {
k = dt.st - lt.st;
// 同じデータがある
if (k == 0)
sw = 0;
// 大きい
else if (k > 0) {
if (lt.right == null) {
lt.right = dt;
sw = 1;
}
else
lt = lt.right;
}
// 小さい
else {
if (lt.left == null) {
lt.left = dt;
sw = 1;
}
else
lt = lt.left;
}
}
}
return sw;
}
/***************************************/
/* データの削除 */
/* st : 数値 */
/* return : =1 : 削除した */
/* =0 : 削除できなかった */
/***************************************/
int del(int st)
{
List lt, lt1 = this, lt2 = this, dt;
int k, rl = 0, sw = 0;
if (lt2.st >= 0) {
while (sw == 0 && lt2 != null) {
k = st - lt2.st;
// 削除
if (k == 0) {
sw = 1;
if (lt2.right == null) {
// 子供無し
if (lt2.left == null) {
if (rl == 0)
lt2.st = -1;
else {
if (rl > 0)
lt1.right = null;
else
lt1.left = null;
}
}
// 右無し
else {
if (rl == 0) {
lt2.st = (lt2.left).st;
lt2.right = (lt2.left).right;
lt2.left = (lt2.left).left;
}
else {
if (rl > 0)
lt1.right = lt2.left;
else
lt1.left = lt2.left;
}
}
}
else {
// 左無し
if (lt2.left == null) {
if (rl == 0) {
lt2.st = (lt2.right).st;
lt2.left = (lt2.right).left;
lt2.right = (lt2.right).right;
}
else {
if (rl > 0)
lt1.right = lt2.right;
else
lt1.left = lt2.right;
}
}
// 左右あり
else {
dt = lt2.left;
if (rl == 0) {
lt = lt2.right;
lt2.st = lt.st;
lt2.right = lt.right;
lt2.left = lt.left;
}
else {
if (rl > 0)
lt1.right = lt2.right;
else
lt1.left = lt2.right;
}
lt1.add(dt);
}
}
}
// 次のデータ
else {
lt1 = lt2;
if (k > 0) {
lt2 = lt2.right;
rl = 1;
}
else {
lt2 = lt2.left;
rl = -1;
}
}
}
}
return sw;
}
/***********************************/
/* データの探索 */
/* st : 数値 */
/* return : =1 : 見つかった */
/* =0 : 見つからない */
/***********************************/
int search(int st)
{
List lt = this;
int k, sw = 0;
if (lt.st >= 0) {
while (sw == 0 && lt != null) {
k = st - lt.st;
// 見つかった
if (k == 0)
sw = 1;
// 次のデータ
else if (k > 0)
lt = lt.right;
else
lt = lt.left;
}
}
return sw;
}
/**********************/
/* リストデータの出力 */
/**********************/
void output()
{
List nt = this;
// 出力
if (nt.st >= 0) {
System.out.print(nt.st);
if (nt.right != null)
System.out.print(" right " + (nt.right).st);
if (nt.left != null)
System.out.print(" left " + (nt.left).st);
System.out.println();
// 次の出力
if (nt.right != null)
(nt.right).output();
if (nt.left != null)
(nt.left).output();
}
}
}
/****************/
/* main program */
/****************/
public class Test
{
public static void main (String[] args)
{
List base = new List ();
List lt;
int i1, k, ct = 0, sw, s[] = new int [100000];
long tm1, tm2, tm3;
Random rn = new Random((long)12345);
// データの追加
System.out.printf("二分探索木\n");
tm1 = System.currentTimeMillis();
while (ct < 5000000) {
k = rn.nextInt();
lt = new List (k);
sw = base.add(lt);
if (sw > 0) {
ct++;
if (ct < 100000)
s[ct] = k;
}
}
tm2 = System.currentTimeMillis();
System.out.printf(" 保存： %d ms\n", tm2-tm1);
// 探索
for (i1 = 0; i1 < 100000; i1++)
base.search(s[i1]);
tm3 = System.currentTimeMillis();
System.out.printf(" 探索： %d ms\n", tm3-tm2);
System.out.printf(" データ数： %d\n", ct);
}
}
--------------------------------------------------------------
/******************************/
/* 二分探索木(TreeSetの利用） */
/* coded by Y.Suganuma */
/******************************/
import java.io.*;
import java.util.*;
/****************/
/* main program */
/****************/
public class Test
{
public static void main (String[] args)
{
TreeSet <Integer> data = new TreeSet <Integer> ();
int i1, k, ct = 0, s[] = new int [100000];
boolean sw;
long tm1, tm2, tm3;
Random rn = new Random((long)12345);
// データの追加
System.out.printf("二分探索木(TreeSetの利用）\n");
tm1 = System.currentTimeMillis();
while (ct < 5000000) {
k = rn.nextInt();
sw = data.add(k);
if (sw) {
ct++;
if (ct < 100000)
s[ct] = k;
}
}
tm2 = System.currentTimeMillis();
System.out.printf(" 保存： %d ms\n", tm2-tm1);
// 探索
for (i1 = 0; i1 < 100000; i1++)
data.contains(s[i1]);
tm3 = System.currentTimeMillis();
System.out.printf(" 探索： %d ms\n", tm3-tm2);
System.out.printf(" データ数： %d\n", ct);
}
}