트리의 정의

대상 정보를 계층적으로 구조화시키고자 할 때 사용하는 자료구조가 "트리" 이다.


이 그림의 혈통도는 "가계"라는 대상 정보를 단순히 데이타 요소를 나열하여 표현하지 않고, 데이타 요소들간의 "parent-child" 관계를 계층적으로 표현하고 있다. 혈통도는 "I"를 뿌리로 하여 가지가 갈라져 나온 거꾸로 된 나무 모양을 하고 있기 때문에 "트리(tree)" 구조를 가졌다고 한다. 트리에서 단위 데이타 요소들은 하나의 노드로 표현된다.

트리는 다음과 같이 재귀적으로 정의할 수 있다.

혈통도를 예로 들어 설명하면 "I" 노드는 전체 트리의 루트 노드가 되고, 루트 를 제외한 나머지 노드들은 {father, grand father, grand mother} 집합과 {mother, grand father, grand mother} 의 두 집합으로 나뉘어진다. 이 때 두 개의 집합은 각각 "father" 노드와 "mother" 노드를 루트로 하는 트리가 된다.

용어 설명


차수(degree)
한 노드에 연결된 서브 트리의 개수를 차수라 한다. 예에서 'A' 노드의 차수는 3이고 'G' 노드의 차수는 0이다. 모든 노드의 차수가 2이하인 트리를 특별히 이진 트리(binary tree) 라 한다.
단말 노드(terminal 노드, leaf 노드)
트리의 말단에 위치한 노드를 단말 노드라 한다. 단말 노드는 서브 트리가 없기 때문에 차수가 0이다. 예에서 'E', 'H', 'I', 'G', 'D' 노드는 단말 노드들이다.
부모 노드(parent)
특정 노드에 연결된 바로 상위 노드를 부모 노드라 한다. 예에서 'C' 노드는 'G' 노드의 부모 노드이다.
자식 노드(child)
특정 노드에 연결된 바로 하위 노드를 자식 노드라 한다. 예에서 'H'와 'I'는 'F' 노드의 자식 노드이다.
형제 노드(sibling)
같은 보모를 공유하는 자식 노드들은 형제 노드가 된다. 예에서 'B', 'C', 'D' 노드는 'A' 노드를 공통 부모 노드로 가지고 있으므로 형제 노드이다.
조상 노드(ancestor)
루트 노드로부터 부모 노드까지의 경로에 있는 모든 노드를 조상 노드라 한다. 예에서 'F' 노드의 조상 노드는 'A'와 'B' 노드이다.
후손 노드(descendant)
서브 트리에 있는 모든 노드들은 후손 노드들이다. 예에서 'B' 노드의 후손은 'E', 'F', 'H', 'I' 노드이다.
레벨(level)
루트 노드를 기점으로 한 각 노드의 단계수. 루트 노드의 레벨은 1이다. 예에서 'B', 'C', 'D' 노드의 레벨은 2, 'E', 'F', 'G' 노드의 레베은 3, 'H', 'I' 노드의 레벨은 4이다.
높이(깊이)(height, depth)
트리의 최대 레벨수를 트리의 높이(깊이)라 한다. 예의 트리는 높이가 4이다.

리스트 표현 방법
left child, right sibling 표현 방법
이진 트리 표현 방법

리스트 표현 방법

트리를 다음과 같은 형식의 리스트를 이용하여 재귀적으로 표현한다.

(루트노드(서브 트리1, 서브 트리2, .... , 서브 트리n))

서브 트리도 트리이므로 이러한 리스트가 중첩되어 표현된다.

<예제 트리>


위의 트리를 리스트 표현 방법으로 표시하면 다음과 같다.

( A ( B ( E , F ) , C ( G ) , D ) )

리스트 표현 방법을 사용할 경우 하나의 서브 트리를 표현하기 위한 노드 구조는 다음과 같다.


예제 트리를 내부적으로 표현하면 다음과 같다.


