BST 트리에서이 재귀 함수를 이해하십시오.

Question

크기별로 노드 순위에 대해이 코드를 이해하는 데 어려움을 겪고 있습니다. Rank는 키보다 작은 모든 노드의 크기를 반환합니다.

결과가 순위에 대해 리턴하는 방법

http://algs4.cs.princeton.edu/32bst/BST.java.html

(키 x.left) ??

코드 : 그 순위는 주어진 키 및 후보자의 사이의 비교를 나타내는 항목 (노드 값)이 아니라 값을 반환하지 않는

public int rank(Key key) { 
     return rank(key, root); 
    } 

    // Number of keys in the subtree less than key. 
    private int rank(Key key, Node x) { 
     if (x == null) return 0; 
     int cmp = key.compareTo(x.key); 
     if  (cmp < 0) return rank(key, x.left); 
     else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right); 
     else    return size(x.left); 
    } 


// is the symbol table empty? 
    public boolean isEmpty() { 
     return size() == 0; 
    } 

    // return number of key-value pairs in BST 
    public int size() { 
     return size(root); 
    } 

// return number of key-value pairs in BST rooted at x 
private int size(Node x) { 
    if (x == null) return 0; 
    else return x.N; 
} 

Answer 1

주 노드의 왼쪽 서브 트리 (가장 왼쪽 노드의 값은 binary search tree입니다.

반환 값은 표준 Comparable interface의 구현에서 비롯됩니다. 첫 번째 요소가 두 번째보다 작은 경우 음수, 더 큰 경우 양수, 두 값이 같으면 0입니다.

반환되는 정확한 숫자는 비교되는 두 키 사이의 거리 (차이)를 나타내며 비교 결과 (일반적으로 정렬 알고리즘)를 사용하는 코드에 유용 할 수 있습니다.