균형 이진 트리-이진 트리가 균형을 이루는 지 확인하는 방법

Twitter Facebook 링크드 인 버퍼 레딧 텀블러

균형 이진 트리 문제에서 우리는 이진 트리. 높이 균형인지 아닌지를 결정해야합니다.

차례

예

입력

핀

산출

참된

입력

핀

출력:

그릇된

균형 이진 트리

균형 잡힌 바이너리의 모든 노드 나무 왼쪽 및 오른쪽 하위 트리 높이의 차이가 1 이하입니다. 빈 나무는 항상 높이 균형을 따릅니다.
즉, 균형 잡힌 이진 트리의 경우
-1 <= 왼쪽 하위 트리의 높이 – 오른쪽 하위 트리의 높이 <= 1

균형 이진 트리에 대한 순진한 접근 방식

모든 노드가 왼쪽 및 오른쪽 하위 트리의 높이를 계산하려면 차이가 1보다 크면 false를 반환하고 그렇지 않으면 왼쪽과 오른쪽 하위 트리에 대해 반복하고 둘 다 균형이 맞으면 true를 반환하고 다른 모든 경우에는 false를 반환합니다.
기본 케이스: 빈 나무는 높이 균형을 따릅니다.

루트에서 시작하십시오. 루트가 null이면 true를 반환합니다.
왼쪽 및 오른쪽 하위 트리의 높이를 계산하고 각각 leftHeight 및 rightHeight라는 변수에 저장합니다.
루트의 왼쪽 및 오른쪽 하위 트리에 대해 균형 높이 함수를 재귀 적으로 호출합니다. 왼쪽 및 오른쪽 하위 트리가 모두 균형을 이루고 leftHeight와 rightHeight의 차이가 1보다 작거나 같으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

시간 복잡성 = O (n ^ 2)

JAVA 코드

public class BalancedBinaryTree {
    static class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    // Function to calculate height of a tree rooted at root
    private static int height(Node root) {
        if (root == null) {
            // Height of empty tree is 0
            return 0;
        }
        // Height of tree is 1 + maximum of height of left or right subtree
        return 1 + Math.max(height(root.left), height(root.right));
    }

    // Function to check if given tree is balanced or not
    private static boolean isBalanced(Node root) {
        if (root == null) {
            // Empty tree is always balanced
            return true;
        }

        // Find the left subtree height and right subtree height
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        // If this node is balanced and also its left and right subtree are balanced return true
        // else return false
        return (Math.abs(leftHeight - rightHeight) <= 1) && isBalanced(root.left)
                && isBalanced(root.right);
    }

    public static void main(String[] args) {
        // Tree in example 1
        Node root = new Node(18);
        root.left = new Node(4);
        root.right = new Node(20);
        root.right.left = new Node(13);
        root.right.right = new Node(70);

        System.out.println(isBalanced(root));

        // Tree in example 2
        Node root2 = new Node(3);
        root2.left = new Node(4);
        root2.right = new Node(8);
        root2.left.left = new Node(5);
        root2.left.right = new Node(9);
        root2.right.right = new Node(7);
        root2.right.right.left = new Node(6);

        System.out.println(isBalanced(root2));
    }
}

C ++ 코드

#include <iostream>
using namespace std;

class Node {
    public:
    int data;
    Node *left;
    Node *right;
};

// Function to calculate height of a tree rooted at root
int height(Node *root) {
    if (root == NULL) {
        // Height of empty tree is 0
        return 0;
    }
    // Height of tree is 1 + maximum of height of left or right subtree
    return 1 + std::max(height(root->left), height(root->right));
}

// Function to check if given tree is balanced or not
bool isBalanced(Node *root) {
    if (root == NULL) {
        // Empty tree is always balanced
        return true;
    }

    // Find the left subtree height and right subtree height
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    // If this node is balanced and also its left and right subtree are alanced return true
    // else return false
    return (abs(leftHeight - rightHeight) <= 1) && isBalanced(root->left)
            && isBalanced(root->right);
}

// Function to allocate new memory to a tree node
Node* newNode(int data) { 
    Node *node = new Node(); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL;
  
    return (node); 
}

