개념 - 트리, 이진 트리

출처 : c++로 쉽게 풀어쓴 자료구조

비선형구조의 첫 주자로, 알아야 할 내용이 조금 많다.

트리는 조직도 같은 계층구조(hierarchical structure)를 표현할 때 사용되는 구조다.

의사결정트리, 디렉토리 구조 등에서 사용된다.

다음 용어들의 뜻을 생각해보자.

노드

루트

서브트리

간선, 에지(edge)

부모 노드, 자식 노드, 형제 노드, 조상 노드, 자손 노드

단말 노드, 리프 노드

비단말 노드

차수

레벨

높이

이진 트리 binary tree

데이터와 링크를 가진 노드로 트리를 구성할 때, 각 노드의 링크 수가 다양할 경우 노드마다 연결리스트를 구성해야해서 프로그램이 복잡해 질 수 있다. 따라서 실제로는 이진 트리를 많이 사용한다.

이진트리는 정의에 의해 그 서브트리도 이진트리거나 공집합이다.

이진 트리의 성질

n 개의 노드를 가진 트리는 몇 개의 간선을 가질까?

-> n - 1개

h 의 높이를 가진 트리는 최소, 최대 몇 개의 노드를 가질까?

-> 최소 h개, 최대 2^h - 1

n 개의 노드를 가진 트리의 최소 높이, 최대 높이는 어떻게 될까?

-> 최소 log2 (n + 1), 최대 n

포화 이진트리(full binary tree)

-> 높이에 따른 최대의 노드 2^n -1개의 노드가 있는 상태의 트리

완전 이진트리(complete binary tree)

-> 높이가 k 일때 레벨 k-1까지가 포화 이진트리이고, 레벨 k도 중간에 빈 곳 없이 (수는 적어도 됨) 구성된 트리. 

포화 이진트리는 반드시 완전 이진트리지만, 역은 아닐 수도 있다.

이진트리의 추상자료형 ADT

객체 : 노드와 간선의 집합. 노드는 공집합이거나 공집합이 아닌 경우 루트노드와 왼쪽 서브트리, 오른쪽 서브트리로 구성됨. 이때 모든 서브트리도 이진트리여야함.

연산 : 

create() 이진트리 생성

isEmpty() 비어있는지 확인

getRoot() 루트 노드 반환

getCount() 노드 수 반환

getHeight() 높이 반환

insertNode(n) 노드 삽입

deleteNode(n) 노드 삭제

display() 출력

이진트리의 표현

배열 표현법 : 높이가 k일 때 2^k - 1 공간을 할당하고, 레벨별로 순서대로 배열에 저장하는 방법.

인덱스를 1부터 사용한다. 레벨에 빈 노드가 많을 수록 공간 낭비가 심하다.

부모와 자식의 관계를 인덱스로 알 수 있다.

인덱스 i의 부모 인덱스 : i/2

인덱스 i의 왼쪽 자식 인덱스 2i

인덱스 i의 오른쪽 자식 인덱스 2i+1

링크 표현법:

데이터 필드와 링크 필드로 구성된 노드를 더블연결리스트 처럼 연결해서 표현하는 방법

이진트리의 순회 traversal

순회란 모든 노드를 한 번씩 방문하는 것이다. 트리를 사용할 때의 가장 기본적인 연산이다. 

이진트리의 모든 서브트리 역시 루트와 같은 구조를 지니므로 재귀적으로 순회를 이어나갈 수 있다.

이 때 순회의 순서에 따라 전위, 중위, 후위 순회로 나뉘게 되는 것이다.

루트의 방문을 V, 왼쪽 서브트리 방문을 L, 오른쪽 서브트리 방문을 R이라고 할 때

전위 preorder traversal : VLR

중위 inorder traversal : LVR

후위 postorder traversal : LRV

이 때 순서는 항상 좌에서 우로 가되, 루트(V)를 언제 방문하느냐갸 곧 그 이름의 뜻이자 순서의 핵심이라는 것을 알 수 있다.

그렇다면 어떤 방식을 사용해야 할까?

모든 노드를 순서 상관 없이 방문하는 게 목적이라면 아무거나 써도 상관없다.

자식 노드를 모두 처리한 다음에만 루트노드를 처리할 때는 후위 순회를 사용한다.

부모 노드를 먼저 처리한 다음에 자식노드를 처리할 때는 전위 순회를 사용한다.

이진 탐색트리를 순서대로 순회할 때 중위 순회를 사용한다.

레벨 순회

레벨 순회란 한 레벨씩 내려가며 레벨에 있는 모든 노드를 방문하는 순회법이다.

큐를 사용하여 구현한다.

이진트리의 연산

노드 개수 구하기 : 1+ n(left()) + n(right())

단말노드 개수 구하기 : nLeaf(left()) + nLeaf(right())

높이 구하기 : bigger(hLeft(), hRight()) + 1

이진 트리 응용

수식 트리(expression tree)의 처리 : 후위 순회

디렉토리 용량 계산 : 후위 순회

스레드 이진트리

n 개의 노드가 있을 때 링크의 수는 2n개인데, 이 중 루트를 뺀 n-1개의 링크는 연결되어있고,

n + 1개의 링크는 사용하지 않는 상태임을 이용해서 빈 우측링크에 자신의 다음 번 행선지(중위 후속자)를 입력하는 순회법.

재귀나 다른 자료구조(스택, 큐)를 사용하지 않고 순회할 수 있다. 자신의 우측링크가 중위 후속자인지 자식노드인지 구분할 불값이 필요하다.

구현 : 

http://kid5.tistory.com/273