C++로 쉽게 풀어쓴 자료구조/ 트리

트리(Tree)의 개념

트리는 계층적인 자료를 표현하는데 이용되는 자료구조이다.

인공지능 문제에서도 트리가 사용되는데, 대표적인 것이 결정 트리(decision tree)이다. 결정 트리는 인간이나 컴퓨터의 의사결정 구조를 표현하는 한 가지 방법이다.

트리의 용어들

트리의 구성 요소를 노드(node)라고 한다. 트리는 한 개 이상의 노드로 이루어진 유한 집합이다. 이들 중 하나의 노드는 루트(root) 노드라 불리고 나머지 노드들은 서브트리(subtree)라고 불린다. 아래 그림에서 계층적인 구조에서 가장 높은 곳에 있는 노드인 A가 루트가 된다.

트리에서 루트와 서브트리는 선으로 연결된다. 이 연결선을 간선 또는 엣지(edge)라고 한다.

노드들간에는 부모 관계, 형제 관계, 조상과 자손 관계가 존재한다. 아래 그림에서 A는 B의 부모 노드(parent node)가 되고, 반대로 B는 A의 자식 노드(children node)가 된다. B와 C와 D는 형제 관계(sibling)이다.

조상 노드(ancestor node)는 루트 노드에서 임의의 노드까지 경로를 이루는 노드를 말하며, 자손 노드(descendent node)는 임의의 노드의 서브트리에 속하는 모든 노드를 말한다.

자식 노드가 없는 노드를 단말 노드(terminal node 또는 leaf node)라고 하며, 그 반대는 비단말 노드(nonterminal node)이다.

노드의 차수(degree)는 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다. 아래 그림에서 루트 노드의 경우 자식 노드가 3개이기 때문에 차수도 3이다. 단말 노드는 차수가 0인 노드가 된다.

트리의 차수는 트리가 가지고 있는 노드의 차수 중에서 가장 큰 차수이다. 아래 그림에서 A와 B 노드의 차수가 3으로 가장 크므로 전체 트리의 차수는 3이 된다.

트리에서의 레벨(level)은 트리의 각층에 번호를 매기는 것으로서 정의에 의하여 루트의 레벨은 1이 되고 한 층씩 내려갈 수록 1씩 증가한다. 아래 그림에서 A의 레벨은 1이고 B의 레벨은 2이다. 트리의 높이(height)는 트리가 가진 최대 레벨을 말한다. 아래 트리의 높이는 3이다.

나무가 모이면 숲이 되듯이 트리들의 집합을 포레스트(forest)라고 한다.

트리의 표현

컴퓨터에서 트리를 표현하는 가장 일반적인 방법은 아래 그림 (a)와 같이 노드 구조를 이용하여 표현하는 것이다. 각 노드는 데이터를 저장하는 데이터 필드와 자식 노드를 가리키는 링크 필드를 갖는다. 이때 링크 필드의 개수는 자식 노드의 개수 즉 노드의 차수가 되어야 한다.

문제는 일반적인 트리에서 각 노드들은 임의의 개수의 자식을 가질 수 있다는 것이다. 자식 노드의 개수가 일정하지 않으면 노드의 구조가 복잡해진다. 이것은 프로그램을 상당히 복잡하게 만드므로 실제로는 위 그림의 (b)와 같이 두 개의 자식 노드를 사용하는 이진트리(binary tree)가 많이 사용된다.

이진트리 소개

이진트리란?

이진트리는 모든 노드가 2개 이하의 서브트리를 갖는 트리를 말한다. 이진트리에는 서브트리 간의 순서가 존재하는데, 왼쪽 서브트리와 오른쪽 서브트리는 반드시 서로 구별되어야 한다.

이진트리는 서브트리가 모두 이진트리이기 때문에 순환적인 구조를 갖는다.

이진트리의 성질

