JAVA 자료구조 : 이진 검색 트리 (이진 탐색 트리)

스터디사이트 : https://www.hackerrank.com

JAVA 자료구조 : 이진 검색 트리 (이진 탐색 트리)

주어진 이진검색트리 중 가장 깊은 깊이를 가진 노드의 높이를 구하라.

이진검색트리

각 노드가 최대 2개의 자식(Child) 노드를 가질 수 있는 트리

이진 탐색 트리에서 새로운 노드는 루트 노드부터 비교를 거쳐, 

비교된 노드 보다 

더 크면 오른쪽 서브 트리로 이동하고, 

작으면 왼쪽 서브 트리로 이동해서 계속 크기 비교 후, 알맞은 자리에 삽입된다. 

입력

7

3

5

2

1

4

6

7

출력

3

해당 이진검색트리의 최대 깊이 : 3

※ 주어진 코딩

지정한 영역에서만 코딩하시오

class Node{

    Node left,right;

    int data;

    Node(int data){

        this.data=data;

        left=right=null;

    }

}

class Solution{

    public static int getHeight(Node root){

      * 이곳에 코딩 *    

    }

    public static Node insert(Node root,int data){

        if(root==null){

            return new Node(data);

        }

        else{

            Node cur;

            if(data<=root.data){

                cur=insert(root.left,data);

                root.left=cur;

            }

            else{

                cur=insert(root.right,data);

                root.right=cur;

            }

            return root;

        }

    }

    public static void main(String args[]){

        Scanner sc=new Scanner(System.in);

        int T=sc.nextInt();

        Node root=null;

        while(T-->0){

            int data=sc.nextInt();

            root=insert(root,data);

        }

        int height=getHeight(root);

        System.out.println(height);

    }

}

insert(Node root, int data) 메소드 파헤치기

주어진 코딩에서 insert(Node root, int data) 메소드는 Linked List의 개념이다.

if(data<=root.data){    ← 입력된 현재 int값(data)이 전에 추가된 Node의 int값(data)보다 작을때

cur=insert(root.left,data); 

└ 현재 존재중인 Node의 left와 현재 data를 이용해서 다시 insert() 메소드를 돌린다. 

만약. root.left가 null이면 새로운 Node를 추가해서 현재 data를 그 추가된 Node에다 집어넣는다.

else. root.left가 not null이면 다시 insert() 메소드를 돌린다.

  ※ 이렇게 root.left가 null이 나올때까지 insert() 메소드 실행을 반복하고, 

      결국에는 new Node(data)를 통하여 새로운 Node에 data를 집어넣는 방식이다.

└ 가장 최근에 삽입 or 수정된 Node를 지정하기 위해 포인터 역할을 하는 cur Node변수에다가 새롭게 추가된 노드의 내용을 넣고, ↓↓

root.left=cur;    ← root.left는 cur의 내용이 들어가게 된다.

}else{        ← 입력된 현재 int값(data)이 전에 추가된 Node의 int값(data)보다 클때

cur=insert(root.right,data); 

root.right=cur;

└ 바로 위의 if조건과 같은 원리로 동작한다.

} 

insert(Node root, int data) - 디버깅 

위의 입력 예를 보면서 디버깅을 해보자.

class Node{ Node left,right; int data; Node(int data){ this.data=data; left=right=null; } } //end class Node1 class Solution { public static Node insert(Node root,int data){ if(root==null){ System.out.println(" * New Node created"); return new Node1(data); } else{ Node cur; if(data<=root.data){ System.out.printf(" data <= root.data --- data:%d, root.data:%d root.left ← data\n", data, root.data); cur=insert(root.left,data); root.left=cur; }else{ System.out.printf(" data > root.data --- data:%d, root.data:%d root.right ← data\n", data, root.data); cur=insert(root.right,data); root.right=cur; } return root; } } //end insert() public static void main(String[] args) { Scanner sc=new Scanner(System.in); int T=sc.nextInt(); Node root=null; while(T-->0){ int data=sc.nextInt(); System.out.println("T : "+ T); System.out.printf(" %d ) data : %d\n",T,data); root=insert(root,data); String left=""; String right=""; if(root.left==null) left="null"; else left=String.valueOf(root.left.data); if(root.right==null) right="null"; else right=String.valueOf(root.right.data); System.out.printf(" %d ) root.left.data : %s , root.right.data : %s\n", T, left, right); } } //end main() }

