트리에 관하여...(개요, 용어, 종류, 이진 트리의 종류, 이진 탐색 트리, 트리 운행법, 수식 표기법)

*글을 시작하기에 앞서,
이 글은 자료구조로써의 트리만을 다루고,

정처기 시험용으로써

기본적인 것만 설명함을 알려드립니다.

 

 

트리(Tree) 란?

  트리는 점 (Node) 과 선분 (Branch) 으로 이루어진,

  사이클을 이루지 않는 그래프 형태를 말합니다.

  아래 그림에 보이듯이 트리는

  여러개의 갈래로 뻗어나가는 비선형 구조입니다.

  사이클이란, 말그대로 순환하는 형태를 말하고,

  노드는 각자 별개의 기억공간이며,

  노드를 연결하는 브랜치를 링크(Link) 라고도 합니다.

 

 

트리의 용어들 정리.

  아래 그림으로 나타내 보았습니다.

  그림에 깜빡하고 안썼는데, Level 은 트리의 각 단계를 말하고, 

  4 가 가장 아래이므로 트리의 깊이가 됩니다.

  또한 트리의 크기 (Size) 를 묻는다면, 노드의 총 개수를 말합니다.

 

 

트리의 종류.

  이진트리와 삼항트리,

  혹은 그 이상도 가능하나,

  많이 쓰이는 이진 트리 위주로 다루겠습니다.

  (삼항 이상이 거의 쓰이지 않는다기 보다는,

  정처기 수준에서 나오지 않는다는 표현이 더 명확할 것 같습니다.) 

  *이 트리 자체는 최대 차수가 3이기 때문에 삼항 트리이며,

  빨간색 박스 외에도 [ b, e, f, j, k, l ] 이나, [ d, h, i, m, n ] 도 이진 트리입니다.

 

 

이진 트리의 종류.

  이진 트리의 종류에는 크게 세가지가 있습니다.

  이 외의 트리는 이름이 있기도 하나,

  구체적으로 다루는 경우가 잘 없습니다.

  (이 말 역시 정처기 기준입니다.)

  *이 외에도 정의된 종류가 몇가지 있고,

  같은 종류를 다르게 부르는 별칭들도 있으나,

  오히려 혼란만 가중시킬 수 있어 가장 대중적인 것만 다루었습니다.

 

 

이진 탐색 트리 (Binary Search Tree)

  이진 탐색 트리는,

  이진 트리의 구조를 활용해

  원하는 수를 빠르게 찾을 수 있는 트리입니다.

  *그림은 아주 좁은 범위로 만들어서 큰 효용을 느끼기 힘들지만,

  엄청 넓은 범위에서 하나의 숫자를 찾는다고 가정하고 상상해보면

  왜 이진 탐색 트리를 쓰는지 알 수 있습니다.

 

 

힙 (Heap)

  힙은 퀵 정렬에서 쓰이는 트리 구조입니다.

  퀵 정렬에서 최대힙을 사용하면 오름차순,

  최소힙은 내림차순 정렬이 가능합니다.

  *힙 그 자체로 정렬이 되는 것은 아니고,

  힙을 만든 뒤 0번째와 마지막 원소의 교환,

  마지막 원소 제외 후 다시 힙 만들기 -> 반복

  이런 식으로 정렬을 만들 수 있습니다.

 

 

이진트리의 운행법과 수식의 표기법

  이진트리의 운행법이라 함은,

  트리의 원소를 순차적으로 옮겨다닐 때,

  각 노드에 들르는 순서를 정의한 것을 의미합니다.

  대표적으로는 3가지가 있습니다.

• Preorder : 부모 노드를 먼저 들름. (Root> Left> Right)
• Inorder : 부모 노드를 중간에 들름.  (Left> Root> Right)
• Postorder : 부모 노드를 마지막에 들름. (Left> Right> Root)

 

  그리고 동일한 개념으로,

  수식의 표기법에도 3가지가 있습니다.

