自作した二分探索木で挿入や検索をしたいのですが行き詰まっています。

Question

前提・実現したいこと

現在、Javaの勉強に取り組んでいます。

自作した二分探索木でデータの挿入や検索を行いたいです。
どのようにすれば、適切な処理を行うことができるでしょうか？

発生している問題・エラーメッセージ

はじめに、1からnまでの整数をint型の配列arrayにランダムに入れます。
ランダムに並んだ整数を二分探索木の適当な場所に挿入するために自作したメソッドinsert()を
使いたいです。しかし、このinsert()について次のエラーが表示されます。

エラーメッセージ
insertに適切なメソッドが見つかりません(int)
                tree.insert(array[i]);
                    ^
    メソッド BinSearchTree.insert(Entry<Integer,Object>)は使用できません
      (引数の不一致: intをEntry<Integer,Object>に変換できません:)
    メソッド BinSearchTree.insert(BinSearchTreeNode<Integer,Object>,Entry<Integer,Object>)は使用できません
      (実引数リストと仮引数リストの長さが異なります)
エラー1個

該当のソースコード

メインのクラスです。

package genericSearch;

import java.util.Comparator;
import java.util.Iterator;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;
import genericSearch.*;

public class Main {

    @SuppressWarnings("resource")
    public static void main(String[] args) {

        BinSearchTree<Integer, Object> tree =
            new BinSearchTree<Integer, Object>(
                new Comparator<Integer>() {
                    public int compare(Integer a, Integer b){
                        return b - a;
                    }
                }
            );

        int n;
        Scanner keyboard = new Scanner(System.in);
        
        System.out.println("#integers: ");
        n = keyboard.nextInt();
        int[] array = new int[n];
        for(int i = 0; i < n; i++) {
            array[i] = i + 1;
        }
        Random rand = new Random();
        for(int i = 0; i < n; i++) {
            int j = rand.nextInt(n - i);
            int temp = array[n - 1 - i];
            array[n - 1 - i] = array[j];
            array[j] = temp;
        }

        for (int i = 0 ; i < n ; i++) {
    		//System.out.print(array[i] + " ");
    		tree.insert(array[i]);
    	}
    	System.out.println("") ;

        int m = rand.nextInt(n) ;
        System.out.println("trying to find " + m + " ...");
        if(tree.search(m) != null) {
            System.out.println("found " + m) ; //結果表示
        	System.out.println("") ;
        }

        System.out.println("") ;

		/**
    	//木にあるデータのキーを指定順に表示する．
    	Set<Integer> keys = tree.keySet() ;
    	System.out.println("data in sorted order:");
    	Iterator<Integer> iter = keys.iterator() ;
    	while (iter.hasNext()) {
            System.out.print(iter.next() + " ");
        }
         */
    }
    
}

探索木に対して処理を行うクラスです。

package genericSearch;

import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

//Kはデータのキーの型，Vはデータの値の型
public class BinSearchTree<K,V> {
	private BinSearchTreeNode<K,V> root ;
	private Comparator<K> comparator ;

	//引数なしのコンストラクタを禁止．
	@SuppressWarnings("all")
	private BinSearchTree( ) { }

	//引数ありのコンストラクタ．
	public BinSearchTree(Comparator<K> comparator) {
		this.comparator = comparator ;
	}

	//空の木か否かを判定するメソッド
	public boolean isEmpty() {
		return root == null;
	}

	//この木において指定キーを持つデータを検索するメソッド
	public V search(K key) {
		return search(root, key);
	}


	//startを根とする木において指定キーを持つデータを検索するメソッド
	private V search(BinSearchTreeNode<K,V> start, K key) {
		//if (start == null) return null ; //木が空の場合

		while(start != null) {
			if(comparator.compare(key, start.getData().getKey()) == 0){
				return start.getData().getValue();
			}

			else if(comparator.compare(key, start.getData().getKey()) < 0){
				start = start.getLeft();
			}
			else{
				start = start.getRight();
			}
		}

		return null;
	}


	//この木において指定キーを持つデータを検索するメソッド
	public void insert(Map.Entry<K,V> data) {
		root = insert(root, data);
	}


	//startを根とする木に新しいデータを挿入してから，結果の木を返すメソッド
	private BinSearchTreeNode<K,V> insert(BinSearchTreeNode<K,V> start, Map.Entry<K,V> data) {
		//易しい場合：空の木の場合
		if (start == null) {
			return new BinSearchTreeNode<K,V>(data) ;
		}

		while(true) {
			if(comparator.compare(start.getData().getKey(), data.getKey()) < 0) {
				if(start.getLeft() == null) {
					start.setLeft(new BinSearchTreeNode<K, V>(data));
				}
				else {
					start = start.getLeft();
				}
			}
			else {
				if(start.getRight() == null) {
					start.setRight(new BinSearchTreeNode<K, V>(data));
				}
				else {
					start = start.getRight();
				}
			}
		}
	}