각각의 노드는 가변적인 포인터 수를 가지므로 효율적인 표현 방법이 되지 못한다. 이 문제를 해결하기 위해 포인터 수를 2개로 고정한 방법이 left child, right sibling 표현 방법과 이진 트리 표현 방법이다.

left child, right sibling 표현 방법

고정된 포인터 수를 가지는 표현 방법으로 다음과 같은 노드 구조를 가진다.


하나의 포인터를 자신의 첫번째 child 노드를 가리키고, 또 하나의 포인터는 인접한 sibling 노드를 가리키도록 한다.


예로 든 트리를 left child, right sibling 표현 방법으로 표시하면 다음과 같다.


포인터의 수가 2개로 고정되어 있으므로 리스트 표현 방법보다 효율적이다.

이진 트리 표현 방법

right sibling 을 right child 로 표시하는 것을 제외하고는 left child, right sibling 표현 방법과 동일한 표현 방법이다.



이진 트리의 정의
특별한 형태의 이진 트리
이진 트리의 성질
이진 트리의 표현 방법
배열 이용법
리스트 이용법
이진 트리의 순회
inorder 순회
preorder 순회
postorder 순회

이진 트리의 정의

이진 트리는 모든 노드의 차수가 2를 넘지 않는 특수한 트리이다. 하나의 노드는 2개의 자식 노드를 가질 수 있는데, 각각을 왼쪽 자식 노드와 오른쪽 자식 노드라 부른다. 일반 트리에서는 자식 노드들의 순서를 구별하지 않지만 이진 트리에서는 자식 노드의 순서를 구별한다.

<이진 트리의 예>


특별한 형태의 이진 트리

skewed 트리
말단 노드를 제외한 모든 노드들이 한 방향의 자식 노드만 가진 트리

<왼쪽 skewed 트리>


<오른쪽 skewed 트리>


완전 이진 트리(complete binary tree)


full 이진 트리
말단 노드를 제외한 모든 노드들이 왼쪽 자식 노드와 오른쪽 자식 노드를 모두 가지는 트리를 full 이진 트리라 한다.


이진 트리의 성질

  1. i번째 레벨은 최대 2^(i-1)개의 노드를 가질 수 있다.
    레벨이 1인 루트노드는 2개의 자식노드를 가진다. 따라서 레벨 2 노드에는 2^(2-1), 즉 2개의 노드가 올 수 있다.
    각 레벨은 이전 레벨의 최대 노드 수보다 2배 많은 노드를 가질 수 있다.
    따라서 i번째 레벨에는 2^(i-1)개의 노드가 존재할 수 있다.

    <예제 트리>


    예의 트리에서 점선으로 표시된 노드들은 앞으로 삽입될 노드들을 표시하고 있다.
    레벨3에는 현재 2개의 노드가 있지만 앞으로 2개가 더 삽입될 수 있으므로 레벨3의 최대 노드 수는 2^(3-1)=4개이다.
    레벨4에는 현재 1개의 노드가 있지만 앞으로 7개가 더 삽입될 수 있으므로 레벨4의 최대 노드 수는 2^(4-1)=8개이다.

    1. 깊이가 k인 이진 트리의 최대 노드 수는 2^(k-1)이다.
    깊이가 k인 이진 트리의 최대 노드 수는 각 레벨의 최대 노드 수를 합산한 것이다. 예의 트리에서 현재 노드 수는 6이지만, 점선으로 표시된 노드를 포함하는 최대 노드 수는 2^4-1=15개이다.

    깊이가 k이고, 노드 수가 2^k-1인 트리를 "full binary" 트리라 부른다.

이진 트리의 표현 방법

배열을 이용한 이진 트리의 표현
연결 리스트를 이용한 이진 트리의 표현

배열을 이용한 이진 트리 표현

고정크기의 기억장소를 가지는 배열을 사용할 경우 각 항목들의 순서는 상위 레벨에서 하위 레벨로, 같은 레벨 의 경우는 왼쪽에서 오른쪽으로 증가한다. <노드의 순서>


연결 리스트를 이용한 이진 트리 표현

이진 트리의 순회(traversal)