이진트리는 다음과 같은 성질을 갖는다.

  • n개의 노드를 가진 트리는 n-1개의 간선을 가진다. 그 이유는 루트를 제외한 트리의 모든 노드가 하나의 부모 노드를 갖기 때문이다.

  • 높이가 h인 이진트리는 h개 이상, 2h-1개 이하의 노드를 가진다.
    • 한 레벨에는 적어도 하나의 노드는 존재해야 하므로 높이가 h인 이진트리는 최소한 h개의 노드를 가져야 한다.
    • 또한 하나의 노드는 최대 2개의 자식을 가질 수 있으므로 레벨 i에서 노드의 최대 개수는 2i-1이 된다. 따라서 높이가 h인 이진트리의 최대 노드 개수는 2h-1개가 된다.

  • n개의 노드를 가지는 이진트리의 높이는 [log2(n+1)] 이상이고 n 이하이다.
    • 먼저 한 레벨에서 최소한 하나의 노드는 있어야 하므로 높이가 n을 넘을 수는 없다. 앞의 성질에서 높이 h의 이진트리가 가질 수 있는 노드의 최댓값은 2h-1이다.
    • 따라서 n ≤2h-1의 부등식이 성립하고 양변에 log를 취하면 h ≥ log2(n+1)이 된다. h는 정수이므로 h ≥ [log2(n+1)]이 된다.

이진트리는 형태에 따라 포화 이진트리(full binary tree), 완전 이진트리(complete binary tree), 기타 이진트리로 분류할 수 있다.

  • 포화 이진트리는 용어 그대로 트리의 각 레벨에 노드가 꽉 차있는 이진트리를 말한다. 즉 높이 k인 포화 이진트리는 정확하게 2k-1개의 노드를 가진다.
  • 포화 이진트리에서 각 노드에 번호를 붙일 때는 레벨 단위로 왼쪽에서 오른쪽으로 붙인다. 즉 루트 노드의 오른쪽 자식 노드는 항상 3이 된다.

  • 완전 이진트리는 높이가 k인 트리에서 레벨 1부터 k-1까지는 노드가 모두 채워져있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리를 말한다. 마지막 레벨에서는 노드가 꽉차있지 않아도 되지만 중간에 빈곳이 있으면 안된다. 고로 포화 이진트리는 완전 이진트리지만 그 역은 항상 성립하지 않는다.

이진트리의 추상 자료형

  • 객체
    • 노드와 간선의 집합. 노드는 공집합이거나 공집합이 아닌 경우 루트노드와 왼쪽 서브트리, 오른쪽 서브트리로 구성됨. 이때 모든 서브트리는 이진트리여야 한다.
  • 연산
    • create(): 이진트리를 생성한다.
    • isEmpty(): 이진트리가 공백상태인지 확인한다.
    • getRoot(): 이진트리의 루트 노드를 반환한다.
    • getCount(): 이진트리의 노드의 수를 반환한다.
    • getHeight(): 이진트리의 높이를 반환한다.
    • insertNode(n): 이진트리에 노드 n을 삽입한다.
    • deleteNode(n): 이진트리에서 노드 n을 삭제한다.
    • display(): 이진트리의 내용을 화면에 출력한다.

이진트리의 표현

이진트리를 프로그램에서 표현할 떄는 배열을 이용한 방법과 포인터를 이용한 방법으로 할 수 있다.

배열 표현법

배열 표현법은 저장하고자 하는 이진트리가 완전 이진트리라고 가정하고 이진트리의 높이가 k이면 먼저 2k-1개의 공간을 연속적으로 할당한다. 그리고 완전 이진트리의 번호대로 노드의 정보를 배열에 저장한다. 이 방법은 주로 포화 이진트리나 완전 이진트리에서 많이 사용되지만, 일반 이진트리도 저장할 수 있다. 이 경우 배열 중간에 빈 공간이 생긴다.

배열 표현법에서 인덱스만 알면 어떤 노드의 부모나 자식을 쉽게 알 수 있다. 부모와 자식의 인덱스 사이에는 다음과 같은 공식이 성립된다.

  • 노드 i의 부모 노드 인덱스 = i / 2
  • 노드 i의 왼쪽 자식 노드 인덱스 = 2i
  • 노드 i의 오른쪽 자식 노드 인덱스 = 2i+1