	//木から指定のキーを持つデータを削除してから，結果の木を返すメソッド
	public void delete(K key) {
		root = delete(root, key);
	}

	
	//木から指定のキーを持つデータを削除してから，結果の木を返すメソッド
	private BinSearchTreeNode<K,V> delete(BinSearchTreeNode<K,V> start, K key) {
		//木が空のとき，そのまま返す
		if (start == null) return null ;

		if(start.isLeaf()) {
			return null;
		}
		if(start.getLeft() == null) {
			return start.getRight();
		}
		if(start.getRight() == null) {
			return start.getLeft();
		}
		else {
			BinSearchTreeNode<K,V> p = start.getRight();
			while(p.getLeft() != null) {
				p = p.getLeft();
			}
			Map.Entry<K,V> nextBigData = p.getData();

			start.setRight( delete(start.getRight(), nextBigData.getKey()) );
			start.setData(nextBigData) ;
			return start ;
		}
	}
	

	//preorderの順に2分探索木にあるデータをたどるためのメソッド
	public Iterator<Map.Entry<K,V>> preorderIterator() {
		return preorder(root).iterator();
	}

	//preorderIterator内でしか呼び出されない再帰メソッド
	private List<Map.Entry<K,V>> preorder(BinSearchTreeNode<K,V> start) {
		List<Map.Entry<K,V>> list = new LinkedList<Map.Entry<K,V>>() ;
		if (start == null) return list ;
		else {
			list.add(start.getData()) ;
			list.addAll(preorder(start.getLeft())) ;
			list.addAll(preorder(start.getRight())) ;
			return list ;
		}
	}

	//inorderの順に2分探索木にあるデータをたどるためのメソッド
	public Iterator<Map.Entry<K,V>> inorderIterator() {
		return inorder(root).iterator();
	}

	//inorderIterator内でしか呼び出されない再帰メソッド
	private List<Map.Entry<K,V>> inorder(BinSearchTreeNode<K,V> start) {
		List<Map.Entry<K,V>> list = new LinkedList<Map.Entry<K,V>>() ;
		if (start == null) return list ;
		else {
			list.addAll(inorder(start.getLeft())) ;
			list.add(start.getData()) ;
			list.addAll(inorder(start.getRight())) ;
			return list ;
		}
	}

	//postorderの順に2分探索木にあるデータをたどるためのメソッド
	public Iterator<Map.Entry<K,V>> postorderIterator() {
		return postorder(root).iterator();
	}

	//postorderIterator内でしか呼び出されない再帰メソッド
	private List<Map.Entry<K,V>> postorder(BinSearchTreeNode<K,V> start) {
		List<Map.Entry<K,V>> list = new LinkedList<Map.Entry<K,V>>() ;
		if (start == null) return list ;
		else {
			list.addAll(postorder(start.getLeft())) ;
			list.addAll(postorder(start.getRight())) ;
			list.add(start.getData()) ;
			return list ;
		}
	}

	//accessorメソッド
	public BinSearchTreeNode<K,V> getRoot() {
		return root ;
	}
	public void setRoot(BinSearchTreeNode<K,V> root) {
		this.root = root ;
	}
}

package genericSearch;

import java.util.Map;

//Kはデータのキーの型，Vはデータの値の型
public class BinSearchTreeNode<K,V> {
	private Map.Entry<K,V> data ;
	private BinSearchTreeNode<K,V> left, right ;

	//コンストラクタ
	public BinSearchTreeNode(Map.Entry<K,V> data, BinSearchTreeNode<K,V> left,
			BinSearchTreeNode<K,V> right) {
		this.data = data ;
		this.left = left ;
		this.right = right ;
	}

	//葉を作るためのコンストラクタ
	public BinSearchTreeNode(Map.Entry<K,V> data) {
		this(data, null, null) ;
	}

	//葉か否かを判定するメソッド
	public boolean isLeaf() {
		return left == null && right == null ;
	}


	//accessorメソッド
	public Map.Entry<K,V> getData() {
		return data ;
	}
	public BinSearchTreeNode<K,V> getLeft() {
		return left ;
	}
	public BinSearchTreeNode<K,V> getRight() {
		return right ;
	}
	public void setData(Map.Entry<K,V> data) {
		this.data = data ;
	}
	public void setLeft(BinSearchTreeNode<K,V> left) {
		this.left = left ;
	}
	public void setRight(BinSearchTreeNode<K,V> right) {
		this.right = right ;
	}
}