int main() {
  // Tree in example 1
    Node *root = newNode(18);
    root->left = newNode(4);
    root->right = newNode(20);
    root->right->left = newNode(13);
    root->right->right = newNode(70);

    if (isBalanced(root) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Tree in example 2
    Node* root2 = newNode(3);
    root2->left = newNode(4);
    root2->right = newNode(8);
    root2->left->left = newNode(5);
    root2->left->right = newNode(9);
    root2->right->right = newNode(7);
    root2->right->right->left = newNode(6);

    if (isBalanced(root2) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    return 0;
}

true
false

균형 이진 트리를위한 최적화 된 접근 방식

나무가 높이 균형 속성을 만족하면 나무의 높이를 반환하도록 높이 함수를 수정하고 그렇지 않으면 -1을 반환합니다.

빈 트리는 항상 높이 균형 (Base Case)을 따릅니다.
height 함수를 재귀 적으로 호출하여 왼쪽 높이를 찾으십시오. 높이가 -1이면 왼쪽 하위 트리가 균형이 맞지 않으면 즉시 -1을 반환합니다.
높이 함수를 재귀 적으로 호출하여 올바른 높이를 찾으십시오. 높이가 -1이면 오른쪽 하위 트리가 불균형 상태가되고 즉시 -1을 반환합니다.
왼쪽과 오른쪽 높이의 차이가 1보다 작거나 같으면 height (1 + max (leftHeight, rightHeight))를 반환하고 그렇지 않으면 -1을 반환합니다.

시간 복잡성 = O (N)

JAVA 코드

public class BalancedBinaryTree {
    static class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    // Modified height function
    // Returns the height of tree if the tree is balanced and returns -1 is the tree is not balanced
    private static int height(Node root) {
        if (root == null) {
            // Empty tree is always balanced
            return 0;
        }

        // Find the left height
        int lh = height(root.left);
        if (lh == -1) {
            // Left subtree is unbalanced
            return -1;
        }
        // Find the right height
        int rh = height(root.right);
        if (rh == -1) {
            // Right subtree is unbalanced
            return -1;
        }
        if (Math.abs(lh - rh) <= 1) {
            // Balanced tree, return the height
            return Math.max(lh, rh) + 1;
        }
        // Unbalanced tree
        return -1;
    }

    private static boolean isBalanced(Node root) {
        // Call the modified height function
        int height = height(root);
        if (height == -1) {
            // Unbalanced tree
            return false;
        }
        // Balanced tree
        return true;
    }

    public static void main(String[] args) {
        // Tree in example 1
        Node root = new Node(18);
        root.left = new Node(4);
        root.right = new Node(20);
        root.right.left = new Node(13);
        root.right.right = new Node(70);

        System.out.println(isBalanced(root));

        // Tree in example 2
        Node root2 = new Node(3);
        root2.left = new Node(4);
        root2.right = new Node(8);
        root2.left.left = new Node(5);
        root2.left.right = new Node(9);
        root2.right.right = new Node(7);
        root2.right.right.left = new Node(6);

        System.out.println(isBalanced(root2));
    }
}

C ++ 코드

#include <iostream>
using namespace std;

class Node {
    public:
    int data;
    Node *left;
    Node *right;
};

// Function to calculate height of a tree rooted at root
int height(Node *root) {
    if (root == NULL) {
        // Empty tree is always balanced
        return 0;
    }
    // Find the left height
    int lh = height(root->left);
    if (lh == -1) {
        // Left subtree is unbalanced
        return -1;
    }
    // Find the right height
    int rh = height(root->right);
    if (rh == -1) {
        // Right subtree is unbalanced
        return -1;
    }
    if (abs(lh - rh) <= 1) {
        // Balanced tree, return the height
        return 1 + std::max(height(root->left), height(root->right));
    }
    // Unbalanced tree
    return -1;
}

// Function to check if given tree is balanced or not
bool isBalanced(Node *root) {
    // Call the modified height function
    int h = height(root);
    if (h == -1) {
        // Unbalanced tree
        return false;
    }
    // Balanced tree
    return true;
}

// Function to allocate new memory to a tree node
Node* newNode(int data) { 
    Node *node = new Node(); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL;
  
    return (node); 
}

int main() {
  // Tree in example 1
    Node *root = newNode(18);
    root->left = newNode(4);
    root->right = newNode(20);
    root->right->left = newNode(13);
    root->right->right = newNode(70);

    if (isBalanced(root) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Tree in example 2
    Node* root2 = newNode(3);
    root2->left = newNode(4);
    root2->right = newNode(8);
    root2->left->left = newNode(5);
    root2->left->right = newNode(9);
    root2->right->right = newNode(7);
    root2->right->right->left = newNode(6);

    if (isBalanced(root2) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    return 0;
}

true
false

참조

Twitter Facebook 링크드 인 버퍼 레딧 텀블러