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

균형은 정말 미묘한 속성입니다. 당신은 그것이 무엇인지 알고 있다고 생각하지만 잘못되기가 너무 쉽습니다. 특히 Eric Lippert의 (좋은) 대답조차도 꺼져 있습니다. 높이 의 개념이 충분하지 않기 때문 입니다. 나무의 최소 및 최대 높이의 개념이 필요합니다 (최소 높이는 뿌리에서 잎까지의 최소 단계 수이고 최대 값은 … 음, 그림을 얻습니다). 이를 고려하여 균형을 다음과 같이 정의 할 수 있습니다.

나뭇 가지의 최대 높이가 나뭇 가지 의 최소 ​​높이 보다 1 배 이하인 나무.

(이것은 실제로 분기 자체가 균형을 이루고 있음을 의미합니다. 최대 및 최소 모두에 대해 동일한 분기를 선택할 수 있습니다.)

이 속성을 확인하기 위해 필요한 것은 현재 깊이를 추적하는 간단한 트리 순회뿐입니다. 처음으로 역 추적하면 기준 깊이가 제공됩니다. 그 후 역 추적 할 때마다 새 깊이를 기준선과 비교합니다.

• 기준선과 같으면 계속
• 둘 이상 다르면 나무가 균형을 이루지 못합니다.
• 일회성 인 경우 이제 균형 범위를 알고 있으며 모든 후속 깊이 (역 추적하려는 경우)는 첫 번째 또는 두 번째 값이어야합니다.

코드에서 :

class Tree {
    Tree left, right;
    static interface Observer {
        public void before();
        public void after();
        public boolean end();
    }
    static boolean traverse(Tree t, Observer o) {
        if (t == null) {
            return o.end();
        } else {
            o.before();
            try {
                if (traverse(left, o))
                    return traverse(right, o);
                return false;
            } finally {
                o.after();
            }
        }
    }
    boolean balanced() {
        final Integer[] heights = new Integer[2];
        return traverse(this, new Observer() {
            int h;
            public void before() { h++; }
            public void after() { h--; }
            public boolean end() {
                if (heights[0] == null) {
                    heights[0] = h;
                } else if (Math.abs(heights[0] - h) > 1) {
                    return false;
                } else if (heights[0] != h) {
                    if (heights[1] == null) {
                        heights[1] = h;
                    } else if (heights[1] != h) {
                        return false;
                    }
                }
                return true;
            }
        });
    }
}

Observer 패턴을 사용하지 않고도이 작업을 수행 할 수 있다고 생각하지만 이런 식으로 추론하는 것이 더 쉽습니다.

[편집] : 왜 당신은 각 측면의 높이를 취할 수 없습니다. 이 트리를 고려하십시오.

        /\
       /  \
      /    \
     /      \_____
    /\      /     \_
   /  \    /      / \
  /\   C  /\     /   \
 /  \    /  \   /\   /\
A    B  D    E F  G H  J

OK, 조금 지저분하지만 루트의 각 측면은 균형 : C깊이 2되고 A, B, D, E깊이 3,있다가 F, G, H, J깊이 4. 왼쪽 지점의 높이입니다은 2 (높이 기억은 트래버스 당신으로 감소 분기) 오른쪽 지점의 높이가 3입니다 그러나 전체 트리입니다 하지 둘 사이의 높이 차이가로 균형 C및F . 최소 최대 사양이 필요합니다 (허용되는 높이가 두 개만 있어야하므로 실제 알고리즘이 덜 복잡 할 수 있음).

답변

IsHeightBalanced(tree, out height)
    if (tree is empty)
        height = 0
        return true
    balance = IsHeightBalanced(tree.left, heightleft) and IsHeightBalanced(tree.right, heightright)
    height = max(heightleft, heightright)+1
    return balance and abs(heightleft - heightright) <= 1     

public static <T> boolean isBalanced(TreeNode<T> root){
    return checkBalance(root) != -1;
}

private static <T> int checkBalance(TreeNode<T> node){
    if(node == null) return 0;
    int left = checkBalance(node.getLeft());

    if(left == -1) return -1;

    int right = checkBalance(node.getRight());

    if(right == -1) return -1;

    if(Math.abs(left - right) > 1){
        return -1;
    }else{
        return 1 + Math.max(left, right);
    }
}

    A
     \
      B
     / \
    C   D

       A
     /  \
    B    C
   /      \
  D        G
 /          \
E            H

int height(treeNodePtr root) {
        return (!root) ? 0: 1 + MAX(height(root->left),height(root->right));
}

bool isHeightBalanced(treeNodePtr root) {
        return (root == NULL) ||
                (isHeightBalanced(root->left) &&
                isHeightBalanced(root->right) &&
                abs(height(root->left) - height(root->right)) <=1);
}

private boolean isLeaf(TreeNode root) {
    if (root.left == null && root.right == null)
        return true;
    return false;
}

private boolean isBalanced(TreeNode root) {
    if (root == null)
        return true;
    Vector<TreeNode> queue = new Vector<TreeNode>();
    int level = 1, minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;
    queue.add(root);
    while (!queue.isEmpty()) {
        int elementCount = queue.size();
        while (elementCount > 0) {
            TreeNode node = queue.remove(0);
            if (isLeaf(node)) {
                if (minLevel > level)
                    minLevel = level;
                if (maxLevel < level)
                    maxLevel = level;
            } else {
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            elementCount--;
        }
        if (abs(maxLevel - minLevel) > 1) {
            return false;
        }
        level++;
    }

    return true;
}