결과 :  아래는 실제 이진검색트리가 만들어지는 과정을 콘솔 디버깅과 비교하여 그려보았다. 노란색 하이라이트 된 부분에 현재 입력된 값 , 현재 Node의 data값, 입력된 값이 삽입될 곳이 나와있으며, 이 정보가 새로운 노드가 만들어지면서 들어가게 된다.

getHeight(root); - 파헤치기 & 디버깅

getHeight(root) 는 본인이 직접 코딩해야 하는 부분이다 허허..

위의 insert()의 디버깅에서 볼수 있듯이 우선 root변수는 가장 상위의 노드가 지정이 되어있고 그 노드에 대한 값이 들어가 있다.

그렇다면 이 getHeight() 메소드에서 

노드의 left, right 노드의 존재를 확인 한 후, 존재하면 준비해 놓은 left용카운트와 right용카운트에 1씩 추가한다.

노드 안의 노드를 이동하면서 그노드에서 가지를뻗은 left와 right를 확인하는 방식이기때문에,

비교를 위한 노드객체 ( pointer ) 를 하나 만들어서 반복분을 이용하여 비교 해 보았다.

public static int getHeight(Node root){ int leftcnt=0; int rightcnt=0; Node pointer = root; System.out.printf("root.left.data : %d , root.right.data : %d\n", root.left.data, root.right.data); while(pointer != null){ if(pointer.right != null){ rightcnt++; pointer = pointer.right; System.out.printf("Right ] pointer.data : %d\n", pointer.data); }else if(pointer.left != null){ leftcnt++; pointer = pointer.left; System.out.printf("Left ] pointer.data : %d\n", pointer.data); }else{ pointer = null; } //end if } // end while System.out.printf("leftcnt : %d , rightcnt : %d\n", leftcnt, rightcnt); return leftcnt >= rightcnt ? leftcnt : rightcnt; } //end getHeight()

결과 :  root.left.data : 2 , root.right.data : 5 Right ] pointer.data : 5 Right ] pointer.data : 6 Right ] pointer.data : 7 leftcnt : 0 , rightcnt : 3

그런데 여기서 문제를 발견한 것은,

pointer Node객체가 노드 안의 노드로 이동을 하면서 비교를 하는데, 정작 상위노드, 그 상위노드로 올라가게 할 수 있는 뾰족한 방법이 안 나는 것이다. 게다가 간편한 코딩이 되어야 할텐데 그거는 이미 글렀고..

그래서 다른 사람들이 한 코딩을 보았다.. ㅎ

해당 메소드는 insert()처럼 메소드 안에서 자신의 메소드를 다시 호출하는 방식을 채택하고 있다..

그래서 흘러가는 구조를 그림으로 그려보았다..

주의할 것은,

getHeight() 파라미터에 Node값이 null값이면 리턴되는 값이 -1 인데,

이 리턴되는 -1은 leftDepth도 rightDepth도 아닌 그냥 숫자 -1이다.

이걸 혼동해서 최종 결과를 2로 생각해가지고 "이거 틀린 코딩아냐?" 라고 고민했던 나자신을 반성한다..

public static int getHeight(Node root){ if(root == null) {    return -1; } else{    int leftDepth  = 1 + getHeight(root.left);    int rightDepth = 1 + getHeight(root.right);    return (leftDepth > rightDepth ? leftDepth : rightDepth ); } } //end getHeight()

결과

class Node{ Node left,right; int data; Node(int data){ this.data=data; left=right=null; } } class Solution{ public static int getHeight(Node root){ if(root == null) { return -1; } else{ int leftDepth = 1 + getHeight(root.left); int rightDepth = 1 + getHeight(root.right); return (leftDepth > rightDepth ? leftDepth : rightDepth ); } } //end getHeight() public static Node insert(Node root,int data){ if(root==null){ return new Node(data); } else{ Node cur; if(data<=root.data){ cur=insert(root.left,data); root.left=cur; } else{ cur=insert(root.right,data); root.right=cur; } return root; } } public static void main(String args[]){ Scanner sc=new Scanner(System.in); int T=sc.nextInt(); Node root=null; while(T-->0){ int data=sc.nextInt(); root=insert(root,data); } int height=getHeight(root); System.out.println(height); } }

결과 :  3