Comments

[YT0014]

BinSearchTreeNodeのコードがないので、実証や確認ができません。質問欄を修正して、追記をお願いいたします。

[karasu116]

申し訳ありませんでした。いま追記しましたのでご確認お願いいたします。

[YT0014]

追記ありがとうございます。
修正してエラーが出ているのなら、Mainの更新もご考慮ください。

Answer 1

やりたいことが明確になっていないのが原因です。

二分探索木の宣言では、キーがInteger、データがObjectです。
ですが、格納したいのは、intの配列です。

コード上でも、質問欄でも、探索木の要素が不明確です。
intの配列をキーの配列とみなすのならば、データは何でしょうか？

例えば、BinSearchTreeの動作確認のために、int配列の処理を確認したいのでしたら、キー、データともIntegerで宣言して、Map.Entry変数のキーと値の両方に配列の値を設定してから、それをinsert()するという手順が必要かと思います。

コメントに対する追記
まず、Map.Entryは、インターフェースです。実装クラスなどの情報は、javadocをご確認ください。

javadocに記載されている実装クラスを使用されるのなら、コンストラクタ(new クラス名()の形式で呼ばれる処理)の引数２つに、配列の要素を積むことになります。

Comments

[karasu116]

回答ありがとうございます。
先日大学の授業で取り扱ったばかりの内容でして、お恥ずかしい話、二分探索木の基本中の基本もわからない状況でございます。

>> BinSearchTreeの動作確認のために、int配列の処理を確認したいのでしたら、キー、データともIntegerで宣言して・・・

BinSearchTree<Integer, Object> tree =
new BinSearchTree<Integer, Object>

の部分のObjectをIntegerに変えればいいのでしょうか？

>> Map.Entiry変数のキーと値の両方に配列の値を設定してから、それをinsert()するという手順が必要かと思います。

具体的な例として一つ上げていただくと大変助かります。

[karasu116]

Map.Entry変数はMap.Entry<Integer, Object> mp;
として、mp.setValue(array[i]); tree.insert(mp);
のようにしたらこれまでのエラーは消えましたが、mpが初期化されていない旨のエラーがでました。
どのように初期化すればいいでしょうか。

[YT0014]

回答に追記しました。
ただ、初期化は、javaの基本なので言及しておりませんでしたが、最初の回答に、"キーと値の両方に配列の値を設定"と記してあったのですが、なぜsetValue()だけなのでしょうか？
また、"自作"とありますが、理解しないままどうやって作成したのでしょうか？サンプルを打ち込んだだけですか？
プログラミングを学ぶのなら、仕様などの文言は、一切の曖昧さがない状態まで読み込んでください。また、発する言葉も、精確に使うように心がけてください。

[karasu116]

追記ありがとうございました。

>> まず、Map.Entryは、インターフェースです。実装クラスなどの情報は、javadocをご確認ください。

javadocに記載されている実装クラスを使用されるのなら、コンストラクタ(new クラス名()の形式で呼ばれる処理)の引数２つに、配列の要素を積むことになります。

実装されているクラスはAbstractMap.SimpleEntry, AbstractMap.SimpleImmutableEntryのようでした。
ここで用いるコンストラクタはSimpleEntry()かSimpleImmutableEntry()だと思います。（勘違いでしたら申し訳ないです。）
しかし、まずこの段階で両方の説明を読みましたがイマイチ違いが分からない状況です。

とりあえず両方を試してみましたが「シンボルが見つからない」といったエラーが表示されてしまいます。

[YT0014]

以下のコードで、insertが呼ばれるのは確認しました。
AbstractMap.SimpleEntry<Integer, Integer> entry
　　= new AbstractMap.SimpleEntry<Integer, Integer>(
　　array[i], array[i]);
tree.insert(entry);
なお、実際には、insert()は、2要素目以降、無限ループになりますが。

[YT0014]

＞しかし、まずこの段階で両方の説明を読みましたがイマイチ違いが分からない状況です。
この場合は、件のインターフェースさえ実装されていれば、クラス本体の中身はどうでも良かったりします。
実際の違いは、後者が、キー、値とも、変更できないようになっていることです。
前者の説明の最初が「キーと値を維持するエントリ。値は、setValue メソッドを使って変更することもできます。」
後者が「不変のキーと値を維持するエントリ。このクラスは setValue メソッドをサポートしません。」
これだけを比べれば、違いが理解できるかと思いますが、いかがでしょう？

[karasu116]

あれから検索、挿入、削除メソッドをいじって格闘し上手く動作するようになりました。

回答ありがとうございました。