왜 StackOverflowError를 생성합니까?

Question

저는 나무가있는 초보자이며 처음으로 구현하려고하고 있었고 stackoverfloweror를 생성했습니다. 나는 아마 재발 호출과 관련이 있다는 것을 알고 있지만, 재귀에 문제가있는 것을 보지 못한다면 약간의 도움을받을 수 있을까요? 이 코드에 오류가 있습니다.

 public void insert(Node node, String value) 
{ 
    if((value.compareTo(node.getValue())) < 0) 
    { 
     if (node.left != null) 
     { 
      insert(node.left, value); 
     } 
     else 
      node.left = new Node(value); 

    } 
    else if((value.compareTo(node.getValue())) > 0) 
    { 
     if(node.right !=null) 
     { 
      insert(node.right, value); 
     } 
     else 
      node.right= new Node(value); 
    } 
} 

나는이 가장 가능성이 발생하게 여기

public static void main(String[] args) throws FileNotFoundException, IOException { 
    Tree dataTree = new Tree(new Node("m")); 


    File file = new File("C:\\randomdata.csv"); 

    BufferedReader br = new BufferedReader(new FileReader(file)); 
    String line; 

    while((line = br.readLine()) != null){ 
     if(line.toString().contains("zogeti")) 
      break; 
     else 
     { 
      dataTree.insert(dataTree.getRootElement(),line); 
     } 
    } 

    br.close(); 
    } 

Answer 1

는,이 함수는 보인다. 자바는 꼬리 재귀를 구현하지 않으므로, 실제로는 재귀가 될 것입니다. 재귀 함수 대신 while 루프로 다시 작성하십시오.

Answer 2

그 메소드를 호출 node.left == node 또는 node.right == node 또는 트리에서 다른 이상주기의 경우.

값이 같으면 블록 인 경우 트리거되지 않으며 단순히 아무것도 반환하지 않고 반환합니다 (또한 추적을 반환합니다). 이것은주기가 아마이 방법의 외부에서 발생하고 있음을 의미합니다.

이 버그는 삽입 방법 이외의 요소 인 Tree 클래스의 생성자를 만들 수있는 유일한 곳에서 찾을 수 있습니다.

Answer 3

이 CSV 파일의 크기는 얼마입니까? 파일이 클수록 재귀가 깊어지고 stackoverflow가 발생합니다.

다음 명령 줄 매개 변수로 java를 실행 해보십시오.

-Xms512m -Xmx512m 

또한 파일에서 읽은 새 줄이 기존 노드 값과 같은 경우 어떻게해야합니까?

다음 코드는이를 무시합니다 ... (요구 사항 일 수 있음). 파일이 처음에 분류되어있는 경우가 N 라인을 가진 파일을 N 시간을 재귀 같은

if((value.compareTo(node.getValue())) < 0) 
{ 
    if (node.left != null) 
    { 
     insert(node.left, value); 
    } 
    else 
     node.left = new Node(value); 

} 
else if((value.compareTo(node.getValue())) > 0) 
{ 
    if(node.right !=null) 
    { 
     insert(node.right, value); 
    } 
    else 
     node.right= new Node(value); 
} 

Answer 4

파일이 3260953 행이고 정렬되어 있으면 문제를 확실히 설명 할 수 있습니다. 요소가 정렬 된 오름차순 인 경우 insert은 새 요소를 삽입 할 때마다 매 노드의 오른쪽 분기에 배치됩니다. 결국 3260953 개의 선형 적으로 링크 된 노드의 문자열이 코드에서 많은 재귀 호출을 통해 액세스합니다. 스택 오버플로가 발생합니다. 훨씬 작은 파일과 알파벳 순서로 뒤섞어서 실행 해보십시오.

빨강 - 검은 색 나무은 요소를 재배포하여 트리의 균형을 자동으로 조정하여이 문제를 방지합니다. 그런 데이터 구조를 코딩하는 것은 그리 간단하지 않습니다.