제7 장 트리)
개관)
트리에서는 용어를 정확하게 아는 것이 중요하다.
이렇게 생긴 게 트리다.
좀 덜 구체적인 트리 이미지를 가지고 오고 싶었는데 이게 제일 먼저 나와서...
교재에는 이진 트리 외에 언급하지 않으니 일단 이걸 쓰자.
아, 이미지를 하나 찾았다.
트리에서도 학습할 내용이 방대하다.
나야 책 보면서 나름대로 기록한다고 드문드문 쓰고 있지만 트리에 대해서 제대로 공부하고 싶으면
바로 위에 있는 링크에서 필요한 내용을 꼭 꼼꼼히 보는 걸 추천한다.
CS 공부를 하려면 한글 블로그에서 뭘 찾으면 절대 안 되고 😊... 제대로 정리된 해외 사이트를 이용하시라...
아무튼, 트리에서 저기 동그란 걸 노드라고 한다.
차수(Degree)는 노드에 달린 자식의 개수다.
트리에 속한 모든 노드의 차수가 2 이하인 트리를 이진 트리라고 한다.
이진 트리는 수학적으로 이론을 정리하기도 쉽고, 컴퓨터 내부에 구현하기도 쉬워 자주 이요된다.
이진 트리에서 각 레벨(위에서부터 내려오는 '단', '층')이 허용되는 최대 개수 노드를 가질 때 그 트리를 가득 찬 이진 트리라고 한다.
용어를 하나 하나 정리하는 게 너무 귀찮아 그냥 이미지를 가져 왔다.
완전 이진 트리(Complete Binary Tree)는 다음과 같다.
자... 이제 슬슬 헷갈리기 딱 좋은 지점으로 들어간다...
트리도 오래 안 보면 뭐가 뭐였는지 까먹는다...
아무튼 트리 분량이 많아서 여러 번 반복해서 언급할 거니까 지금 당장 모든 걸 설명하지 않는다고 신경 쓸 건 없다.
...
학습 목표)
트리의 용어와 표현 방법을 이해하자.
트리의 추상 자료형을 이해하자.
이진 트리의 개념과 구현 방법을 이해하자.
이진 트리의 순회 연산과 생성, 삽입, 삭제 연산을 이해하자.
...
용어 정리)
전 이진 트리(Full Binary Tree): 모든 노드가 0 또는 2개의 자식을 갖는 트리(위 이미지에 있다.).
가득 찬 이진 트리(Perfect Binary Tree): 이진 트리에서 각 레벨이 허용하는 최대 개수 노드를 가지는 트리
완전 이진 트리(Complete Binary Tree): 높이가 k인 이진 트리가 레벨0부터 k-2까지 다 채우고 마지막 k-1레벨에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워진 트리
...
여기까지 읽고 나니까 번역이 진짜 마음에 안 든다.
전 이진 트리랑 완전 이진 트리랑 이름만 가지고 분별이 되나? 😄
이런 건 원어를 병기해야 하는 거 아닌가?
...
1. 트리
교재 161페이지를 보면 모든 트리의 종류에 대해 아주 멋지게 정리해 놓은 표가 있다.
유사한 이미지가 없나 싶어 인터넷 검색을 해 봤는데 없다.
보고 싶으면 교재를 빌려 보거나 구매 하시라.
...
2. 용어와 논리적 표현 방법
루트 노드는 진입 차수가 0이다.
루트를 제외한 모든 노드의 진입 차수가 1이면 그건 트리다.
진입 차수가 2 이상인 경우, 그래프다.
트리에서 각 노드의 차수(degree of a node)는 진출 차수로 정의한다.
트리의 차수(degree of a tree)는 트리 안에 있는 각 노드의 차수 가운데 최대 차수로 정의한다.
...
트리 레벨을 1로 시작하는 사람?들?이 있는데 나는 그런 걸 제일 싫어한다.
인덱스를 0부터 시작하는 걸로 합의 봤으면 트리 레벨도 0부터 시작해야 한다고 생각한다.
안 그러면 혼란스럽잖아.
교재에서는 0부터 시작한다.
...
3. 추상 자료형
트리는 데이터의 계층 관계, 포함 관계 등을 나타내는 자료구조다.
따라서 트리로 표현할 수 있는 데이터는 매우 광범위하며, 적용할 연산도 응용에 따라 매우 다양하다.
그래서 트리는 (가능하나) 일반적인 추상 자료형을 적용하기 어렵다.
...
4. 이진 트리
트리의 높이는 잎의 레벨에 1을 더한 것이다.
이진 트리 종류 쉽게 구분하는 법:
전 이진 트리(full): 모든 노드의 자식이 0 또는 2개다.
가득 찬 이진 트리(perfect): 모든 노드의 자식이 2개다.
완전 이진 트리(complete): 잎 노드 바로 위 레벨까지 노드의 자식이 2개로 다 차 있고 리프 노드가 왼쪽부터 오른쪽으로 순서대로 찬다.
...
공간(메모리) 낭비를 하지 않기 위해 이진 트리는 보통 연결 리스트로 구현한다.
...
5. 이진 트리 연산
트리의 각 노드를 빠짐 없이 그리고 중복 없이 한 번씩 방문하는 것을 순회한다(traverse)라고 한다.
여기서 '방문한다'는 '출력한다'로 생각해도 좋다.
트리는 보통 연결 리스트로 구현한다.
트리 순회 방법으로는
전위 순회(PLR): 루트 방문 > 왼쪽 서브트리를 전위 순회로 순회 > 오른쪽 서브트리를 전위 순회로 순회
중위 순회(LPR): 왼쪽 서브트리를 중위 순회로 순회 > 루트를 방문 > 오른쪽 서브트리를 중위 순회로 순회
후외 순회(LRP): 왼쪽 서브트리를 후위 순회로 순회 > 오른쪽 서브트리를 후위 순회로 순회 > 루트를 방문
아주 중요하다. 시험에 내기 딱 좋다. 그런데 자주 안 보면 잘 까먹는다.
총 6가지 방법이 있어도 교재에는 3개에만 나온다. 감사하다.;
전위는 루트부터 찍는다, 중위는 중간에 루트를 찍는다, 후위는 루트를 마지막에 찍는다.
나는 이렇게 외운다.
...
컴파일러는 프로그래머가 작성한 수식을 후위 표기법으로 바꾸어 트리로 구성하여 후위 순회로 계산되도록 한다.
...
이 지점부터 C 코드가 더욱 눈에 잘 안 들어오기 시작함. 🥹... 이게 뭐지? 이게 왜 여기에...? 하면서...
...
6. 일반 트리를 이진 트리로 변환
1. 주어진 트리에 대해 각 노드의 형제들을 연결한다.
2. 각 노드에 대해 가장 왼쪽 링크만 남기고 모두 제거한다.
3. 루트 노드는 반드시 왼쪽 자신 하나만 가지도록 한다.
교재 183페이지에 나와 있는 이미지 보면 딱 이해가 되는데 인터넷에서는 비슷한 이미지도 찾지를 못 하였다.
...
이제 스레드 트리 보러 가자!
'방송대 컴퓨터과학과 > 자료구조' 카테고리의 다른 글
| 방송대 자료구조 교재 요약 제9 장 - 힙 (0) | 2024.05.02 |
|---|---|
| 방송대 자료구조 교재 요약 제8 장 - 스레드 트리 (0) | 2024.05.01 |
| 방송대 자료구조 교재 요약 제6 장 - 연결 리스트의 응용 (0) | 2024.05.01 |
| 방송대 자료구조 교재 요약 제5 장 - 연결 리스트 (0) | 2024.04.30 |
| 방송대 자료구조 교재 요약 제4 장 - 큐 (0) | 2024.04.30 |
