Java Tee & Graph

1. 트리란?

트리란, 그래프의 일종으로 순환하지 않는 그래프이며, 부모 - 자식 간의 계층 구조로 되어있다. 트리 에서 부모는 여러개의 자식노드를 갖을 수 있지만, 자식은 하나의 부모를 갖을 수 있다. 트리의 종류에는 이진탐색트리(Binary Search Tree) , 이진트리(Binary Tree) , 경사트리(Slope Tree) 등 이 있다.

시간 복잡도의 경우

• 이진탐색트리(BST) = O(logN) / O(N)
• 경사트리 = O(N) [ 연결리스트 ]

2. 트리에 관련된 문제들

이진트리에서 최대(소)값 찾기

public class BinaryTreeHandler {
    public static int getMax(Node head) {
        // 1. Get max value on the left side of the tree
        if(head.left == null) { return head.data;}
        int leftMax = getMax(head.left);

        // 2. Get max value on the right side of the tree
        if(head.right == null) {return head.data;}
        int rightMax = getMax(head.right);        

        // 3. compare with root value / left max value / right max value
        return Math.max(Math.max(leftMax, rightMax),head.data);
    }

}

이진트리가 균형을 이루는가 ?

public class BinaryTreeHandler {
    public static boolean isBalanced(Node root) {
        // Reculsive function will return difference between left side and right side
        // if difference is more than 2, reculsive will return -1.
        return isBalRec(root) != -1;
    }
    private static int isBalRec(Node root ){
        if(root == null){
            return 0;
        }
        int l = isBalRec(root.left);
        if(l == -1) return -1;

        int r = isBalRec(root.right);
        if(r == -1) return -1;
        int diff = Math.abs(r-l);
        if(diff > 1){
            return -1;  
        }
        return Math.max(r, l) +1;
    }
}

오름차순 배열의 BST변환

public class BSTBuilder {
    public static Node build(int[] a) {
        return buildRec(a, 0 , a.length-1);
    }

    // Return sub root node
    private static Node buildRec(int[] a, int l, int r){
        if( r < l )
            return null;

        int m = (r + l) / 2;

        Node leftNode = buildRec(a, l, m-1);
        Node rightNode = buildRec(a, m+1, r);

        return new Node(a[m], leftNode, rightNode);

    }
}

LCA(Least Common Ancestor)

트리 상 두 정점이 있을 때, 두 정점의 공통 조상 노드 중 깊이가 가장 깊은 노드.

트리상에서 두 정점의 거리를 구할 때 사용된다.

static Node lca(Node root,int v1,int v2){
    if(root == null){
        return null;
    }

    Node ans = root;
    if(v1 > ans.data && v2 > ans.data){
        ans= lca(root.right, v1, v2);
    }else if(v1 < ans.data && v2< ans.data){
        ans= lca(root.left, v1,v2);
    }
    return ans;
}