트리

그래프의 일종으로 계층형 자료구조다.
그래프를 약간 제한시켜 만든 자료구조.

파일시스템(폴더)이 사용하는 것이 트리 이다.

트리에는 사이클이 없다.

데이터가 저장된 노드와 노드간 관계(부모자식)를 표현하는 간선으로 구성된다.

트리는 제귀적인 구조를 가지고 있다.(트리 안에는 또다른 트리(Sub-tree)가 있다.)

std::set / std::map / std::multiset / std::multimap 으로 구현되어 있다.

레드블랙트리로 구현되어 있다.

set : 유일한 데이터를 저장하는 자료구조
반환값은 pair 이며 set::pair<iterator, bool> 을 반환한다.
연산
count() : 데이터가 몇 개인지 센다.

map : 첫 번째 템플릿 파라미터는 키의 타입을, 두번째 템플릿 파라미터는 값을 타입을 지정
std::map<std::string, int> ageMap;

// 원소 접근
// [] 연산자로 ageMap에 있는 원소를 접근할 수 있다.
std::cout << ageMap["홍길동"] << "\n"; // 23
std::cout << ageMap["김철수"] << "\n"; // 17
ageMap["홍길동"] = 25; // 이제 홍길동과 대응되는 데이터는 25다.
ageMap["이영희"] = 19; // 새로운 데이터를 삽입할 수도 있다.

용어 정리

조상 노드(Ancestor) :

한 노드에서 간선을 따라 루트 노드(트리의 시작 노드)까지 이르는 경로에 있는 모든 노드

자손 노드(Descendant) :

조상 노드이 반대

차수(Degree) :

한 노드가 가지는 서브 트리의 수(간선 수). 노드의 차수 중 최댓값을 트리의 차수라 한다.

내부 노드(Internal) :

단말 노드를 제외한 나머지 노드

포레드트(Forest) :

트리의 집합

루트 노드(Root) :

트리의 시작 노드 Level 0

리프 노드(Leaf) :

자식이 없는 노드

형제 노드(Siblings) :

같은 항렬? 을 가진 노드 같은 위치에 있다고 보면 된다.

트리의 높이 개념도 있다. 위 사진은 Level3 까지있으니 높이는 3이다.

순회

전위 순회 :

루트노드를 먼저 방문하고 자식 노드를 순서대로 방문. 보통 왼쪽부터 간다.
A - B - D - H - I - E - J - C - F - G
깊이 우선탐색(DFS)과 같다.

중위 순회 :

자기 자신을 중간에 방문(왼쪽을 돌았으면 나를 방문 후 오른쪽으로 간다.)
H - D - I - B - J - E - A - F - C - G

후위 순회 :

맨 뒤에 루트노드가 방문된다.(왼쪽에 있는 자식노드를 먼저방문 후 오른쪽에 있는 자식노드를 방문 후 본인노드를 방문)
H - I - D - J - E - B - F - G - C - A

레벨 순회 :

너비 우선 탐색과 같다(BFS)
A - B - C - D - E - F - G - H - I - J

B트리

데이터베이스나 파일 시스템에서 널리 사용되는 트리 자료구조의 일종

이진 검색 트리

Binary Search Tree

한 노드(본인)를 기준으로 왼쪽서브 드리는 모두 그 노드(본인)보다 작은 값을 가지고 있으며, 오른쪽 서브 트리는 모두 그 노드(본인)보다 큰 값을 가지고 있는 이진 트리(트리의 차수가 2 이하) 이다.

STL에 구현되있는 모든 트리 컨테이너는 모두 이진 검색 트리다.

연산

트리가 균형잡혀 있다면 O(logN)이지만 편향되어 있다면 O(N)에 가까워 진다.

균형잡혀 있는 트리 : 루트노드를 기준으로 서브트리의 레벨이 같거나 비슷한 경우

편향되어 있는 트리 : 루트노드를 기준으로 서브트리 레벨의 차이가 심할경우

이진검색트리를 중위순회 하면 작은값부터 오름차순으로 나온다.

데이터 삽입의 순서가 중요하다.

AVL트리

자가 균형 이진 탐색 트리

어떤순서로 삽입 삭제를 하던 회전을 하여 균형잡힙 트리를 만들어준다.

레드블랙트리

자가 균형 이진 탐색 트리

AVL 트리의 발전형태