트리 순회
이진 트리의 순회는 일정한 순서로 트리의 모든 노드들을 오직 한번씩만 방문하는 것이다. 트리의 순회는 트리 구조로 된 정보의 검색이나 수식 처리등에 유용하게 사용된다.
트리 순회의 방법
트리 순회는 노드를 방문하는 순서에 따라 다음의 3가지로 분류할 수 있다.
  1. inorder 순회
  2. preorder 순회
  3. postorder 순회

inorder 순회

inorder 순회의 원리
특정 노드에서 자신의 왼쪽 서브 트리를 모두 방문하고, 자기 노드를 방문한 후에 오른쪽 서브 트리를 방문한다. 이 원리를 모든 노드에 재귀적으로 적용하면 모든 노드들을 한번씩 방문할 수 있다.
inorder 순회의 동작 : 그림을 마우스로 클릭하세요

preorder 순회

preorder 순회의 원리
특정 노드에서 먼저 자기 노드를 방문하고, 왼쪽 서브 트리를 모두 방문하고, 마지막으로 오른쪽 서브 트리를 모두 방문한다. 이 원리를 ㅤ모든 노드에 재귀적으로 적용하면 모든 노드를 한번씩 방문할 수 있다.
preorder 순회의 동작 : 그림을 마우스로 클릭하세요

postorder 순회

postorder 순회의 원리
특정 노드에서 자신의 왼쪽 서브 트리와 오른쪽 서브 트리를 차례로 방문한 후, 마지막으로 자신의 노드를 방문한다. 이 원리를 모든 노드에 재귀적으로 적용하면 각 노드를 한번씩 방문할 수 있다.
postorder 순회의 동작 : 그림을 마우스로 클릭하세요

이진 탐색 트리

이진 탐색
이진 탐색 트리의 정의
이진 탐색 트리의 연산
검색
삽입
삭제

이진 탐색(binary 검색)

서로다른 키값을 가지는 노드들 중에서 원하는 key값을 가지는 노드를 찾는 방법으로는 선형 탐색과 이진 탐색이 있다.


