線分データの数え上げ

今、N個のデータが得られるとする。そのデータは、１次元尺度上の線分に相当するデータであるものとする。簡単に言えば、aiからbiまでというようなデータが、N個得られるとする。このようなデータから、ある値xについて、[tex:ai<=x

package binaryTree;

/**
 *  2分探索木
 *
 *  @version $Revision: 1.6 $, $Date: 2003/04/28 23:23:14 $
 */

import java.io.*;



public class BinarySearchTreeRY {
    class Node {
        Node left, right;  double value;
        Node(Node left, Node right, double value) {
            this.left = left;  this.right = right;  this.value=value;
        }
        
    }

    final private Node
        zero = new Node(null, null,  -99),  // 各葉の子(番人用)
        rootParent = new Node(null, zero,  0);  // {\tt rootParent.right} が根
    private Node parent;  private boolean isChildLeft;  // 検索成功時の親


    public boolean isEmpty() { return (rootParent.right == zero); }

    public Node searchNode(double value) {  // 検索（未登録なら {\tt null} を返す）
         zero.value=-99; // {\tt zero} は番人
        Node child = rootParent;
        //int cmp = 1;  // 最初の子は {\tt rootParent.right}
        double cmp = 1;
        boolean loop=true;
        do {
            parent = child;
            if (cmp < 0) { child = child.left;  isChildLeft = true; }
            else         { child = child.right; isChildLeft = false; }
            //System.out.println("value="+value);
            //System.out.println("child.value="+child.value);
            if(child.value==-99){
            	loop=false;
            }else{
            	cmp=-value+child.value;
            	if(cmp==0){
                	loop=false;
                }
            }
            
        //} while ((cmp = key.compareTo(child.key)) != 0);
    	} while (loop);
        //System.out.println("childvalue="+child.value);
        return (child == zero) ? null : child;
    }

    public Node insertNode(double value) {  // 挿入（登録）
        if (searchNode(value) != null) return null;  // すでに登録されている

        Node newChild = new Node(zero, zero, value);
        if (isChildLeft) parent.left  = newChild;
        else             parent.right = newChild;
        return newChild;
    }

    public boolean deleteNode(double value) {  // 削除できれば {\tt true} を返す
        final Node target = searchNode(value);
        if (target == null) return false;  // 未登録

        Node newChild;  // {\tt target} の代わりに {\tt parent} の子になる
        if      (target.left  == zero) newChild = target.right;
        else if (target.right == zero) newChild = target.left;
        else {
            Node s = target.left;  // {\tt s} を {\tt target} の次に小さいものに
            if (s.right != zero) {
                Node p;  // {\tt s} の親
                do {  p = s;  s = s.right;  } while (s.right != zero);
                p.right = s.left;  s.left = target.left;
            }
            s.right = target.right;  newChild = s;
        }
        if (isChildLeft) parent.left  = newChild;
        else             parent.right = newChild;
        return true;  // 削除成功, C++ では {\tt delete target;} も必要
    }

    public void printNode() {
        if (!isEmpty()) printNode(rootParent.right);
    }

    private int depth = 0;
    private void printNode(Node p) { // 深さ優先探索,中間順でキーを表示
        if (p.left != zero) {
            depth++;  printNode(p.left);  depth--;
        }
        for (int i = 0; i < depth; i++) System.out.print("     ");
        
        System.out.println(p.value);
        if (p.right != zero) {
            depth++;  printNode(p.right);  depth--;
        }
    }

    public static void main(String[] args) throws IOException {
    	int n=10;
        double[] data=new double[n];
        for(int i=0;i<data.length;i++){
        	data[i]=Math.random();
        }
        BinarySearchTreeRY tree = new BinarySearchTreeRY();

        /*
        System.out.print("命令 Iabc:  abcを挿入\n"
                       + "     Dabc:  abcを削除\n"
                       + "     Sabc:  abcを検索\n");
                       */
        String message;
        for (int i=0;i<data.length;i++) {
        	
            double value=data[i];
        	if (tree.insertNode(value) != null)
                message = "登録しました.";
           else message = "登録ずみです.";
           //break;
           System.out.println(message);  tree.printNode();
        }
        int[] searchID={5,3,8};
        for(int i=0;i<searchID.length;i++){
        	if (tree.searchNode(data[searchID[i]]) != null)
                message = "登録されています.";
           else message = "登録されていません";
        	System.out.println(message);
        }
        double valueex=2;
        if (tree.searchNode(valueex) != null)
            message = "登録されています.";
       else message = "登録されていません";
    	System.out.println(message);
    	
    	int[] deleteID={6,3,9};
    	for(int i=0;i<deleteID.length;i++){
        	if (tree.deleteNode(data[deleteID[i]]))
        	     message = "削除しました.";
            else message = "登録されていません.";
        	System.out.println(message);
        }
    	
    	tree.printNode();
       /*
        for (int i=0;i<data.length;i++) {
            
            String message;
            double value=data[i];
            String insert="'I'";
            switch ('I') {
            case 'I':
                if (tree.insertNode(value) != null)
                     message = "登録しました.";
                else message = "登録ずみです.";
                break;
            case 'D':
                if (tree.deleteNode(value))
                     message = "削除しました.";
                else message = "登録されていません.";
                break;
            case 'S':
                if (tree.searchNode(value) != null)
                     message = "登録されています.";
                else message = "登録されていません";
                break;
            default:
                message = "使えるのは I, D, S です.";
                break;
            }
            System.out.println(message);  tree.printNode();
        }
        */
    }
}