트리

트리의 특성을 활용하는 분야

• 인공지능: 인공지능의 판단 기준을 만들 때 의사 결정 트리를 사용합니다.

• 자동 완성 기능: 트리는 문자열 처리에도 많이 활용됩니다. 예를 들어 검색 엔진에서 자동 검색어 추천 기능도 트라이라는 독특한 트리 구조를 활용한 것입니다.

• 데이터베이스: 데이터를 쉽게 검색, 삽입, 삭제를 할 수 있도록 트리를 활용해서 데이터를 구조화하고 인덱싱합니다.

나무를 거꾸로 뒤집어 놓은 모양의 트리

트리는 나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤집어 놓은 모양입니다. 따라서 나무의 뿌리(root)는 맨 위에 있습니다.

트리를 구성하는 요소들

트리를 구성하는 노드

노드는 트리를 구성하는 요소입니다. 노드 중 가장 위에 있는 노드를 루트 노드라고 합니다. 앞에 그림에서는 A가 루트 노드입니다.

배열로 표현하기

배열로 트리를 표현하려면 다음 3가지 규칙이 필요합니다.

1. 루트 노드는 배열 인덱스 1번에 저장합니다.

2. 왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 X 2 입니다.

3. 오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 X 2 + 1 입니다.

트리로 배열을 만들게 될 경우 아주 쉽게 구현할 수 있습니다. 하지만 메모리 낭비가 심할 수 있습니다. 메모리만 넉넉하다면 구현 시간을 단축하는 용도로 사용해도 좋습니다.

이진 트리 순회하기

이진 트리를 순회하는 방법은 총 3가지로 전위 순회, 중위 순회, 후위 순회가 있습니다.

• 전위 순회: 현재 노드를 부모 노드로 생각했을 때 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 방문합니다.

• 중위 순회: 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순서로 방문합니다.

• 후위 순회: 현재 노드를 부모 노드로 생각했을 때 오른쪽 자식 노드 -> 부모 노드 -> 왼쪽 자식 노드 순서로 방문합니다.

이진 탐색 트리 구축하기

이진 탐색 트리의 대상 데이터가 3 -> 4 -> 2 -> 1 -> 9 -> 5 순서로 들어온다고 생각하고 이진 탐색 트리를 구축한다고 할 때, 이진 탐색 트리는 데이터의 크기를 따져 현재 노드보다 값이 작으면 왼쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치하는 독특한 정렬 방식을 갖고 있습니다.

이진 탐색 트리 탐색하기

구축하기에서 정렬을 하여 집어넣었기 때문에 찾을 때는 쉽게 찾을 수 있습니다.

1. 찾으려는 값이 현재 노드의 값과 같으면 탐색을 종료하고 찾고자 하는 값이 더 크다면 오른쪽 노드를 탐색합니다.

2. 본인이 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 노드를 탐색합니다.

3. 값을 찾으면 종료합니다. 노드가 없을 때까지 탐색을 했다면 현재 트리에 값이 없는 것입니다.

이진 탐색 트리와 배열 탐색의 효율 비교

위에서 본 것처럼 이진 탐색 트리에서 탐색하는 것이 배열로 탐색하는 것보다 효율이 좋을 것 같다고 할 수 있습니다. 하지만 두 자료구조의 삽입과 탐색 시간 복잡도는 이진 탐색 트리의 균형이 맞지 않으면, 최악의 경우 으로 같다고 얘기합니다.

치우쳐진 형태의 트리

위에 보이는 트리처럼 만약 91이라는 값을 찾는다면 해당 트리의 시간 복잡도는 이 되고 맙니다. 하지만 이런 경우는 매우 극단적인 상황입니다.