트리 {이진트리, 수식트리, 분리 집합}
트리: 나무를 닮은 자료구조, 트리는 뿌리(Root), 가지(Branch), 잎(Leaf) 3가지 요소로 이루어져 있음.
뿌리, 가지, 잎은 모두 똑같은 노드이다. 어디에 위치하는가에 따라 불리는 이름이 달라질 뿐.
뿌리 - 트리 자료구조의 가장 위에 있는 노드 , 가지 - 뿌리와 잎 사이에 있는 모든 노드
잎 - 가지의 끝에 매달린 노드, 끝에 있다고 해서 단말 노드라고 부르기도 한다.
B는 C와D의 부모(Parent), C와 D는 B의 자식(Children), 그리고 한 부모 밑에서 태어난 C와 D를 형제(Sibling)라고 함.
B와 K는 아무 관계가 아니다.
경로: 한 노드에서 다른 한 노드까지 이르는 길 사이에 있는 노드들의 순서 I노드에서 K노드 까지 찾아간다면, I, J, K를
I에서 K까지의 경로라고 한다.
경로에는 길이(Length)라는 속성이 있고 출발 노드에서 목적지까지 거쳐야 하는 노드의 개수이다.
노드의 깊이(Depth): 뿌리 노드에서 해당 노드까지 이르는 경로의 길이. ex) I노드는 뿌리 노드인 A로부터 경로의 길이가 1이므로 깊이도 1. 뿌리 노드인 A의 깊이는 0이다.
레벨: 깊이가 같은 노드의 집합. ex) 레벨 2는 C, D, H, I 노드 전체를 가리킴.
높이: 트리의 높이는 가장 깊은 곳에 있는 잎 노드까지의 깊이를 뜻함. ex) 가장 깊이 있는 잎 노드가 E, F, K의 깊이가 3이므로 트리의 높이는 3이 된다.
차수: 노드의 차수는 그 노드의 자식 노드 개수를 뜻하고, 트리의 차수는 트리 내의 노드들 중 자식 노드가 가장 많은 노드의 차수를 뜻함. ex) A노드는 자식 노드가 3개이므로 차수가 3, G노드는 자식노드가 1개이므로 차수가 1, 트리 중 가장 많은 자식을 가진 노드는 A이므로 A의 차수 3이 트리의 차수가 된다.
트리 표현 방법
1. 중첩된 괄호 표현법: 같은 레벨의 노드들을 괄호로 함께 묶어 표현하는 방법. ex) (A(B(C)(D(E)(F)))(G(H))I(J(K))))
읽기는 어렵지만 트리를 하나의 공식으로 나타낼 수 있다는 장점이 있음
2. 중첩된 집합 표현법: 트리가 하위 트리의 집합이라는 사실을 잘 표현할 수 있음.
3. 들여 쓰기: 자료의 계층적인 특징을 잘 나타낸다 ex)윈도 탐색기의 폴더 트리
노드 표현 방법
1. N-링크 표현법: 노드의 차수가 N개면 N개의 링크를 가지고 있는데 이 링크들이 각자 자식 노드들을 가리키도록 노드를 구성하는 방법, 차수가 노드마다 달라지는 트리에는 적용하기 힘들다는 단점이 있음.
2. 왼쪽 자식 - 오른쪽 형제 표현법(Left Child-Right Sibling): 왼쪽 자식과 오른쪽 형제에 대한 포인터만을 갖도록 노드를 구성하는 방법
이 표현법을 쓰는 트리에서 어느 한 노드의 모든 자식 노드를 얻으려면 일단 왼쪽 자식 노드에 대한 포인터만 있으면 됨. 해당 포인터를 이용해서 왼쪽 자식 노드의 주소를 얻은 후, 이 자식 노드의 오른쪽 형제 노드의 주소를 얻고, 그다음 오른쪽 형제 노드의 주소를 계속해서 얻어나가면 결국 모든 자식의 노드를 얻을 수 있음.
트리의 기본 연산 (왼쪽 자식 - 오른쪽 형제 표현법)
트리의 노드 구조체: 데이터를 담는 Data 필드, 왼쪽 자식과 오른쪽 형제를 가리키는 2개의 포인터로 구성.
노드 생성/ 소멸 연산: malloc() 함수를 이용해서 자유 저장소에 할당, free() 함수를 이용해서 해제
자식 노드 연결 연산: 먼저 부모 노드인 Parent에게 자식 노드가 있는지 검사, LeftChild 노드가 NULL이라면 자식이 하나도 없다는 뜻이고 이때는 Parent의 LeftChild 포인터에 자식 노드 주소를 바로 저장.
Parent의 LeftChild가 NULL이 아닌 경우에는 자식 노드를 하나 이상 가지고 있다는 의미. 이때는 자식노드의 RightSibling 포인터를 이용해서 가장 오른쪽에 있는 자식노드(RightSibling이 NULL인 노드)를 찾아내고 이렇게 찾아낸 가장 오른쪽의 자식 노드의 RightSibling에 Child를 대입한다.
트리 출력 연산: Depth - 1 만큼 공백 3칸을 출력, 공백 마지막에는 해당 노드가 누군가의 자식 노드임을 나타내는 +--를 덧붙인 후 노드의 데이터를 출력. 이렇게 하면 깊이가 0인 뿌리 노드는 제일 앞쪽에 출력되고 잎 노드는 제일 깊은 곳에 출력된다.
이진트리: 하나의 노드가 자식 노드 2개까지만 가질 수 있는 트리. 노드의 최대 차수가 2이기에 모든 이진트리의 노드의 자식 노드 수는 0, 1, 2 중 하나이다. 이진트리는 컴파일러나 검색과 같은 알고리즘의 뼈대가 되는 특별한 자료구조이다. 특히 이진트리를 이용한 검색에서는 트리의 노드를 가능한 한 완전한 모습으로 유지해야 높은 성능을 낼 수 있음.
포화 이진트리: 잎 노드를 제외한 모든 노드가 자식을 둘 씩 가진 이진트리, 잎 노드들이 모두 같은 깊이다.
완전 이진트리: 앞 노드들이 트리 왼쪽부터 차곡차곡 채워진 것이 특징
높이 균형 트리: 뿌리 노드 기준 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 2 이상 차이 나지 않는 이진트리.
완전 높이 균형 트리: 뿌리 노드 기준 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 이진트리.
순회(Traversal): 트리 안에서 노드 사이를 이동하는 연산.
전위 순회: 1) 뿌리 노드부터 시작하여 아래로 내려오면서 2) 왼쪽 하위 트리 방문 3) 오른쪽 하위 트리 방문
하위 트리에서도 뿌리 노드 - 왼쪽 하위 트리 - 오른쪽 하위 트리 순으로 방문.
전위 순회를 이용하면 이진트리를 중첩된 괄호를 표현 가능. 뿌리부터 시작해서 방문하는 노드의 깊이가 깊어질 때마다 괄호를 한 겹 씩 두르면 된다. ex) (A(B(C, D)), (E(F, G)))
전위 순회가 활용되는 경우는 트리 복사.
중위 순회: 1) 왼쪽 하위 트리 2) 뿌리 노드 3) 오른쪽 하위 트리
왼쪽 하위 트리부터 시작한다는 건 트리에서 가장 왼쪽의 잎 노드부터 시작한다는 뜻.
중위 순회가 응용되는 사례는 수식트리에서 중위표기식을 사용할 때.
후위 순회: 1) 왼쪽 하위트리 2) 오른쪽 하위 트리 3) 뿌리 노드
전위 순환과 반대의 순서를 가지고 있다.
후위 순회가 응용되는 사례는 메모리에서 트리를 제거할 때, 수식 트리가 후위 표기법을 사용할 때
이진트리의 기본 연산
이진트리 노드 구조체: 왼쪽 자식을 가리키는 Left 필드와 오른쪽 자식을 가리키는 Right 필드, 데이터를 담는 Data 필드로 구성.
노드 생성 소멸 연산: malloc() 함수를 이용해 자유 저장소에 할당, free() 함수로 제거
이진트리 출력: 전위, 중위, 후위 순회를 이용한 트리 출력.
트리 소멸 연산: 트리 구축 시 어떤 순서로 생성해도 문제가 없지만 트리 파괴 시에는 반드시 잎 노드부터 자유 저장소에서 제거해야 한다. 이유는 부모 노드부터 제거 시 자식 노드들에게 접근할 수 없기 때문에 남아있는 자식 노드를 해제할 수 없게 되어 메모리 누수 발생. 따라서 후위 순회를 이용하면 문제없이 소멸시킬 수 있다.
수식 트리: 수식을 표현하는 이진트리. 수식트리의 일반적인 규칙
1. 피연산자는 잎 노드이다.
2. 연산자는 뿌리 노드 또는 가지 노드이다.
뿌리 노드와 가지 노드 모두 피연산자를 양쪽 자식으로 가지는데 이때 피연산자는 '수'일 수도 또 다른 '식'일 수도 있다.
그림에서 뿌리 노드인 +연산자는 왼쪽 하위 트리가 표현하는 수식 (1*2)와 오른쪽 하위 트리가 표현하는 수식 (3-4)를 피연산자로 가지고 있는데 뿌리 노드를 연산자로 각각의 결괏값을 피연산자로 계산을 수행하면 전체 수식의 결과 값을 알 수 있다.
수식 트리는 가장 아래에 있는 하위 수식트리로부터 수 또는 계산 결괏값을 병합하며 올라가는 과정을 반복하며 계산을 수행
=> 후위 순회 방법이 적합
수식 트리 구축 방법: 후위 표기식을 이용해 구축하는 게 수월, 후위 표기식을 입력받는다고 가정함.
1. 수식을 뒤에서부터 앞쪽으로 읽어나가며 토큰을 취한다.
2. 수식에서 제일 마지막에 있는 토큰으로 뿌리 노드를 생성한다. 후위 표기식에서 가장 마지막에 있는 토큰은 항상 연산자이다.
3. 읽어낸 토큰이 연산자라면 노드를 생성하며 다음에 따라오는 2개의 토큰으로 각각 오른쪽 자식 노드와 왼쪽 노드를 생성한다. 단 다음 토큰도 연산자인 경우 이 토큰에서 만들어지는 하위 트리가 완성된 이후 읽어낸 토큰으로 왼쪽 자식 노드를 생성한다.
4. 읽어낸 토큰이 숫자인 경우 잎 노드를 생성한다.
분리 집합: 서로 공통된 원소를 갖지 않는, 교집합을 갖지 않는 복수의 집합을 뜻함. 분리집합의 개념은 2개 이상의 집합에만 사용할 수 있음. 분리 집합에는 합집합만 있다. 소속 관계가 분명해야 하는 데이터를 다룰 때 유용. 원소 또는 개체가 어느 집합에 소속되어 있는지 정보를 바탕으로 동작하는 알고리즘에 응용할 수 있음.
합집합: 두 집합을 합한 집합.
분리 집합 표현: 자식이 부모를 가리킴. 뿌리 노드는 집합 그 자체이고 , 뿌리 노드 자신을 포함하는 트리 내의 모든 노드는 그 집합에 소속됨.
분리 집합의 노드 구조체: 부모 노드에 대한 포인터와 데이터 필드로 구성, 뿌리 노드는 부모가 없으므로 Parent가 NULL.
분리 집합의 기본 연산: 합집합과 집합 탐색 연산만 기억하면 된다. 원소가 어느 집합에 귀속되어 있는지 아는 것이 목표이다.
합집합 연산: 두 집합을 더하는 연산, 오른쪽 집합의 뿌리 노드를 왼쪽에 있는 뿌리 노드의 자식으로 만들면 쉽게 구현된다.
집합 탐색 연산: 원소가 속한 집합을 찾는 연산, 집합 내 어떤 노드에게든 트리의 최상위에 있는 뿌리 노드가 곧 자신이 속한 집합을 나타내므로 원소가 속한 트리의 뿌리 노드를 찾으면 됨. 부모가 NULL 인 뿌리 노드를 만날 때까지 타고 올라가서 반환하면 해당 노드가 소속된 집합을 반환하게 되는 것.