링크 표현법

링크 표현법은 연결 리스트를 이용한 방식과 유사하다. 트리의 노드들은 메모리 공간 상에 흩어져 있고, 하나의 노드는 데이터 필드와 링크 필드를 갖는다. 그리고 이중 연결 리스트와 같이 두 개의 포인터 변수를 갖는데, 이들은 각각 왼쪽 자식 노드와 오른쪽 자식 노드를 가리킨다.

이진트리의 순회

선형적인 자료구조에서와 달리 트리에서는 동일한 트리에서도 여러 순회 방법이 존재한다.

이진트리 순회 방법

이진트리를 순회하는 표준적인 방법으로는 전위, 중위, 후위의 3가지 방법이 있다. 이는 루트와 왼쪽 서브트리, 오른쪽 서브트리를 각각 어떤 순서로 방문하느냐에 따라 구분된다.

만약 루트를 방문하는 작업을 V라고 하고 왼쪽 서브트리 방문을 L, 오른쪽 서브트리 방문을 R이라고 하면 다음과 같이 3가지 방법을 생각할 수 있다.

  • 전위 순회(preorder traversal): VLR
  • 중위 순회(inorder traversal): LVR
  • 후위 순회(postorder traversal): LRV

이진트리에서는 각각의 서브트리도 이진트리이므로 서브트리에서도 동일한 순회 방법을 적용한다. 즉 전위 순회라면 서브트리에 들어 있는 노드들도 VLR 순서대로 순회된다.

전위 순회

전위 순회의 알고리즘은 다음과 같다.

preorder(x)

if x != NULL
    print DATA(x);
    preorder(LEFT(x));
    preorder(RIGHT(x));

중위 순회

중위 순회의 알고리즘은 다음과 같다.

inorder(x)

if x != NULL
    inorder(LEFT(x));
    print DATA(x);
    inorder(RIGHT(x));

후위 순회

후위 순회의 알고리즘은 다음과 같다.

postorder(x)

if x != NULL
    postorder(LEFT(x));
    postorder(RIGHT(x));
    print DATA(x);

순회 방법의 선택

  • 순서는 중요치 않고 노드를 전부 방문하기만 하면 된다면 3가지 방법 중 어느 것을 쓰든 상관없다.
  • 자식 노드를 처리한 다음 부모 노드를 처리해야 하는 문제라면 후위 순회를 사용해야 한다.
  • 부모 노드를 처리한 다음 자식 노드를 처리해야 한다면 전위 순회를 사용해야 한다.

레벨 순회

레벨 순회는 각 노드를 레벨 순으로 검사하는 순회 방법으로 표준적인 순회 방법은 아니지만 많이 사용된다.

루트 노드의 레벨이 1이고 아래로 내려갈수록 레벨을 증가한다. 동일한 레벨의 경우에는 좌에서 우로 방문한다.

앞선 3가지 표준 순회 방법은 순환을 사용하므로 내부적으로 스택이 사용되었다고 볼 수 있다. 반면 레벨 순회는 큐를 사용한다.

레벨 순회는 큐에서 노드를 하나 꺼내 방문하고 그 자식들을 큐에 삽입한다. 이때 자식이 없으면 삽입하지 않고 왼쪽 자식을 먼저 오른쪽 자식을 다음에 처리한다. 이 과정은 큐가 공백 상태가 될 때까지 반복한다.

level_order()

initialize queue;
queue.enqueue(root);
while queue.isEmpty() != NULL
    x <- queue.dequeue();
    if(x != NULL)
        print DATA(x);
        queue.enqueue(LEFT(x));
        queue.enqueue(RIGHT(x));

이진트리 연산

트리의 노드 개수 구하기

트리 전체 노드의 개수를 계산할 수 있다. 기본적으로 노드의 개수를 세기 위해서는 트리 안의 노드들을 전체적으로 순회해야 한다. 트리의 노드의 개수는 왼쪽 서브트리의 노드 개수와 오른쪽 서브트리의 노드 개수에 루트 노드를 더하면 된다. 서브트리의 노드 개수는 순환 호출로 계산한다.