• 전위식 : 연산자를 먼저 씀. (연산자> Left> Right)
• 중위식 : 연산자를 중간에 씀. (Left> 연산자> Right)
• 후위식 : 연산자를 나중에 씀. (Left> Right> 연산자)

  (*우리가 일반적으로 쓰는 것이 중위식 표기법입니다.)

 

  역시 이해를 돕기 위해 그림을 준비했습니다.

 

 

  위 그림을 통해 운행법의 개념을 익힐 수 있고,

  동일한 개념을 이용해 수식 표기법을 이해할 수 있습니다.

  아래에 간단한 그림을 준비했습니다.

  *수식 표기법은 괄호를 활용하는 것이

  틀리는 것을 방지하기 좋습니다.

 

  응용해서 조금 더 어려운 수식을

  각각 전위, 중위, 후위로 바꿔보겠습니다.

 

  X = A * (B - C / D) + E 라는 중위식이 있습니다.

  이것을 전위식으로 바꾸면,

  X = ((A * (B - (C / D))) + E) 로 각각 괄호로 묶은 뒤에,

  내부의 괄호부터 순서대로 바꿔줍니다.

 

  X = ((A * (B - (/ C D))) + E)

  X = ((A * (- B (/ C D))) + E)

  X = ((* A (- B (/ C D))) + E)

  X = (+ (* A (- B (/ C D))) E)

  = X (+ (* A (- B (/ C D))) E)

 

  이제 괄호를 없애주면,

   = X + * A -B / C D E

  가 됩니다.

  

  같은 방법으로 후위식으로도 바꿔본다면,

  X = ((A * (B - (C / D))) + E) 에서

 

  X = ((A * (B - (C D /))) + E)

  X = ((A * (B (C D /) -)) + E)

  X = ((A (B (C D /) -) *) + E)

  X = ((A (B (C D /) -) *) E +)

  X ((A (B (C D /) -) *) E +) =

 

마찬가지로 괄호를 없애주면,

   X A B C D / - * E + =

  이 됩니다.

 

  전위식에서 후위식이나

  후위식에서 전위식으로의 변환도

  같은 방법을 사용해서 가능합니다.

 

  이번엔 다른 식을 사용해보겠습니다.

 

  X A B C + D / E - * = 라는 후위식이 있습니다.

  똑같이 괄호를 만드는데,

  중위식의 괄호를 만들 때와 똑같이,

  내부 괄호부터 만들면 어렵지 않습니다.

  

  X A (B C +) D / E - * =

  X A ((B C +) D /) E - * =

  X A (((B C +) D /) E -) * =

  

  X (A (((B C +) D /) E -) *) =

  이제 이것을 활용해서

  전위식과 중위식으로 바꿀수 있는데,

  똑같이 내부 괄호부터 하나씩 바꾸면 됩니다.

 

  X (A (((+ B C) D /) E -) *) =

  X (A ((/ (+ B C) D) E -) *) =

  X (A (- (/ (+ B C) D) E) *) =

  X (* A (- (/ (+ B C) D) E)) =

  = X (* A (- (/ (+ B C) D) E))

 

 

  여기서 괄호를 제거한

  = X * A - / + C B D E

  가 전위식이고,

 

   X (A (((C + B) D /) E -) *) =

   X (A (((C + B) / D) E -) *) =

   X (A (((C + B) / D) - E) *) =

   X (A * (((C + B) / D) - E)) =

   X = (A * (((C + B) / D) - E))

 

 

  마찬가지로 필요없는 괄호를 제거하면,

   X = A * ((C + B) / D - E)

  로써 우리에게 익숙한 중위식이 됩니다.

 

  적힌 것만 보면 어지러울 수 있는데,

  직접 손으로 적어보면 어렵지 않습니다.

 

 

 

 

 

  이로써 트리와,

  트리의 운행법과 그 개념을 응용한

  수식 표기법을 설명한 글을 마치겠습니다.

  읽어주셔서 감사합니다.