2-3-4 트리의 최소값 찾기

StackOverflow https://stackoverflow.com//questions/25006856

문제

우선, 이 질문은 숙제가 아닙니다.저는 현재 Robert Lafore가 쓴 "데이터 구조 및 알고리즘 2판"이라는 책을 읽고 있습니다.10장에서 우리는 2-3-4 트리에 대해 배웠고, 그런 다음 해당 트리에서 최소값을 찾는 방법을 작성하라는 요청을 받았습니다.

개념적인 관점에서 최소값이 어디인지 이해합니다.이는 리프의 가장 왼쪽에 있는 데이터 항목입니다.

프로그래밍 관점에서 볼 때 이 데이터 항목을 찾는 메서드를 구현하는 방법이 약간 혼란스럽습니다.노드가 리프인지 알 수 있는 부울이 있습니다.그래서 제가 원래 한 일은 다음과 같습니다.

  public long minValue() {
   Node curNode = root; // current node = root
   long min = curNode.getMin();
   while(!curNode.isLeaf()) { // while current node is NOT a leaf
       curNode = getNextChild(curNode, min);
   } // end while
   return min;
} // end minValue()

이것이 하는 일은(적어도 내가 해야 한다고 생각하는 것은 루트 노드에서 시작하는 curNode를 만드는 것입니다.그런 다음 curNode.getMin을 저장하는 최소값을 만듭니다.getMin()은 배열의 인덱스 0(가장 낮은 값이 유지되어야 하는 위치)에서 값을 가져옵니다.그런 다음 현재 노드는 리프가 아니지만 최소 지점에서 다음 자식으로 이동해야 합니다.현재 노드가 리프이면 최소값을 반환해야 합니다.

하지만 이것은 작동하지 않습니다.누구든지 이것을 구현하는 방법에 대한 아이디어를 가지고 있습니까?힌트나 제안 또는 다른 것이 있나요?

편집하다:각 클래스와 클래스의 상호 작용 방식을 보려면 각 개별 클래스에 대한 링크를 참조하세요.Tree234 클래스에 최소값 방법을 넣었습니다.

데이터항목, 마디, 트리234, 그리고 프로그램이 실행되는 곳, 트리234앱

도움이 되었습니까?

해결책

먼저 더 나은 도움을 받으려면 다음 게시물을 게시하세요. SSCCE 이는 전체 프로그램의 최소한의 구현을 제공합니다. 즉, 자체 IDE에 c/p하고 실행하여 무슨 일이 일어나고 있는지 확인할 수 있는 것입니다.우리가 코드의 이 부분만 볼 때 "이것이 작동하지 않는 이유"를 말하기는 어렵습니다.

둘째, "이것은 작동하지 않습니다"가 무엇을 의미하는지 자세히 설명해야 합니다.예상치 못한 일이 무엇인지, 무엇을 하지 않고 있는지 정확하게 알려주세요.당신이 그렇게 하는 대신에, 그것이 왜 그렇게 하는지 어느 정도 확실하게 우리가 당신에게 어떻게 말할 수 있겠습니까?

그러나 한 가지가 두드러집니다.인스턴스화 중입니다. min 루트 노드의 가장 작은(직접) 자식으로 (아마도) 트리를 반복하여 가장 왼쪽 요소를 찾았지만 동일한 결과를 반환합니다. min 처음에 생성한 값입니다.즉, 반복 루틴이 원하는 작업을 정확하게 수행할 수 있지만 결과적으로 반환 값에 대해서는 아무 작업도 수행하지 않습니다.

나는 당신이 다음과 같은 일을 해야 한다고 생각합니다. 

  public long minValue() {
      Node curNode = root;
      long min = curNode.getMin();
      while(!curNode.isLeaf()) { // 
           curNode = getNextChild(curNode, min); //it's not immediately clear what min is doing here 
       } 
       //curNode is now the leftmost non-leaf element in the tree
       min = curNode.getMin();
       return min;

내가 변경한 유일한 변경 사항은 return 문 위에 줄을 삽입한 것입니다. min 트리의 가장 왼쪽 요소에 연결된 최소값입니다.

다른 팁

효율성을 높이려면 전화할 필요가 없습니다. getNextChild(curNode, min), 노드의 항목은 2-3-4 트리에서 항상 오름차순으로 정렬되고 가장 작은 항목이 항상 인덱스에 있기 때문입니다. 0.시작 시 min 선언도 필요하지 않습니다.따라서 프로그램은 다음과 같을 수 있습니다.

public long minValue() {
    Node curNode = root;
    while (!curNode.isLeaf()) {
        curNode = curNode.getChild(0);
    }
    return curNode.getMin();
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top