단말 노드 개수 구하기

단말 노드의 개수를 구하기 위해서는 트리 안의 노드들을 전체적으로 순회해야 한다. 순회하면서 만약 왼쪽 자식과 오른쪽 자식이 동시에 0이 되면 단말 노드이므로 1을 반환한다. 만약 그렇지 않으면 비단말 노드이므로 각각의 서브트리에 대하여 순환 호출한 다음 반환되는 값을 서로 더하면 된다.

높이 구하기

먼저 각 서브트리에 대하여 순환 호출을 해야 한다. 순환 호출이 끝나면 각각 서브트리로부터 서브트리의 높이가 반환되어 왔을 것이다. 그러면 어떻게 현재 트리의 높이를 구해야 하는가? 트리의 높이는 왼쪽 서브트리와 오른쪽 서브트리 중에서 더 높은 트리를 먼저 찾는다. 현재 트리의 높이는 더 높은 서브트리의 높이보다 1 더 높다.

이진트리 응용

수식 트리

이진트리 순회는 수식 트리(expression tree)를 처리하는데 사용될 수 있다. 수식 트리는 산술식이나 논리식의 연산자와 피연산자들로부터 만들어진다. 피연산자들은 단말 노드가 되며 연산자들은 비단말 노드가 된다. 각 이진 연산자에 대하여 왼쪽 서브트리는 왼쪽 피연산자가 되며 오른쪽 서브트리는 오른쪽 피연산자가 된다.

이들 수식 트리를 전위, 중위, 후위의 순회 방법으로 읽으면 각각 전위 표기 수식, 중위 표기 수식, 후위 표기 수식이 된다.

수식 a + b a – (b x c) (a < b) or (c < d)
전위 순회 + a b – a x b c or < a b < c d
중위 순회 a + b a – b x c a < b or c < d
후위 순회 a b + a b c x – a b < c d < or

스레드 이진트리

이진트리의 노드에는 많은 NULL 링크들이 존재한다. 만약 노드의 개수가 n이면 각 노드당 2개의 링크가 있으므로 전체 링크의 수는 2n이다. 이들 중 루트를 제외한 n-1개의 노드가 부모와 연결되어 있으므로 2n 중 n-1을 제외한 나머지 n+1개의 링크가 항상 NULL이다. 따라서 이들을 잘 활용하면 순환 호출 없이도 트리의 노드들을 순회할 수 있다. 이런 트리를 스레드 이진트리(threaded binary tree)라 한다.

트리의 노드들을 중위 순회로 방문할 때 어떤 노드 바로 앞에 방문되는 노드를 중위 선행자(inorder predecessor)라 하고 바로 다음에 방문하는 노드를 중위 후속자(inorder succeessor)라 한다. 스레드 이진 트리에서는 NULL 링크를 재사용한다. 링크 값이 NULL을 갖는 대신에 중위 선행자나 중위 후속자를 저장시켜 놓는 것이 스레드 이진트리의 핵심 아이디어이다.

이것은 스레드, 즉 실을 이용하여 노드들을 순회 순서대로 연결시켜 놓는다는 의미이다. 아래 그림에서 점선으로 표시한 링크들이 중위 후속자를 나타낸다. A, B, D 노드의 오른쪽 링크가 NULL이 아니라 중위 순회에서 다음으로 방문되는 노드를 가리킨다. 중위 선행자도 동일한 방법으로 선언할 수 있다. 이 경우 B, D, E 노드의 왼쪽 자식 링크가 C, G, F를 각각 가리키게 될 것이다.

한 가지 문제가 남아 있다. 만약 이런 식으로 NULL 링크에 스레드가 저장되면 링크에 자식을 가리키는 포인터가 저장되어 있는지 아니면  NULL이 저장되어야 하는데 대신 스레드가 저장되어 있는지를 구별해주는 bool 변수가 필요하다.

[ssba]

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기