二分探索木でtraverse()を用いて木のバランスの悪さをはかりたいです。

Question

二分探索木の（図にしたときの）バランスをはかる指標をunbalance度とします。
unbalance度の定義はあるノードにおける右の子の合計数と左の子の合計数の差の絶対値です。
各ノードにおけるunbalance度の最大値をその探索木のunbalance度とします。

青字で表したのが各ノードにおけるunbalance度で、緑字で表したのが各ノードにおけるそれぞれ左の子の合計数と右の子の合計数です。

package genericSearch;

import java.util.AbstractMap;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.Scanner;


public class StringSearch2 {
	//テスト用のmainメソッド
	@SuppressWarnings("resource")
    public static void main( String [ ] args ) {
    	//データ型がString型である空の2分探索木を作る．
    	VisitableBinSearchTree2<Integer,String> tree =
    		new VisitableBinSearchTree2<Integer,String>(
        		new Comparator<Integer>() {
    				public int compare(Integer a, Integer b) {
    					return a - b ;
    				}
    			}
    		) ;

    	//1,2,..,nのランダムな順列を生成する
    	int n ;
    	Scanner keyboard = new Scanner(System.in) ;
    	System.out.println("#strings:") ;
    	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 ;
    	}

    	//上記の木にn個のデータを，生成したランダム順に挿入
    	for (int i = 0 ; i < n ; i++) {
    		//System.out.print(array[i] + " ");
    		tree.insert(new AbstractMap.SimpleEntry<Integer,String>(array[i], i + "-th string"));
    	}

    	//木の高さを求める
    	tree.accept(new BTVisitor<Integer,String>() {
    		public Integer visitNull() {
    			return 0 ;
    		}
    		public Integer visitNode(Object left, Object right, Map.Entry<Integer,String> data) {
    			return Math.max((Integer)left, (Integer)right) + 1 ;
    		}
    	});
    	System.out.println("height: " + (Integer)tree.traverse());
    	System.out.println("") ;

		//unbalance：
    	tree.accept(new BTVisitor<Integer,String>() {
    		public int[] visitNull() {
    			return new int[] {0, 0, 0};
    		}
			public int[] visitNode(Object left,Object right,Map.Entry<Integer,String> data) { 
				
				//ここに処理を記述
			}
		});
    	System.out.println("unbalance度:"+ (Integer)tree.traverse());

    	//postorder順に木をたどる．
    	System.out.println("visiting the tree in post order");
    	tree.accept(new BTVisitor<Integer,String>() {
    		public Void visitNull( ) {
    			return null ;
    		}
    		public Void visitNode(Object left, Object right, Map.Entry<Integer,String> data) {
    			System.out.println(data.getKey() + ":" + data.getValue());
    			return null ;
    		}
    	});
    	tree.traverse();

    	//検索と削除操作をテスト
    	int m = rand.nextInt(n) ;
    	System.out.println("trying to find " + m + " ...");
    	String result = tree.search(m) ;
    	if (result != null) {
    		System.out.println("found " + m + ":" + result) ; //結果表示
        	System.out.println("") ;
    		System.out.println("trying to delete " + m + " ...");
    		tree.delete(m); //削除
        	result = tree.search(m) ;
        	if (result != null)
        		System.out.println("Error: found the deleted data.") ;
        }
    	System.out.println("") ;

    	//木にあるデータをキーの小さい順に表示する別の方法．
    	Iterator<Map.Entry<Integer,String>> iter = tree.inorderIterator() ;
    	System.out.println("data in sorted order:");
    	while (iter.hasNext()) {
    		Map.Entry<Integer,String> d = iter.next();
    		System.out.println(d.getKey() + "：" + d.getValue());
    	}
    }
}

package genericSearch;

import java.util.Comparator;
import java.util.Map;

//Kはデータのキーの型，Vはデータの値の型
public class VisitableBinSearchTree2<K,V> extends BinSearchTree<K,V>
		implements BTAcceptor<K,V> {
	private BTVisitor<K,V> visitor ;

	//引数ありのコンストラクタ
	public VisitableBinSearchTree2(Comparator<K> comparator) {
		super(comparator) ;
	}

	//Visitorを引き受けるメソッド.
	public void accept(BTVisitor<K,V> visitor) {
		this.visitor = visitor ;
	}


	//木全体を処理するメソッド
	public Object traverse( ) {
		return traverse(getRoot()) ;
	}

	//木の指定ノードstartを根とする部分木を処理するメソッド
	private Object traverse(BinSearchTreeNode<K,V> start) {
		if (start == null)//空の木であるとき
			return visitor.visitNull();
		else {//空ではない木のとき
			Object left = traverse(start.getLeft()) ;
			Object right = traverse(start.getRight()) ;
			return visitor.visitNode(left, right, start.getData());
		}
	}
}

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 ;
	}
}

package genericSearch;

import java.util.Map;

public interface BTVisitor<K,V> {
	//nullを処理して値を返すためのメソッド
    public abstract Object visitNull( );

	//あるノードにあるデータdata，そのノードの左の部分木を処理した結果leftValue，
    //およびそのノードの右の部分木を処理した結果rightValueから，そのノードを
    //処理した結果を返すためのメソッド
    public abstract Object visitNode(Object leftValue, Object rightValue, Map.Entry<K,V> data) ;
}

treverce()メソッドが探索木を再帰的にたどっていくので、その過程にあるノードにおいて左の子がいれば左の子の個数を覚えておく変数に1を加えて、右の子がいる場合も同様に右の子の個数を覚えておく変数に1を加えてあげればいいと思いました。
これらの変数の差の絶対値がそのノードにおけるunbalance度になり、全てのノードの中で最も大きいunbalance度を返すようにすればいいと思いました。

大学の資料では最初のファイルにある通りint型の配列を用いれば比較的簡単にうまくいくと書いてあったのですがint型の配列を戻り値とする利点は何なのでしょうか？　ここでの配列の利用の仕方を教えて下さい。　また整数としてのunbalance度を取得するためにはどうしたらいいのでしょうか？

単純にキャストするしか方法が思いつかなかったのですが他に方法はありますか？

Comments

[quickquip]

疑問点がわからないですが、「int型の配列を用いれば比較的簡単にうまくいく」という文には"戻り値"という語はありません。「int型の配列を戻り値とする」はどこからでてきましたか? 前後の文ですか?
"コードがそうなってるから"ということであればこのままでもいいですが、前後の文からだったらその辺りも書いた方がいいかと思いました。

Answer 1

質問者様、写真の図だけでは何がなにを指し示すのか理解できません。

青字で表したのが各ノードにおけるunbalance度で、緑字で表したのが各ノードにおけるそれぞれ左の子の合計数と右の子の合計数です。

この図の例だと「アンバランス度」がよくわからないです。
例としてなら
「投入ノード10に対して3：7に2分木ノード分割した際 7 - 3 = 4 がアンバランス度となる。」
だと思うのですが？

unbalance度の定義はあるノードにおける右の子の合計数と左の子の合計数の差の絶対値です。

これは各ノードにおける左右の数値さえわかれば良いので

各BinSearchTreeNodeのLeftとRightの配列数から求めれば良いだけでは？