위의 그림처럼 각 노드들이 순서대로 정렬되어 있으면 다음과 같은 방법으로 특정 노드를 찾을 수 있다.

  1. N개의 노드중 N/2번째 노드를 선택한다. 그러면 원래 리스트는 (1번 ~ N/2 -1 번) 노드그룹과 (N/2 +1번 ~ N번)` 노드 그룹으로 나눠진다.
  2. N/2 번째 위치에 원하는 노드가 있으면 그것을 반환한다.
  3. N/2 번째 노드의 키가 탐색하는 키보다 작은 경우는 { 1 ~ N/2 -1 } 그룹을 탐색할 필요가 없다. 따라서 { N/2 + 1 ~ N } 그룹에 대해서 1단계부터 다시 탐색을 한다.
  4. N/2 번째 노드의 키가 탐색하는 키보다 큰 경우는 { N/2 +1 ~ N } 그룹을 탐색할 필요가 없다. 따라서 { 1 ~ N/2 -1 } 그룹에 대해 1단계부터 다시 탐색한다.

    <키가 55인 노드를 검색>

    그림을 마우스로 클릭하세요

선형탐색(linear 검색)

서로 다른 키값을 가지는 노드들 중에 원하는 키를 가지는 노드를 찾는 방법으로는 선형탐색과 이진 탐색이 있다.


위의 그림처럼 각 노드들이 아무런 순서 없이 나열되어 있으면 특정 노드를ㅤ찾기 위해 처음부터 그 노드가 있는 위치까지 모든 노드를 검색해야 한다. 예를 들어 24를 찾으려면 4번, 19를 찾으려면 9번의 검사가 필요하다. 이러한 탐색방법을 선형탐색(linear 검색)라고 한다.

이진 탐색 트리의 정의

이진 탐색 트리는 이진 트리의 일종으로 다음과 같은 성질을 가진다.

  1. 모든 노드는 유일한 키값을 가진다.
  2. 루트 노드의 왼쪽 서브 트리에 있는 노드는 모두 루트 노드보다 작은 키값을 가진다.
  3. 루트 노드의 오른쪽 서브 트리에 있는 노드는 모두 루트 노드보다 큰 키값을 가진다.
  4. 오른쪽 서브 트리와 왼쪽 서브 트리도 이진 탐색 트리이다.

이진 탐색 트리는 이진 탐색을 쉽게 하도록 만들어진 트리이다. 이진 탐색 방법에서 N/2번째 노드에 해당하는 것이 루트 노드이고, {1 ~ N/2 -1}그룹에 해당되는 것은 왼쪽 서브 트리, { N/2 +1 ~ N } 그룹에 해당되는 것은 오른쪽 서브 트리이다. 그러나 이진 탐색 트리는 왼쪽 서브 트리와 오른쪽 서브 트리의 갯수가 항상 같지는 않다.

이진 탐색 트리의 예


이진 탐색 트리의 연산

검색
삽입
삭제

이진 탐색 트리의 연산(1)

검색(search>

이진 탐색 트리에서 특정 노드를 찾기 위해서는 다음과 같은 단계를 ㅤ거친다.

  1. 현재 서브 트리의 루트와 키값을 비교한다.
  2. 루트의 키값과 검색 키가 같으면 루트값을 반환한다.
  3. 루트의 키보다 검색 키가 작으면 왼쪽 서브 트리를 검사한다.
  4. 루트의 키보다 검색 키가 크면 오른쪽 서브 트리를 검사한다.

    <키값이 65인 노드를 검색>

    그림을 마우스로 클릭하세요

이진 탐색 트리의 연산(2)

삽입(insert)

특정 노드를 이진 탐색 트리에 삽입하려면 같은 키값을 가지는 노드가 없어야 한다. 그러므로 다음과 같은 방법으로 동일한 키를 가지고 노드의 존재여부와 삽입할 위치를 알아낸다.

  1. 현재 서브 트리의 루트와 키값을 비교한다.
  2. 루트의 키값과 검색 키가 같으면 동일 키를 가진 노드가 존재하는 것이므로 삽입이 불가능하다.
  3. 루트이 키보다 검색 키가 작으면 왼쪽 서브 트리를 검사한다.
  4. 루트의 키보다 검색 키가 크면 오른쪽 서브 트리르 검사한다.
  5. 더이상 검사할 노드가 없을 때, 즉 말단 노드에 도달한 경우 그 위치가 삽입할 위치이다.

삽입할 위치를 찾았으면 새로운 노드를 삽입한다.

이진 탐색 트리의 연산(3)

삭제(delete)

특정 키값을 가지는 노드를 이진 탐색 트리로부터 삭제하려면 면저 검색 연산을 하여 삭제할 노드를 찾아낸다. 특정 노드를 삭제하는 것은 다음의 3가지 경우중 하나에 해당된다.

  1. 삭제하려는 노드가 말단 노드인 경우
  2. 삭제하려는 노드가 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우
  3. 삭제하려는 노드가 두개의 서브 트리를 모두 가지고 있는 경우

삭제하려는 노드가 말단 노드인 경우

삭제하려는 노드가 말단 노드인 경우는 해당 노드만 삭제해준다.

<삭제전>



<삭제후>



삭제하려는 노드가 왼쪽이나 오른쪽 서브 트리중 하나만 갖고 있을 경우

자기 노드는 삭제하고 서브 트리는 자기 노드의 부모 노드에 붙여준다.

<삭제전>



<삭제후>



삭제하려는 노드가 두개의 서브 트리를 모두 가지고 있는 경우

자기 노드를 삭제한후 두개의 서브 트리를 하나로 합하여 부모 노드에 붙여준다. 합한 서브 트리의 루트노드는 왼쪽 서브 트리에서 가장 큰 키값을 가지는 노드나, 오른쪽 서브 트리에서 가장 작은 키값을 가지는 노드가 된다.

<삭제전>



<삭제후1>



<삭제후2>