편집토론문서 역사

Binary tree

Binary Tree.png

개요

부모 노드 밑에 자식 노드가 최대 2개밖에 오지 않는, 트리의 가장 간단한 형태다. 두 자식 노드를 보통 왼쪽 자식과 오른쪽 자식으로 구분지으며, 하나의 값과 왼쪽, 오른쪽 자식 노드를 각각 가리킬 두 개의 포인터를 가진 구조로 구현할 수 있다.

일반적으로 n개의 자식을 가질 수 있는 트리 구조에서, 1개를 초과한 자식 하나마다 노드를 하나 추가해 추가된 새 노드의 왼쪽에 원래의 자식 노드, 오른쪽에 형제 노드를 배치 하는 이진 트리 구조로 변환할 수 있으며(Left-Child, Right-Sibling), 이 방법으로 모든 트리를 이진 트리 형태로 재구성할 수 있다(좌우를 바꾸어도 동일). 때문에 특별한 이유가 없는 이상 트리는 보통 이진 트리로 구현된다.

이진트리에는 다음과 같은 종류가 있다.

  1. 정 이진 트리(full binary tree): 모든 트리의 자식은 0개나 2개다.
  2. 포화 이진 트리(perfect binary tree): 모든 리프 노드의 높이가 같다.
  3. 완전 이진 트리(complete binary tree): 모든 리프노드의 높이가 최대 1 차이가 나고, 모든 노드의 오른쪽 자식이 있으면 왼쪽 자식이 있는 이진트리이다. 다시 말해 트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간 형태이다.


일반적으로 비선형 구조인 이진트리는 각각의 노드가 자식들의 포인터를 갖도록 구현되지만, 완전 이진 트리의 경우 왼쪽부터 빠짐없이 채워져있다는 성질을 이용해 배열을 사용하여 구현 하기도 한다. 1번부터 시작하는 배열을 생각하면 n번째 원소의 왼쪽 자식은 2n, 오른쪽 자식은 2n+1번째 원소로 구성하면 된다. 또 n번째 원소의 부모 노드는 [n/2]번째 원소가 된다.

이진 트리의 순회

이진 트리의 순회 과정은 한번 지난 노드를 출력하는 과정(위치)에 따라 세가지 순회와 너비 우선 순회로 나눌 수 있다.

전위 순회(Preoreder Traversal)

전위 순회는 왼쪽 우선으로 가는 경로를 출력하게 된다.

  1. 노드 출력
  2. 원쪽 부분 트리를 순회하는 재귀 호출
  3. 오른쪽 부분 트리를 순회하는 재귀 호출

예)8-3-1-6-4-7-10-14-13

중위 순회(Inorder Traversal)

이진 탐색 트리에서 중위 순회를 사용하면 왼쪽에 있는것 부터 정렬되어 나오기 때문에, 오름차순으로 정렬된 데이터를 얻을 수 있다.

  1. 원쪽 부분 트리를 순회하는 재귀 호출
  2. 노드 출력
  3. 오른쪽 부분 트리를 순회하는 재귀 호출

예)1-3-4-6-7-8-10-13-14

후위 순회(Postorder Traversal)

  1. 왼쪽 부분 트리를 순회하는 재귀 호출
  2. 오른쪽 부분 트리를 순회하는 재귀 호출
  3. 노드 출력

예)1-4-7-6-3-13-14-10-8

너비 우선 순회

레벨 우선 순위는 큐나 스택을 이용해서 구현할 수 있다. 스택을 이용한 구현은 스택을 2개 사용하여, 한 스택은 현재 깊이의 해당하는 노드들을 저장하고 다른 스택에는 다음 깊이에 해당하는 자식노드들을 저장하여 구현한다. 큐는 자식노드들을 큐에 집어넣으면서 구현하게 된다. 물론 큐로 구현하는 것이 현명하고 깔끔하다. 8-3-10-1-6-14-4-7-13

이진 트리 종류

이진 탐색 트리

Binary Search Tree.png

Binary Search Tree (BST) 라 불리는 이진 탐색 트리는, 노드의 왼쪽 가지에는 노드의 값보다 작은 값들만 있고 오른쪽 가지에는 큰 값들만 있도록 구성한 트리이다. 어떤 값 n 을 삽입 탐색 삭제 할때, n의 위치를 확인 하는 작업을 이진 탐색을 이용하여 탐색할 수 있기 때문에, 이상적인 상황에서 탐색 삽입 삭제 모두 시간 복잡도가 logN 이다. 다만, 산입되거나 삭제되는 순서가 순서가 있게 삽입되면 N의 시간이 걸리게 된다.

힙 트리

Heap Tree.png

모든 부모 노드가 반드시 자식 노드 두 개를 갖는 완전 이진 트리에서, 어떤 부모 노드를 선택해도 '부모 노드 < 자식 노드' 혹은 그 역인 조건을 만족하는 트리를 힙이라 한다. 한편 왼쪽 자식 노드와 오른쪽 자식 노드 간의 대소관계는 상관없다.

데이터의 추가

  1. 후위추가: 버블 소트처럼 맨 아랫단에 노드를 넣고, 부모 노드와 값을 비교한뒤, 교환하는 작업을 부모 노드와 값이 같거나 조건에 만족할 때 까지 반복 한다. 이때 버블소트와는 달리 전체 길이가 logN 임으로 추가의 작업은 logN 만에 할 수 있다.

힙 생성

모든 데이터가 이진트리에 있을 때 (배열에서 이진트리를 만드는 것은 매우 쉬움으로) 힙으로 재구축 하는 방법이 있다.

  1. 자식 노드를 가진 마지막 부모 노드에서 시작하여 루트 노드까지 다음을 반복하면 된다.
  2. 부모 노드가 자식노드보다 크면 (최소 힙) 두 자식 노드 중에서 더 작은 노드와 부모 노드를 교환한다. 교환한 자식 노드를 새로운 부모 노드로 간주해서 \부모 노드 > 자식 노드 관계를 만족하는 동안에 하향 이동하는 루프에 대해 같은 처리과정을 반복한다.
  3. 2를 반복하다 루트노드에 도달하면, 반복을 종료한다.