이 게시글은 윤성우 선생님의 자료구조 강의를 수강 후 나름대로의 내용 정리를 한 것임을 미리 밝힙니다.
스스로의 복습을 위해 작성한 글이므로 심층있는 학습을 위해서는 책의 구매 및 강의수강을 권장합니다.
Prologue
자료구조는 데이터를 표현하는 학문이다.
표현은 저장을 포함하는 것이다.
그리고 비션형 자료구조를 배우면서 자료구조는 데이터의 표현을 위해 배우는 것임을 확실히 느낄 수 있을 것이다.
앞에서 선형 자료구조들을 공부할 때는
1. 그 자료구조를 정의하는 구조체 정의
2. 함수 정의 : 기본적으로 데이터의 삽입과 삭제와 조회
와 같이 공부했는데
이번에 트리를 배우면서 정의하는 함수들은 이것들과 전혀 성격이 다를 것이다.
트리는 트리를 만들고 변경하고 조합하고 컨트롤한다.
(만들고 변경하고 조합하고 컨트롤하는 것이 무엇인가는 이후에 설명한다.)
(앞에서도 연결리스트 등을 만드는 함수를 정의한게 아니냐 할 수 있는데 그와는 성격이 다르다. 앞에서는 삽입,삭제 하면서 자동으로 연결리스트가 만들어진 것이다.)
즉, 트리라는 자료구조를 구성하는데 필요한 도구를 함수로 만들거고 트리라는 자료구조를 통해 데이터를 저장이 아닌 '표현'할 것이다.
1. 트리의 접근과 이해 -> 왜? 라는 의문을 늘 가지고 끊임없이 고민하면서 공부
(1) 그림을 통한 트리의 표현
ex. 조직도, 의사결정 트리 등
(2) 트리 관련 용어의 소개
노드 : 트리의 구성요소에 해당되는 A,B,C,D,E,F와 같은 요소 // 꼭 연결리스트의 노드는 X, 배열로도 표현 가능
간선 : 노드와 노드를 연결하는 연결선
루트 노드 : 트리구조에서 최상위에 존재하는 A와 같은 노드
단말 노드 : 아래로 또 다른 노드가 연결되어 있지 않은 E,F,C,D와 같은 노드
내부 노드 : 단말 노드를 제외한 모든 노드로 A,B와 같은 노드 (루트 노드도 내부 노드에 포함)
노드 A는 노드 B,C,D의 부모 노드이다.
노트 B,C,D는 노드 A의 자식 노드이다.
노드 B,C,D는 부모 노드가 같으므로 , 서로가 서로에게 형제 노드이다.
ex.B노드의 형제노드는 C,D이다.
노드 B는 노드 E,F의 부모 노드이기도 하다.
(3) 서브 트리의 이해
B를 루트노드로 하는 트리를 뗴어 놓고 보면 이 역시 트리이고 이를 서브 트리라 부른다.
이 때 D I J 로 이루어진 트리를 누구의 서브트리라 할 것이냐?
B를 루트노드로 하는 트리의 서브트리가 되기도 하지만 A를 루트 노드로 하는 트리의 서브트리가 되기도 한다.
(4) 이진 트리의 이해
각 노드에서 뻗어나가는 간선이 모두 두개이면 이진 트리라고도 할 수 있다.
하지만 이러한 표현은 트리의 재귀적인 성향을 담아내지 못한 완전하지 못한 표현이다.
나뉘어진 두 서브 트리도 모두 이진 트리여야 한다. 에서 이진 트리의 재귀적인 성질을 엿볼 수 있다.
시험에서 이진 트리의 조건을 묻는다 하면
반드시 1. 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 진다. 2. 나뉘어진 두 서브 트리도 모두 이진트리이어야 한다.
라고 해야하는데 문제가 있다.
그림에서 B D E로 이어진 트리는 이진트리의 조건에 맞지 않다고 생각할 수 있다.
그래서 세개의 노드로 이루어진 트리에 대한 정의를 따로 하여 기반 조건을 만들어야 할 것 같은데...
결론적으로는 단말노드 D,E 역시 이진 트리라서 B D E로 이루어진 트리 역시 이진트리이다.
(5) 이진 트리와 공집합 노드
공집합 노드도 노드로 간주하기에 단말노드 역시 이진트리로 간주한다.
공집합 노드도 노드이므로 공집합 노드도 두개의 자식 노드를 가질 수 있기 떄문이다.
굳이 공집합 노드를 만드는 이유는?
이진 트리는 하나의 노드에 두개의 자식 노드를 추가할 수 있는 트리를 이진 트리라 한다.
그림의 A B C D E 로 이루어진 트리 역시 이진 트리인 것이다.
이 트리의 빈, 다른 노드를 추가할 수 있는 자리에 공집합 노드를 추가하면 이는 이진 트리임을 알 수 있다.
그럼 세상의 트리는 모두 이진트리 아니냐?
그것은 당연히 아니다. 하나의 노드에 두개를 초과한 자식 노드를 다는 순간 당연히 이진 트리가 아니게 된다.
같은 논리로 밑의 A B C D로 이루어진 트리 역시 이진트리이다.
(6) 레벨과 높이, 그리고 포화, 완전 이진 트리
레벨 - 루트 노드를 레벨 0으로 잡고 한 계층 내려갈 때마다 레벨은 + 1
높이 - 레벨의 최댓값과 같으나 최대레벨을 높이라 가리키는 것은 X 높이는 높이
(루트 노드에서 최대레벨에 있는 단말노드까지의 간선의 개수를 높이라 보면 편할 듯하다.)
포화 이진 트리 - 모든 레벨에 노드가 꽉 찬 트리가 포화 이진 트리이다.
완전 이진 트리 - 위에서 아래로 왼쪽에서 오른쪽으로 순서대로 채워진 트리를 의미한다.
모든 포화 이진 트리는 완전 이진 트리이나 모든 완전 이진 트리는 포화 이진 트리가 아니다.
(구현에 있어서도 사용되므로 완전 이진 트리는 매우 중요한 용어이다.)
