나무 모양의 자료구조인 트리는 응용 분야가 굉장히 다양하다. 어떤 트리는 조직도 같은 계층적인 데이터를 표현하는 데 사용되고, 어떤 트리는 수식을 표현할 때 사용됩니다. 또 어떤 트리는 집합을 나타내는 데 사용되며, 심지어는 데이터의 탐색을 위한 트리도 있다.
트리의 가장 중요한 응용 분야 중 하나는 탐색이다. 이것은 6장 탐색에서 더 알아보자.
트리는 나무를 닮은 자료구조이다. 컴퓨터 과학에서도 트리는 굉장히 활용도가 높은 자료구조이다. 운영체제의 파일 시스템이 트리 구조로 이루어져 있고, HTML이나 XML 문서를 다룰 때 사용하는 DOM(Document Object Model)도 트리 구조로 이루어져 있다. 검색 엔진이나 데이터 베이스도 트리 자료구조에 기반해서 구현된다.
트리
트리는 뿌리(Root), 가지(Branch), 잎(Leaf) 세 가지 요소로 이루어져 있다.
뿌리, 가지, 잎 모두 실제로는 똑같은 노드이다. 이들은 트리 내의 위치에 따라 명칭만 달라질 뿐이다. 뿌리인 루트는 트리 자료구조의 가장 위에 있는 노드를 가리키고, 가지는 루트와 잎 사이에 있는 모든 노드를 일컫는 말이다. 그리고 가지의 끝에 매달려 있는 노드를 잎이라고 한다. 잎 노드는 끝에 있다고 해서 단말(Terminal) 노드라고 부르기도 하는데, 여기서는 잎이라고 한다.
트리의 구성 요소와 관계
노드 B, C, D를 보자 B에서 C와 D가 뻗어 나와있다. B는 C와 D의 부모(Parent)이고, C와 D는 B의 자식(Children)이다. 그리고 한 부모 밑에서 태어난 C와 D는 형제(Sibling)이다.
B와 K 관계는 아무 관계도 아니다.
경로(Path)에 대해서 알아보자
트리에서 경로는 한 노드에서부터 다른 한 노드까지 이르는 길 사이에 놓여있는 노드들의 순서이다.
EX) B노드에서 F 노드를 찾아간다고 해보자. B노드에서 출발하여 D노드를 방문하고, D에서 출발하여 F에 도착한다. 이때 "B, D, F"를 B에서 F까지의 경로라고 한다. 경로는 길이(Length)라는 속성을 가진다. 쉽게 말하면 그저 출발 노드에서 목적지 노드까지 거쳐야 하는 노드의 개수를 말하는 것 뿐이다. 앞에서 이야기한 B, D, F 경로의 길이는 2가 되는 식이다.
노드의 깊이(Depth)를 알아보자
노드의 깊이는, 루트 노드에서 해당 노드까지의 경로의 길이를 뜻한다.
EX) G 노드는 루트 노드인 A로부터의 경로의 길이가 1이므로 깊이가 1이고, K 노드는 A 노드로부터 경로의 길이가 3이므로 깊이 역시 3이 되는 것이다. 여기서 중요한 것은 루트의 깊이는 0이다.
쉽게 말하면 깊이가 있다는 것을 말하고 있는 것.
깊이와 비슷한 개념의 용어로 레벨(Level)과 높이(Height)가 있다. 이게 같은 건 아니고 비슷한 거다.
레벨
:레벨은 깊이가 같은 노드의 집합을 일컫는 말이다. 위 그림에서 '레벨 2'라고 하면 C, D, H, J 노드 전체를 가리킨다.
높이
: '가장 깊은 곳'에 있는 잎 노드까지의 깊이를 뜻한다. 위 그림에서 가장 깊은 곳에 있는 잎 노드들이 E, F, K인데 이들의 깊이는 3이니, 트리의 높이는 3이 된다.
차수(Degree)에 대해서 알아보자.
차수에는 노드의 차수와 트리의 차수가 있다.
노드의 차수는 그 노드의 자식 노드 개수를 말하는 것이다.
트리의 차수는 트리 내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수를 말한다.
위 그림에서는 a의 자식이 가장이 가장 많으니 차수는 3이다.
트리 표현하기
트리는 여러 가지 방법으로 표현이 가능한 자료구조이다.
트리 구조의 데이터를 소프트웨어의 GUI로 표현할 때 자주 채택되므로 잘 익혀두기 바랍니다.
1.중첩된 괄호 표현법
이 표현법은 같은 레벨의 노드들을 괄호로 같이 묶어 표현하는 방법
이 방법은 읽기는 다소 어렵지만 트리를 하나의 공식처럼 표현할 수 있다는 장점이 있다.
2.중첩된 집합 표현
3.들여쓰기 표현
들여쓰기로 표현된 트리는 계층적인 특징을 잘 나타낸다. 윈도우 탐색이ㅢ 폴더 트리가 들여쓰기로 표현한 트리의 좋은 예이다.
노드 표현하기
트리를 이루는 '노드를' 표현하는 방법에 대해서 알아보자. 노드의 표현법이라고 하면 부모와 자식, 그리고 형제 노드를 서로 연결짓는 방법을 말한다.
1.N-링크(N-Link) 표현법
N-링크는 노드의 차수가 N이라면, 노드가 N개의 링크를 가지고 있어서 이 링크들이 각각 자식 노드를 가리키도록 노드를 구성하는 방법
단점:차수(자식 노드의 수)가 노드마다 달라지는 트리에는 적용하기 어려운 단점이 있다.
2.왼쪽 자식-오른쪽 형제(Left Child-Right Sibling) 표현법
왼쪽 자식-오른쪽 형제 이름이 뜻하는 것처럼 왼쪽 자식과 오른쪽 형제에 대한 포인터를 갖고 있는 노드의 구조이다.
이 방법을 사용하면 N개의 차수를 가진 노드의 표현이 두 개의 포인터, 왼쪽 자식-오른쪽 형제만으로 가능하게 된다.
트리에서 어느 한 노드의 모든 자식 노드를 얻으려면 일단 왼쪽 자식 노드에 대한 포인터만 있으면 된다. 이 포인터를 이용해서 왼쪽 자식 노드의 주소를 얻은 후, 이 자식 노드의 오른쪽 형제 노드의 주소를 얻고, 또 그 다음 오른쪽 형제 노드의 주소를 계속해서 얻어 나가면 모든 자식 노드를 얻을 수 있다.
이진 트리
앞에서는 한 노드가 N개의 자식을 가질 수 있는 트리들이다.
:이진 트리는 모든 노드가 최대 2개의 자식을 가질 수 있는 트리이다. 이진(Binary)이라는 이름도 둘이라는 뜻으로 붙여진 것이다.
이진 트리의 여러 형태
이진 트리의 너드는 자식 노드가 아예 없거나 하나 또는 둘 뿐이라는 것이다.
포화 이진 트리(Full Binary Tree)
잎 노드를 제외한 모든 노드가 자식을 둘씩 가지고 있는 이진 트리를 '포화 이진 트리'라고 한다.
완전 이진 트리(Complete Binary Tree)
잎 노드들이 트리의 왼쪽부터 차곡차곡 채워지는 것이 특징이다. 위 그림 이진 트리들은 모두 완전 이진 트리이다.
그런데 포화 이진 트리, 완전 이진 트리를 왜 따로 분류해서 설명을 할까?
:이진 트리는 일반 트리처럼 나무 모양의 자료를 담기 위한 자료구조가 아니라 컴파일러나 검색 등에 사용되는 특수 자료구조이다. 특히 이진 트리를 이용한 검색에서는 높은 성능을 위해 트리의 노드들을 가능한 한 '완전한' 모습으로 배치하는 것이 필수이다. 그래서 완전한 모습의 트리가 어떤 것인지 알아야 한다.
높이 균형 트리(Height Balanced Tree)
높이 균형 트리는 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1이상 차이나지 않는 이진 트리를 말한다.
완전 높이 균형 트리(Completely Height Balanced Tree)
완전 높이 균형 트리는 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 이진 트리를 말한다.
이진 트리의 순회
순회(Traversal)란?
:트리 내의 노드들 사이를 돌아다니는 것을 말한다.
순회에는 몇 가지 규칙이 있다. 즉 효율적인 방법으로 원하는 데이터에 접근할 수 있는 방법을 제공한다.
1. 루트 노드부터 잎 노드까지 아래 방향으로 방문하는 전회 순회(Preorder Traversal)
2. 왼쪽 하위 트리부터 오른쪽 하위 트리 방향으로 방문하는 중위 순회(Inorder Traversal)
3. 루트, 왼쪽 하위 트리, 오른쪽 하위 트리 순으로 방문하는 후위 순회(Postorder Trversal)
전위 순회
전위 순회는 (1) 루트 노드부터 시작해서 아래로 내려오면서 (2) 왼쪽 하위 트리를 방문하고, 왼쪽 하위 트리의 방문이 끝나면 (3) 오른쪽 하위 트리를 방문하는 방식이다.
EX) A > B > C > D > E > F > G
전위 순회 이용하여 중첩된 괄호 표현
부모 > 자식 > 형제
중위 순회
(1) 왼쪽 하위 트리부터 시작해서 (2) 루트를 거쳐 (3) 오른쪽 하위 트리를 방문하는 방법이다.
왜 노드가 아닌 하위 트리부터 방문하는 건가요?
:트리는 하위 트리의 집합이라고 할 수 있다. 하위 트리 역시 또 다른 하위 트리의 집합이라고 할 수 있다. 이러한 정의는 하위 트리가 또 다른 하위 트리로 나뉘어질 수 없을 때까지, 즉 하위 트리가 잎 노드일 때까지 반복해서 계속된다.
따라서 왼쪽 하위 트리부터 시작한다는 말은 트리에서 가장 왼쪽의 '잎 노드'부터 시작한다는 뜻이고, 이 잎 노드에서부터 시작된 순회는 부모 노드를 방문한 후 자신의 형제 노드를 방문한다. 이렇게 해서 최소 단위의 하위 트리가 순회가 끝나면 그 윗 단계 하위 트리에 대해 순회를 계속한다.
이 중위 순회가 응용되는 대표적인 사례는 수식 트리(Expression Tree)이다.
자식 > 부모 > 형제
후위 순회
후위는 전위와 반대되는 규칙을 가지고 있다.
후외 순회의 방문 순서는 왼쪽 하위 트리 > 오른쪽 하위 트리 > 루트 노드 순이다. 그리고 이 순서는 하위 트리의 하위트리, 또 그 하위 트리의 하위 트리에 대해 똑같이 적용된다. 물론 하위 트리가 잎 노드라면 방문은 중지된다.
후위 순회를 가지고 계산을 하면 후위 표기식이 나온다.
같은 노드를 가지고 중위 순회를 실행해서 계산하면 중위 표기식이 나온다.
수식 트리(Expression Tree)
:수식을 표현하는 이진 트리이다. 그래서 수식 트리는 수식 이진 트리(Expression Binary Tree)라고 부르기도 한다.
두 가지 규칙을 가진다.
1. 피연산자는 잎 노드이다.
2. 연산자는 루트 노드, 또는 가지 노드이다.
1, 2, 7, 8은 모두 잎 노드이다. 반면에 연산자들은 모두 루트 노드이거나 가지 노드인 것을 알 수 있다.
'+' 연산자는 왼쪽 하위 트리가 표현하고 있는 수식 (1*2)와 오른쪽 하위 트리가 표현하고 있는 수식 (7-8)을 피연산자로 삼고 있다. 따라서 이 수식 트리는 루트 노드를 중심으로 왼쪽 하위 수식 트리의 결과 값과 오른쪽 하위 수식 트리의 결과 값을 피연산자로 하는 계산을 수행하면 전체 수식의 계산 결과를 얻을 수 있다.
이 수식 트리의 성질에 적합한 노드 순회 방법을 알고 있다 그것은 후위 순회이다. 후위 순회는 왼쪽 하위 트리 > 오른쪽 하위 트리 > 루트 노드의 순으로 순회를 하기 때문에 양쪽 하위 트리에서부터 결과 값을 병합해 올라와야 하는 수식 트리의 계산에 안성맞춤이다.
수식 트리의 구축
후위 표기식을 사용해 트리를 구축하자.
후위 표기식에 기반한 수식 트리 구축 알고리즘은 여러 가지가 있다. 하지만 우리는 다음과 같은 과정으로 동작하는 알고리즘을 사용한다.
1. 수식을 뒤에서부터 앞쪽으로 읽어나간다.
2. 수식에서 제일 마지막에 있는 토큰은 루트 노드가 된다. 후위 표기식에서 가장 마지막에 있는 토큰은 항상 연산자이다.
3. 수식에서 읽어낸 토큰이 연산자인 경우에는 가지 노드가 되며, 이 토큰 다음에 따라오는 두 개의 토큰은 각각 오른쪽 자식 노드와 왼쪽 자식 노드가 된다. 단, 다음 토큰에도 연속해서 연산자인 경우에는 이 토큰으로부터 만들어지는 하위 트리가 완성된 이후에 읽어낸 토큰이 왼쪽 자식 노드가 된다.
4. 수식에서 읽어낸 토큰이 숫아지면 이 노드는 잎 노드이다.
문제를 하나 풀어보자
1.'+' 가 가장 마지막 토큰을 취하여 루트 노드가 된다.
뒤 두 개 중에서 첫 번째 토큰이 연산자인 경우에는 두 번째 토큰을 첫 번째 토큰의 피연산자로 사용해야 하기 때문이다. 그래서 토큰은 하나씩만 읽어들여서 먼저 연산지인지 숫자인지 확인을 해야한다.
2. '+' 연산자 다음의 토큰은 '-' 연산자이다. 수식을 뒤에서부터 읽고 있다는 것을 기억하자. 이 토큰 역시 또 다른 두 개의 토큰이 필요하다. 일단 '-'을 오른쪽 자식 노드로 만들어준다.
'-' 노드는 연산자 노드이니 양쪽 자식으로 피연산자가 필요하다. 다음 8을 오른쪽에 붙여주고 7을 왼쪽 자식에 붙여준다. 새로운 자식 노드들은 모두 숫자를 가지고 있으므로 자식이 없는 잎 노드이다.
'*'는 루트로 부터 왼쪽 자식에 붙여준다. 이 노드는 연산자이니 1은 왼쪽 자식으로 2는 오른쪽 자식으로 붙여준다.
분리 집합: 교집합을 갖지 않는 집합들
: 서로 공통된 원소를 갖지 않는 집합들을 말한다. 두 개 이상의 집합을 일컬을 때만 사용할 수 있는 개념이다.
분리 집합에 교집합이 있다면 그것은 분리 집합이 아니다. 분리 집합에는 합집합만 있을 뿐이다.
분리 집합은 집합들 간의 교집합을 허락하지 않기 때문에 서로 구분되어야 하는 데이터 집합을 다룰 때 아주 유용하다.
ex) 책가게의 판매관리 프로그램
베스트셀러 책을 할인하려고 한다. 일반 도서와 베스트셀러 도서를 따로 구분하는 것
분리 집합은 원소 또는 개체가 "어느 집합에 소속되어 있는가?" 라는 정보를 바탕으로 하는 알고리즘에 응용할 수 있다.
분리 집합의 표현
일반 트리나 이진 트리는 모두 부모가 자식을 가리키는 포인터를 갖고 있다. 분리 집합은 이와는 반대로 자식이 부모를 가리킨다.
루트 노드는 집합 그 자체이고, 루트 노드 자신을 포함한 트리 내의 모든 노드들은 그 집합에 소속된다고 보면 된다. 링크드 리스트에서 헤드가 링크드 리스트를 나타내는 것을 떠올려보면 이해가 될 것이다.
분리 집합의 연산
합집합과 집합 탐색만 기억하면 된다.
합집합
집합 탐색
이 연산은 집합에서 원소를 찾는 것이 아니라, 원소가 속해 있는 집합을 찾는 연산이다. 집합 내의 어떤 노드든 루트 노드가 나타내는 집합이 곧 자신이 속해 있는 집합이므로, 해당 원소(노드)가 어떤 집합에 속해 있는지 알려면 이 원소가 속해 있는 트리의 루트 노드를 찾으면 된다.
'C++ > 뇌를 자극하는 알고리즘' 카테고리의 다른 글
| 5장 정렬 (0) | 2022.02.14 |
|---|---|
| 3장 큐 (0) | 2022.02.02 |
| 2장 스택 (0) | 2022.02.01 |