C++ AVLTree Rotation

Question

AVLTree로 LeftRotation을 수행하려고합니다. 3, 5, 10을 삽입하여 퇴화 된 나무가됩니다. 내가 트래버스 할 때 3, 5, 10을 주겠지 만 회전을 할 때 나는 단지 5, 10 대신에 5, 3, 10을 얻습니다.

a을 의 left 브랜치로 설정하는 것과 관련이 있습니다. 나는 그것을 따라갈 것이고 나무의 뿌리는 5이고, 왼쪽은 3이고 오른쪽은 10이 될 것이다. 그러나 나는 가로 질러 갈 때 왼쪽면이 null 인 것을 보여준다.

void AVLTree::RotateLeft(Node *root) 
{ 
    Node a = *root; 
    Node b = *root->GetRight(); 
    *root = b; 
    a.SetRight(b.GetLeft()); 
    b.SetLeft(&a); //This is where the problem occurs 
} 

그리고 내 Traversal 코드 :

void AVLTree::Traverse(Node *node) 
{ 
    cout << node->GetValue() << ", "; 
    if (node->GetLeft() != nullptr) 
     Traverse(node->GetLeft()); 
    if (node->GetRight() != nullptr) 
     Traverse(node->GetRight()); 
} 

미리 감사드립니다

여기 내 회전 코드입니다!

수정 : 모두 0을 nullptr (으)로 변경했습니다. 수정 해 주셔서 감사합니다.

Answer 1

새 위치를 가리 키도록 root을 (를) 이동하는 방법에 문제가 있습니다. 그것에 대한 의문이 있다면 다음 두 문장을 고려하십시오. 위의 원래 코드의 변수 명명 규칙은 일관성을 위해 사용됩니다. (1)에서

*root = b; // (1) 
root = &b; // (2) 

는 루트 포인터의 내용은 b 변수에 저장된 값을 포함하도록 수정된다. root의 주소는 어떤 식 으로든 수정되지 않았습니다. 주소 root은 (1)이 실행되기 전에 (1)이 완료된 후에 변경되지 않습니다.

(2)에서 root은 이제 b 변수의 주소를 가리키고 있습니다. root이 가리키는 주소가 수정되었으므로 이제 root 포인터의 내용이 b 변수의 값과 같습니다.

라인별로 void AVLTree::RotateLeft(Node *root) 함수를 단계별로 실행하고 모든 변수의 주소와 내용을 검사하여이 첫 번째 손을 보는 것이 좋습니다. 위의 작업에 대한 시뮬레이션을 예제 정수 데이터에서 수행했으며 포인터는 (2)을 사용하여 예상대로 이동했습니다.

샘플 데이터에서 회전이 발생하기 전에 3 노드가 root으로 지정되도록 불균형 트리를 배열해야합니다. 그런 다음 root->right은 5을 가리키고 root->right->right은 10을 가리 킵니다. root->right->left은 nullptr이어야하고 root->left도 nullptr이어야합니다.

이없는 경우는, 다음 AVL 삽입 알고리즘 중 하나를 잘못 구현하거나 설계 요구 사항 (마크 앨런 와이즈, 잘게 썬 야채를 넣은 멀건 수 우프 워커 AVL Tree Tutorial on Eternally Confuzzled에 의해 예를 들어, 위키 백과에 AVL tree, Data Structures and Algorithm Analysis in C++ (3rd Edition) [Hardcover]를) 예상과 다른 경우.최종 결과 5-root 포인트 3에 root->left 점 10-root->right 포인트 인 트리 상기 root 포인터 전달 오른쪽 포인터 균형의 이동에 관해서

는

좌측을 가리 키도록 설정 될 로컬 pB 포인터 (아래 참조)의 왼쪽 포인터 pB 포인터는 root 포인터로 전달되고, (이 경우에는 원래 포인터로 설정 됨)을 가리 키도록 root 포인터가 설정됩니다.

위 샘플 데이터를 사용하여 함수의 본문이 수정됩니다. 이것은 GetRight() 및 GetLeft()이 위의 원본 게시물에서 노드 복사본을 반환하는 것처럼 보이지 않습니다. 아래 수정 된 함수 본문은 위의 Mark Allen Weiss가 구현 한 single AVL rotation with right child과 일치합니다. 원래 게시물에는 높이 변수가 없으므로 아래 코드도 마찬가지입니다.

// 
// The `root` variable is passed as a pointer by reference 
// 
void AVLTree::RotateLeft(Node* & root) 
{ 
    // 
    // This works as long as the GetRight() method returns a pointer, not a Node copy 
    // 
    Node *pB = root->GetRight(); 

    // 
    // In the example values for three nodes, the root->right will become nullptr 
    // 
    root->SetRight(pB->GetLeft()); 

    // 
    // In the example values, the pB->left will point to the node with value of 3 
    // 
    pB->SetLeft(root); 

    // 
    // Move root to point to where pB does (root->right) 
    // 
    root = pB; 
}