[data structure] 자료구조 트리(Tree), 이진트리(Binary Tree) 알고리즘 이란?? (java로 구현)

Q. 이진트리(Binary Tree) 에 대해 알아보자.

1. 트리(Tree) ??

2. 이진트리(Binary Tree) ??

3. 이진트리 탐색방식(in-order, post-order, pre-order, level-order)

4. 이진트리와 함께하는 대표적인 기능들(add, delete)

5. 이진트리의 탐색 기능(in-order, post-order, pre-order, level-order)

6. 이진트리의 부가적인 기능들(getLevel, getMax)

1. 트리(Tree) ??

트리란, 1개 이상의 노드로 이루어진 유한 집합이다.

말로 설명하면 어려우니 아래 그림을 보겠습니다.

각 동그라미를 노드(node)라고 합니다.

A노드, B노드.... H노드까지 8개의 노드가 있습니다.

각 노드들은 부모노드(parent node)와, 자식노드(child node)를 가지고 있습니다.

B노드를 기준으로 설명하자면,

B노드의 부모노드는 A노드이고,

B노드의 자식노드는 E노드, F노드 입니다.

A노드는 가장 위에 있고 부모노드가 없는 유일한 노드이기 때문에,

루트(root) 라는 이름을 가지고 있습니다.

A노드의 자식의 개수는 3개 입니다.

이를 또다른 말로 차수(degree) 라고 하는데,

A노드의 차수는 3 이라고 합니다.

(D노드의 차수는 2)

차수가 0인 가장 마지막에 있는 노드를 리프(leaf) 또는 단말노드(terminal node)라고 합니다.

트리의 깊이(height) 를 나타내는 말로는 레벨(level) 이 있습니다.

루트인 A노드를 1로 하고 가장 아래 자식 노드가 있을때까지는 세어보면,

레벨이 나옵니다. 위, 트리는 레벨이 3 이라고 합니다.

2. 이진트리(Binary Tree) ??

위에서 한참 트리에 대해 설명을 해드렸는데요,

트리와 이진트리는 다르지 않습니다.

대신 가장 중요한 차이점은,

트리는 1개 이상의 노드를 가질수 있지만,

이진 트리는 1개 이상 2개 이하의 노드만 가질수 있습니다.

아래 그림은 각 노드가 자식노드를 2개이하로 갖고 있는 이진 트리의 모습입니다.

이진트리를 조금 다르게 표현하면,

이진트리는 차수(degree)를 2 이하로만 갖을수 있다.

이진트리의 최대 노드수는 아래와 같이 구할수 있습니다.

레벨(i)을 알고 있을 때

레벨이 3인 트리는 2의 3제곱승 - 1 = 7 이 나오게 됩니다.

포화이진트리(perfect binary tree)는,

모든 리프(단말)노드가 같은 레벨에 있을때를 말합니다.

아래 그림이 바로 포화이진트리 입니다.

완전이진트리(complete binary tree)는,

포화이진트리에서 끝부분을 제외하고 다른것이 남아 있는 트리입니다.

그러니까 왼쪽에서 오른쪽으로 번호를 매겼을때,

그 번호가 연속성이 있는 경우 완전이진트리가 됩니다.

3. 이진트리 탐색방식(in-order, post-order, pre-order, level-order)

이진트리를 순회(탐색)하는 방식에는 크게 4가지가 있습니다.

• in-order 방식
• post-order 방식
• pre-order 방식
• level-order 방식

이렇게 4가지가 있습니다.

자신 노드를 V라 하고, 왼쪽 자식 노드를 L,

오른쪽 자식노드를 R 이라고 가정하고 설명하겠습니다.

1) in-order 방식(LVR)

in-order 방식은 왼쪽, 자신, 오른쪽 노드를 순차적으로 방문하는 탐색 방식입니다.

위 트리를 in-order 방식으로 탐색한다면,

123456789 순서대로 방문합니다.

2) post-order 방식(LRV)

post-order 방식은 왼쪽, 오른쪽, 마지막으로 자기 자신 노드를 탐색합니다.

위 트리를 post-order 방식으로 탐색한다면,

1 2 4 3 6 9 8 7 5 순서대로 방문합니다.

3) pre-order 방식(VLR)

pre-order 방식은 자신, 왼쪽, 오른쪽 노드를 차례대로 탐색합니다.

위 트리를 pre-order 로 방문한다면,

5 3 2 1 4 7 6 8 9 순서대로 방문합니다.

4) level-order 방식

level-order 방식은 다른 방식과 달리

루트 레벨부터 왼쪽부터 차례대로 탐색하는 방식입니다.

위 트리를 level-order 방식으로 탐색하면,

5 37 2468 19 순서대로 방문을 합니다.

4. 이진트리와 함께하는 대표적인 기능들(add, delete)

이제 실제로 구현해보겠습니다.

우선 대표적인 기능에는

트리에 노드를 추가하는 add

트리의 노드를 삭제하는 delete

이 두 기능이 있습니다.

※ 트리는 이진트리로 구성되고, data는 int 형이다.

※ 중복값은 add 하지 않는다.

※ 새 값이 자기 자신의 값보다 작으면 왼쪽 자식노드 보낸다.

※ 새 값이 자기 자신보다 크면 오른쪽 자식노드로 보낸다.

※ delete 시 해당노드의 자식노드가 있더라도 같이 삭제 된다.

먼저 add 는 다음과 같이 구성됩니다.

