[CS 스터디 발표] 자료구조(Data Structure) - 3

Tree

트리는 대표적인 비선형 자료구조로 방향성이 있는 비순환 그래프의 한 종류이다.

 

값을 가진 노드(Node)와 이 노드들을 연결해주는 간선(Edge)으로 이루어져 있다.

트리는 2개의 노드 사이에서 1개의 간선만을 가지며 사이클이 절대 존재하지 않는 방향 그래프이다.

 

Tree vs Graph

그래프는 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조이다.

이를 통해 연결된 노드 간의 관계를 표현할 수 있는 자료구조이다.

 

 

트리 순회 방식

전위 순회

Root → 왼쪽 자식 → 오른쪽 자식

 

중위 순회

왼쪽 자식 → Root → 오른쪽 자식

 

후위 순회

왼쪽 자식 → 오른쪽 자식 → Root

 

레벨 순회

루트부터 계층별로 방문하는 방식

 

이진트리

각 노드가 최대 두 개의 자식노드를 갖는 트리로 포화이진트리(Perfect-Binary Tree), 완전이진트리(Complete Binary-Tree), 정 이진트리(Full-Binary Tree)가 있다.

 

이진탐색트리

왼쪽 서브 트리에는 부모보다 작은 값, 오른쪽 서브 트리에는 부모보다 큰 값을 갖는 트리이다. 중복된 노드가 없어야 한다.

 

검색, 삽입, 삭제 : O(depth)

 

균등트리가 아니고 편향이 심한 트리면 검색 효율이 선형검색 급으로 떨어지기 때문에 이진탐색트리를 쓸 이유가 없어진다. 이를 개선한 트리가 AVL Tree, Red Black Tree, B Tree, B+Tree가 있다.

 

AVL 트리

 

1. 이진탐색 트리의 속성을 가진다.

2. 왼쪽, 오른쪽 서브 트리의 높이 차이가 1이다.

3. 높이 차이가 1보다 커지면 회전을 통해 균형을 맞춰 높이 차이를 줄인다.

4. 삽입, 검색, 삭제의 시간복잡도가 O(log N)

 

https://code-lab1.tistory.com/61

[자료구조] AVL트리란? AVL트리 쉽게 이해하기, AVL트리 시뮬레이터

 

Red Black 트리

자가 균형 이진 탐색 트리이다.

 

1. 모든 노드는 빨간색 혹은 검은색이다.

2. 루트 노드는 검은색이다.

3. 모든 리프 노드(NIL)들은 검은색이다.

4. 빨간색 노드의 자식은 검은색이다.

5. 모든 리프노드에서 Black Depth는 같다.

https://code-lab1.tistory.com/62

[자료구조] 레드-블랙 트리(Red-Black Tree)란? | 레드-블랙 트리 쉽게 이해하기

 

B Tree

기존의 이진트리를 확장하여 더 많은 수의 자식 노드를 가질 수 있게 일반화한 것이며 균등트리다.

• 노드의 자료수가 N이면, 자식 수는 N+1이어야 함
• 각 노드의 자료는 정렬된 상태여야함
• 루트 노드는 적어도 2개 이상의 자식을 가져야함
• 루트 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야함
• 외부 노드로 가는 경로의 길이는 모두 같음.
• 입력 자료는 중복 될 수 없음

https://code-lab1.tistory.com/217

[자료구조] B-트리(B-Tree)란? B트리 그림으로 쉽게 이해하기, B트리 탐색, 삽입, 삭제 과정

 

B+ Tree

리프 노드를 제외한 모든 노드는 키만 저장할 수 있으며 데이터는 리프토드에만 저장한다.

다른 노드에는 키만 저장하기 때문에 메모리 공간을 효율적으로 사용할 수 있다.

데이터를 전체 순회할 때 리프노드끼리는 연결리스트로 연결되어 있기 때문에 한번의 탐사로  전체 순회를 할 수 있다.