C 트리(Tree) 설명

트리

- 비선형 자료구조의 일종이다.

- 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다.

  ※ 사용 예로 컴퓨터의 디렉터리 구조를 들 수 있다.

 

용어 정리

1. 노드(Node) : 트리의 구성요소에 해당하는 요소.

2. 간선(Edge) : 노드와 노드를 연결하는 연결선.

3. 루트 노드(Root node) : 트리 구조에서 최상위에 존재하는 노드.

4. 단말 노드(Leaf node) : 아래로 또 다른 노드가 연결되어 있지 않은 노드.

5. 내부 노드(Internal node) : 단말 노드를 제외한 모든 노드.

6. 형제 노드(Sibling node) : 같은 부모를 가지는 노드.

 

 

이진 트리(Binary tree)

- 노드의 자식 수가 2 이하인 트리

 

 

포화 이진 트리(Full binary tree)

- 단말 노드를 제외한 모든 노드가 2개의 자식을 가진 트리

 

 

이진 탐색 트리(Binary search tree)

- 이진 탐색 트리는 이진 탐색과 이진 트리를 결합한 자료구조이다.

- 이진 탐색 트리는 다음과 같은 속성을 갖기 때문에 효율적인 탐색이 가능하다.

  1. 중복된 값을 혀용하지 않는다. (하지만 일부에서는 중복된 값을 혀용하는 경우도 있다.)

  2. 왼쪽 서브트리의 키들은 부모 노드의 키보다 작다.

  3. 오른쪽 서브트리의 키들은 부모 노드의 키보다 크다.

  4. 양쪽 서브트리는 그 자체로 이진 탐색 트리이다.

- 위와 같은 특징 때문에 탐색 연산은 O(log₂n)의 시간복잡도를 가진다.

 

트리 순회(Tree traversal)

- 트리의 순회는 전위 순회, 중위 순회, 후위 순회 세 가지가 있다.

  ※ 순회에서 중요한 부분은 자식 노드를 좌, 우 순서로 출력된다고 생각하면 된다.

- 전위 순회(PreOrder) : Root 노드부터 시작된다.

- 중위 순회(InOrder) : Root 노드가 중간에 위치한다.

- 후위 순회(PostOrder) : Root 노드가 마지막에 위치한다.

 

전위 순회

- Root 노드가 제일 먼저 순회가 시작되고 자식 노드의 좌, 우 순서로 순회가 이루어진다

- 즉, 탐색 순서는 A → B → D → E → C → F → G가 된다.

 

중위 순회

- 왼쪽 자식노드, Root 노드, 오른쪽 자식노드 순으로 순회가 이루어진다.

- 즉, 순회 순서는 D → B → E → A → F → C → G가 된다.

 

후위 순회

- 왼쪽 자식노드, 오른쪽 자식노드, Root 노드 순으로 순회가 이루어진다.

- 즉, 순회 순서는 D → E → B → F → G → C → A가 된다.

 

  ※ 어렵게 생각할 필요없이 자식 노드는 무조건 오른쪽 왼쪽 순으로 순회가 되고, 전위냐 중위냐 후위냐에 따라 Root 노드가 자식 노드들의 앞, 중간, 뒤에 위치한다고 생각하면 편하다.