public void add( int data ) { if( root == null ) { TreeNode newNode = new TreeNode( data ); root = newNode; return; } TreeNode node = root; for( ;; ) { if( node.data == data ) break; else if( node.data < data ) // ① { if( node.right == null ) { TreeNode newNode = new TreeNode( data ); node.right = newNode; break; } else node = node.right; } else if( node.data > data ) // ② { if( node.left == null ) { TreeNode newNode = new TreeNode( data ); node.left = newNode; break; } else node = node.left; } } }

① : 새로 들어온 data가 기존의 값보다 크기 때문에 오른쪽 자식 노드 쪽에 넣는다.

② : 새로 들어온 data가 기존의 값보다 작기 때문에 왼쪽 자식 노드 쪽에 넣는다.

두번째로 delete 는 이렇게 구성됩니다.

public void delete( int data ) { if( root == null ) { // System.out.println( "isEmpty" ); return; } if( root.data == data ) { root = null; return; } TreeNode node = root; for( ;; ) { if( node.right == null && node.left == null ) { // System.out.println( "Not Found value" ); return; } if( node.data < data ) // ① { if( node.right.data == data ) { node.right = null; break; } else node = node.right; } else if( node.data > data ) // ② { if( node.left.data == data ) { node.left = null; break; } else node = node.left; } } }

① : 새로 들어온 data가 기존의 값보다 크기 때문에 오른쪽 자식 노드의 값을 비교한다.

② : 새로 들어온 data가 기존의 값보다 작기 때문에 왼쪽 자식 노드의 값을 비교한다.

5. 이진트리의 탐색 기능(in-order, post-order, pre-order, level-order)

1) in-order 방식(LVR)

public void inOrderPrint() { System.out.println( "## in-order(LVR) ##" ); inOrder( root ); System.out.println(); System.out.println(); } private void inOrder( TreeNode node ) { if( node != null ) { inOrder( node.left ); // ① System.out.print( node.data ); inOrder( node.right ); // ② } }

① : 자기 자신을 node.left 바꿔 재귀(recursion)호출을 한다.

② : 자기 자신을 node.right 바꿔 재귀(recursion)호출을 한다.

2) post-order(LRV)

public void postOrderPrint() { System.out.println( "## post-order(LRV) ##" ); postOrder( root ); System.out.println(); System.out.println(); } private void postOrder( TreeNode node ) { if( node != null ) { postOrder( node.left ); // ① postOrder( node.right ); // ② System.out.print( node.data ); } }

① : 자기 자신을 node.left 바꿔 재귀(recursion)호출을 한다.

② : 자기 자신을 node.right 바꿔 재귀(recursion)호출을 한다.

3) pre-order(VLR)

public void preOrderPrint() { System.out.println( "## pre-order(VLR) ##" ); preOrder( root ); System.out.println(); System.out.println(); } private void preOrder( TreeNode node ) { if( node != null ) { System.out.print( node.data ); preOrder( node.left ); // ① preOrder( node.right ); // ② } }

① : 자기 자신을 node.left 바꿔 재귀(recursion)호출을 한다.

② : 자기 자신을 node.right 바꿔 재귀(recursion)호출을 한다.

4) level-order

public void levelOrderPrint() { System.out.println( "## level-order ##" ); levelOrder( root ); System.out.println(); System.out.println(); } private void levelOrder( TreeNode node ) { ArrayList<TreeNode> queue = new ArrayList<TreeNode>( getMax() ); if( node == null ) { System.out.println( "Tree is Empty" ); return; } queue.add( node ); int pos = 0; int size = 0; for( ;; ) { size = queue.size(); if( pos == size ) return; else node = queue.get( pos++ ); // ① if( node != null ) { System.out.print( node.data ); if( node.left != null ) queue.add( node.left ); // ② if( node.right != null ) queue.add( node.right ); // ③ } else break; } }

level-order 방식은 노드를 만날때마다 큐(queue)에 넣어

차례대로 빼어사용하는 방식입니다.

① : 큐에 가장 처음 넣은 값을 뺍니다.

② : 왼쪽 노드를 차례대로 큐에 넣습니다.

③ : 오른쪽 노드를 차례대로 큐에 넣습니다.

6. 이진트리의 부가적인 기능들(getLevel, getMax)

현재 트리의 레벨 과 최대 노드 개수를 가져오는 메소드도 작성해보았습니다.

먼저 getLevel 입니다.

private int level = 0; public int getLevel() { level = 0; getLevel( root ); return level; } private void getLevel( TreeNode node ) { int _level = level; if( node == null ) level = 0; else { _level++; getLevel( node.left ); // ① getLevel( node.right ); // ② if( level < _level ) // ③ level = _level; } }

① : node.left 를 파라미터로 넘겨 재귀(recursion)호출을 합니다.

② : node.right 를 파라미터로 넘겨 재귀(recursion)호출을 합니다.

③ : 현재 탐색한 레벨이 기존 갖고 있는 레벨보다 크다면 레벨값을 교체합니다.

두번째로 getMax 입니다.

public int getMax() { int level = getLevel(); // ① if( level <= 0 ) return 0; else return (int)Math.pow( 2, level ) - 1; // ② }

① : 우선 getLevel 을 통해서 현재 트리의 레벨을 가져옵니다.

② : 최대 노드를 구하는 수식을 이용하여 최대 노드개수를 구합니다.

※ 결론

이번 트리를 구현하면서 느낀것은 생각보다 어렵습니다.

현재 단계에서는 간단히 구현했지만,

delete 시 삭제될 값을 대체하는 노드가 그 자리를 메꾸면서

정렬을 해야하는 등 많은 고려사항이 있습니다.

이것이라도 충분히 이해하고 지나가야겠습니다.