균형 이진 트리는 무엇이며 어떻게 확인합니까?

이진 트리의 경우 트리가 왜곡되면 작업을 수행하는 데 계산적으로 비효율적이 됩니다.

이것이 나무가 비뚤어지지 않도록 하는 동기입니다. 따라서 균형 잡힌 이진 트리가 필요합니다.

균형 이진 트리 란 무엇입니까

균형 이진 트리는 작업을 수행하는 데 계산적으로 효율적입니다.

균형 이진 트리는 다음 조건을 따릅니다.

모든 노드에서 왼쪽 및 오른쪽 하위 트리 높이의 절대 차이는 1 미만입니다.
각 노드의 왼쪽 하위 트리는 균형 잡힌 이진 트리입니다.
각 노드의 오른쪽 하위 트리는 균형 잡힌 이진 트리입니다.

높이 균형 이진 트리

균형 이진 트리는 높이 균형 이진 트리라고도 합니다. 높이 균형 이진 트리는 HB(k)로 표시할 수 있습니다. 여기서 k는 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이입니다. 'k'는 균형 요인으로 알려져 있습니다.

트리의 경우 균형 요소(k)가 0이면 해당 트리를 완전 균형 이진 트리라고 합니다. HB(0)으로 나타낼 수 있습니다.

자체 균형 이진 검색 트리

이진 검색 트리의 균형 요소가 1이면 AVL(Adelso-Velskii 및 Landis) 트리입니다. 이는 AVL 트리에서 왼쪽 하위 트리와 오른쪽 하위 트리 높이의 차이가 최대 1임을 의미합니다.

AVL 트리는 자체 균형 이진 검색 트리입니다. AVL 트리에서 왼쪽 하위 트리와 오른쪽 하위 트리 간의 차이가 1보다 크면 다음 4개의 회전 중 하나를 수행하여 균형을 재조정합니다.

왼쪽 회전
오른쪽 회전
좌우 회전
오른쪽-왼쪽 회전

이진 트리가 균형을 이루고 있는지 확인하는 방법은 무엇입니까?

이진 트리가 균형을 이루고 있는지 확인하려면 세 가지 조건을 확인해야 합니다.

모든 노드에서 왼쪽 및 오른쪽 하위 트리 높이의 절대 차이는 1 미만이어야 합니다.
각 노드의 왼쪽 하위 트리는 균형 잡힌 이진 트리여야 합니다.
각 노드의 오른쪽 하위 트리는 균형 잡힌 이진 트리여야 합니다.

나무의 높이를 계산할 수 있는 함수가 필요합니다. 이를 수행하는 한 가지 방법은 높이를 계산하는 별도의 함수를 작성하고 높이가 필요할 때마다 호출하는 것입니다. 이것은 계산상 비효율적일 것입니다.

이를 구현하는 더 좋은 방법은 동일한 함수에서 높이를 반환하는 것입니다.

각 노드에 대해 균형이 맞지 않으면 -1을 반환하고 균형이 맞으면 해당 노드/하위 트리의 높이를 반환합니다.

알고리즘은 다음과 같습니다.

노드 == null인 경우 -> 0 반환
왼쪽 하위 트리를 확인합니다. 균형이 맞지 않으면 -> -1 반환
오른쪽 하위 트리를 확인합니다. 균형이 맞지 않으면 -> -1 반환
왼쪽 하위 트리와 오른쪽 하위 트리 높이 사이의 절대값입니다. 1보다 크면 -1을 반환합니다.
트리가 균형을 이룬 경우 -> 높이 반환

의사 코드는 다음과 같습니다.

 private int balanceHeight (TreeNode currentNode)
    {
        if (currentNode == null)
        {
            return 0;
        }

        // checking left subtree
        int leftSubtreeHeight = balanceHeight (currentNode.left);
        if (leftSubtreeHeight == -1) return -1;
        // if left subtree is not balanced then the entire tree is also not balanced

        //checking right subtree
        int rightSubtreeHeight = balanceHeight (currentNode.right);
        if (rightSubtreeHeight == -1) return -1;
        // if right subtree is not balanced then the entire          tree is also not balanced

        //checking the difference of left and right subtree for current node
        if (Math.abs(leftSubtreeHeight - rightSubtreeHeight) > 1)
        {
            return -1;
        }
        //if it is balanced then return the height
        return (Math.max(leftSubtreeHeight, rightSubtreeHeight) + 1);
    }

트리의 루트에서 이 함수를 호출할 수 있으며 -1 이외의 값을 반환하면 균형 잡힌 이진 트리입니다. -1을 반환하면 균형 이진 트리가 아닙니다.

결론

이 튜토리얼에서 균형 이진 트리와 트리가 균형 이진 트리인지 확인하는 방법을 다루었습니다. 당신이 이해하고 우리와 함께 배우는 것을 즐겼기를 바랍니다.