AVL 트리 균형이 고르지 않음 C++

Question

자체 밸런싱 AVL 트리를 만들고 있습니다. 다른 AVL 트리를 구현 한 것처럼 구현하고 있지만, 트리 균형을 조정하면 함수는 분명히 그렇지 않을 때 트리가 균형을 유지한다는 것을 반환합니다.

#include "AVLTree.h" 
#include "Node.h" 
#include <iostream> 

using namespace std; 

AVLTree::AVLTree(void) 
{ 
    root = nullptr; 
} 

Node* AVLTree::GetRoot() 
{ 
    return root; 
} 

Node* AVLTree::RotateLeft(Node *root) 
{ 
    Node *temp = root; 
    root = temp->GetRight(); 
    temp->SetRight(root->GetLeft()); 
    root->SetLeft(temp); 
    return root; 
} 

Node* AVLTree::RotateRight(Node *root) 
{ 
    Node *temp = root; 
    root = temp->GetLeft(); 
    temp->SetLeft(root->GetRight()); 
    root->SetLeft(temp); 
    return root; 
} 

Node* AVLTree::DoubleRight(Node *root) 
{ 
    RotateLeft(root->GetLeft()); 
    RotateRight(root); 
    return root; 
} 

Node* AVLTree::DoubleLeft(Node *root) 
{ 
    RotateRight(root->GetRight()); 
    RotateLeft(root); 
    return root; 
} 

void AVLTree::Add(int value, Node *r) 
{ 
    Node *node; 
    if (r == nullptr) 
    node = root; 
    if (root == nullptr) 
    { 
    root = new Node(value); 
    return; 
    } 

    if (value < node->GetValue()) 
    { 
    if (node->GetLeft() == nullptr) 
    { 
     node->SetLeft(new Node(value)); 
     node = MakeBalance(node); 
    } 
    else 
    { 
     Add(value, node->GetLeft()); 
     node = MakeBalance(node); 
    } 
    } 

    else if (node->GetRight() == nullptr) 
    { 
    node->SetRight(new Node(value)); 
    node = MakeBalance(node); 
    } 

    else 
    { 
    Add(value, node->GetRight()); 
    node = MakeBalance(node); 
    } 
} 

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

int AVLTree::CheckHeight(Node *node) 
{ 
    int height = 0; 
    if (node != nullptr) 
    { 
    int left = CheckHeight(node->GetLeft()); 
    int right = CheckHeight(node->GetRight()); 
    height = max(left, right) + 1; 
    } 
    return height; 
} 

int AVLTree::GetDifference(Node *node) 
{ 
    int left = CheckHeight(node); 
    int right = CheckHeight(node); 
    int balance = left - right; 
    return balance; 
} 

Node* AVLTree::MakeBalance(Node *node) 
{ 
    int balance = GetDifference(node); 
    if (balance > 1) 
    { 
    if (GetDifference(node->GetLeft()) > 0) 
     node = RotateLeft(node); 
    else 
     node = DoubleLeft(node); 
    } 
    else if (balance < -1) 
    { 
    if (GetDifference(node->GetRight()) > 0) 
     node = DoubleRight(node); 
    else 
     node = RotateRight(node); 
    } 
    return node; 
} 

내가 그것을 통해 몇 번 밟아야하고 3, 5, 왼쪽 균형이 2이고, 내가 추가 한 후 적절한 균형이이 것을 반환 유지 : 여기

내 AVLTree 클래스 다음 10 만들고 나무가 2

Answer 1

의 균형이이 부분은 나를 밖으로 점프 :

int AVLTree::GetDifference(Node *node) 
{ 
    int left = CheckHeight(node); 
    int right = CheckHeight(node); 
    int balance = left - right; 
    return balance; 
} 

이 항상 left == right 따라서가 발생합니다. 이것은 아마입니다

// You might want this too: if (!node) return 0; 
int left = CheckHeight(node->GetLeft()); 
int right = CheckHeight(node->GetRight()); 
int balance = left - right; 
return balance;