Java 이진 검색 트리 - 노드 경로 길이 계산

Question

Java의 TreeMap 구현을 사용하면 트리 내의 지정된 노드에 대한 경로의 길이를 계산하는 것이 어떻게 가능합니까? 이 말은 바이너리 검색 트리에서 노드를 검색하는 동안 수행 된 비교 횟수를 계산하는 것을 의미합니다.

Answer 1

TreeMap has a constructor 비교기를 인수로 사용합니다. 비교자를 사용하여지도에 저장된 키를 정렬합니다. 말 그대로 "수행 된 비교 횟수"를 계산하려면 호출 된 횟수를 세는 인스트루먼트 된 비교기를 작성할 수 있습니다.

public class StringComparator implements Comparator<String> { 
    private int count = 0; 

    @Override 
    public int compare(String o1, String o2) { 
     ++count; 
     return o1.compareTo(o2); 
    } 

    public int getCount() { return count; } 
    public void reset() { count = 0; } 

    public static void main(String[] args) { 
     StringComparator sc = new StringComparator(); 
     TreeMap<String, String> map = new TreeMap<>(sc); 
     map.put("foo", "one"); 
     System.out.println("foo took " + sc.getCount() + " comparisons"); 
     sc.reset(); 
     map.put("bar", "two"); 
     System.out.println("bar took " + sc.getCount() + " comparisons"); 
    } 
}