[c++] 균형 이진 트리(Balanced Binary Tree)

12 Dec 2023

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 자료구조입니다. 균형 이진 트리(Balanced Binary Tree)는 서브트리의 높이 차가 1 이하인 이진 트리를 의미합니다. 이러한 균형 이진 트리는 검색을 빠르게 수행할 수 있어 많은 응용 분야에서 사용됩니다.

균형 이진 트리의 특징

모든 리프 노드들은 높이 차가 1 이하입니다.
모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차가 1 이하입니다.
모든 서브트리도 균형 이진 트리여야 합니다.

균형 이진 트리의 구현

#include <iostream>
#include <cmath>

class TreeNode {
public:
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

int height(TreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    return 1 + std::max(height(node->left), height(node->right));
}

bool isBalanced(TreeNode* root) {
    if (root == nullptr) {
        return true;
    }
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return std::abs(leftHeight - rightHeight) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
    
    if (isBalanced(root)) {
        std::cout << "The tree is balanced" << std::endl;
    } else {
        std::cout << "The tree is not balanced" << std::endl;
    }
    
    return 0;
}

결론

균형 이진 트리는 트리의 높이가 최소화되어 검색 연산을 효율적으로 수행할 수 있는 자료구조입니다. 트리를 구현하거나 쿼리하는 경우, 균형 이진 트리를 사용하여 성능을 향상시킬 수 있습니다.

참고 문헌:

GeeksforGeeks