트리와 그래프

트리가 왜 필요할까?

 

1. 계층형 자료구조.

2. 균형잡힌 트리에 한해 O( log N ) 이라는 일반적인 순차적 탐색 ( O( N ) )보다 빠른 속도가 보장

 

 

나무위키좌님께서 
수학, 특히 그래프 이론에서 회로[1]가 없는 연결 무향 그래프를 트리라고 한다

                                        [1] =Cycle

 

사이클이없는 방향성이 없는 그래프라고 정의할 수 있는데

 

자료구조에서 나타내는 트리는

 

쉽게 구현 가능하고 익숙하기에 트리부터 보자.

 

트리의 특성

 

• 부모가없는 루트노드가 존재.
• 루트노드는 0개 이상 자식 노드를 갖고 있다.
• 그 자식 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

 

그렇다면 이제 이진트리를 봐야하는데

 

삼진 사진도아니고 왜 굳이 이진트리인지 잘 몰라서 검색해봤습니다.

 

 - 굳이 이진트리인 이유

   1. 단순한 구조로 학습에 도움이 된다.

   2. 판별식이 단순히 T,F로 좌우로 나뉠 수 있기 때문에 구현 난이도 대비 성능도 좋은편

  이랍니다.

 

이진트리는 단순히 자식의 최대 노드가 두개인 트리입니다.

 

거기서 발전해서 이진 탐색트리라는 형식을 많이 사용합니다.

 

이진트리 : 단순히 최대노드가 2개,

이진탐색트리 : 좌는 부모보다 작고 우는 부모보다 큰값이 들어갑니다.

 

 

 

 이진탐색트리의 삽입방법입니다.

 

 

 

 

 

 

 

 

 

 

왜 이진탐색트리를 쓰지...?

 

보시면.. 정렬된 배열도 스텝10 까지 가는반면

이진탐색트리는 27뿐아니라 모든값을 평균적으로 스텝3만에 찾아낼수있습니다.

 

성능의 기본값을 보장해주죠.

 

잘 모르겠지만 공식언어들의 정렬 기본 알고리즘이라던가 자료구조들은 최선과 최악의 편차가 큰 자료구조보다 평균값이 좋은 자료구조를 좋은 자료구조라고 생각하는 것 같습니다.

 

안정성을 생각하면 당연하다고 볼수있겠네용..

 

 

 

 

 

 

 

이진탐색트리의 종류는 책에있는 3가지만 그림으로 다루고 가보겠습니다.

 

 

전 이진 트리 (FULL Binary Tree) 

 - 모든 노드의 자식이 없거나 2개임

 

완전 이진 트리 (Complete Binary Tree)

 - 트리의 모든 높이에서 노드가 꽉 차있는 이진 트리를 말한다. 마지막 단계에서는 꽉 차있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야한다.

 - 보통 이진트리라 함은 완전 이진트리를 기본으로 생각 ( 본인생각 )

 

포화이진트리 (Perfect Binary Tree)

 - 전 이진 트리 + 완전 이진 트리인 경우

 - 모든 말단 노드는 같은 높이여야하면서, 마지막 단계에서 노드의 수가 최대라면 포화이진트리

 

 

이진 트리 순회

 

 

중위 순회

 LEFT -> ROOT -> RIGHT

 

8 4 9 2 10 5 11 1 12 6 13 3 14 7 15

 

 

 

 

 

전위 순회

 ROOT -> LEFT -> RIGHT

 

 

 

1 2 4 8 9 5 10 11 3 6 12 13 7 14 15

 

 

후위 순회

 LEFT -> RIGHT -> ROOT

 

8 9 4 10 11 5 2 12 13 6 14 15 7 3 1

 

 

 

 

 

 

 

이진 힙

 

 

1부터 100까지의 정수를 저장한 최대 힙의 예시. 모든 부모노드들이 그 자식노드들보다 큰 값을 가진다.

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다. - 위키백과, 우리 모두의 백과사전.

 

 - 최대, 최소값을 루트에 놓고 삽입, 삭제시마다

 - 힙검사를 통하여 루트값 = 최대값 or 최소값이 유지되는 자료구조.

 

삽입 , 삭제 = O(log n)

 

접두사 트리 - 트라이(trie) 

 

 

 문자열을 위해 태어난 접두사 트리 트라이(trie)

 

 

 

 

 

 

 

 

 

1. 트라이처럼 쓰면 맵과 비교했을때 어떤지..?

 

map을 이용하면 충분히 트라이와 같은 효과를 낼 수 있지 않을까??

 

맵을 이용하면 충분히 트라이와 비슷(?)한 효과를 낼 수 있다.

 

하지만, 맵의 특성상 이진 검색 트리에서 O(logN)만큼의 시간이 들 것이고, 그 문자열을 확인하는데

 

O(N)만큼의 시간이 들 것이기에 map을 이용하는 것( O(N log N) ) 과 Trie ( O(N) )를 이용하는 것은 엄연히 다른 시간 복잡도를 나타낸다.

출처: https://www.crocus.co.kr/1053 [Crocus]

맵과 비교했을때 만약 이진 탐색트리라면 ...?

 

2. 장점은? 

문자열한정 탐색속도가 최고다 O(N) 에 끝낼 수가 있다.

 

3. 단점 

문자열 검색에 있어서는 가장 효율적이라고 볼 수 있다.

하지만 보통 단어를 그냥저장하면 var x = "abc";이면 끝이지만

트라이의 저장방식은 var first = "a"; var second = "b" ... 이런식..

하나하나를 각각 저장해서 비교하기땜시 상당히 큰 자료구조가 필요하다.

알파벳이 26개니 풀로 4번만채워도 26*26*26*26 = 456,976 ... 

 

즉 최종 메모리는 O(포인터 크기 * 포인터 배열 개수 * 트라이에 존재하는 총 노드의 개수)가 된다.
이렇다고한다.

 

 

그래프

 

- 트리는 그래프의 일종이었습니다.

- 그래프는 단순히 노드와 간선을 하나로 모아 놓은 것

- 간선에는 방향성이 있을수도, 없을수도 있다.

- 여러개의 고립부분 그래프로 구성될 수 있다.

 

그래프는 인접행렬, 인접리스트로 보통 나타냅니다.

 

사실 그냥 필요한부분만 저장하는건 리스트,

필요없는거 다저장해두는건 행렬이라고 하는거 같은데,

 

둘다 배열로 해도되고, 둘다 리스트로 해도 된다.

필요한부분만 저장하는걸 배열로 구현하려면 매번 필요한 배열의 크기를 모르기때문에

매~번 구해줘야하는 알고리즘이 추가되야되는 번거로움 때문에 리스트를 쓰는듯.

 

 

그래프 탐색 ( BFS, DFS )

정말 자주나와서 .. 색입힘

 

깊이 우선 탐색( DFS, Depth-First Search )의 개념

 

- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

 

1. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사함

 

2. 즉 넓게(wide) 탐색하기 전에 깊게(deep) 탐색함 

 

3. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함

 

4. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함

 

5. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

 

※ 깊이 우선 탐색(DFS)의 특징

- 자기 자신을 호출하는 순환 알고리즘의 형태를 지님

- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것 (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있음)

 

 

※ 너비 우선 탐색 (BFS, Breadth-First Search)

 

- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

 

1. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

 

2. 즉 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것

 

3. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택함

 

ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash 와 Vanessa 사이에 존재하는 경로를 찾는 경우

 

* 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야할지도 모름

* 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색

 

※ 너비 우선 탐색(BFS)의 특징

 

- BFS 는 재귀적으로 동작하지 않는다.

- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.

- BFS 는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용함 

- 즉 선입선출(FIFO) 원칙으로 탐색

 

※ 너비 우선 탐색(BFS)이 과정

 

- 깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.

 

 

 

 

 -- > 차이점이다

 

 

 

 

 

 

 

 

 

 

 

레드 -

블랙 트리

꼭 알아야 하지만.. 이거 설명이 진짜 길고 어려워서 죄송하지만 링크첨부로 대체 

https://zeddios.tistory.com/237

집에가서 꼭 읽어보시길 바라겠습니다 ㅠㅠ..

 

 

B- Tree, B+ Tree

B Tree 계열은 데이터베이스에서 근본이 되는 자료구조입니다.

꼭 알아두셔야합니다. 저도 몰랐다가 털렸기에

간단히 설명하자면 노드에 들어있는 판별키가 여러개입니다.

그사이에 서브트리를 끼워넣는 방식으로 만들어져 있습니다.

 

왜?

이렇게 하는 이유는 이진 탐색트리 등의 구조들에서는 logN이라는 평균적인 탐색 속도를 보장 한다고 했습니다만

하드디스크같은 2차 저장장치에서는 접근시간이 연산시간보다 훨씬 긴 경우가 다분히 발생되기 때문에, 접근을 덜하기 위해서 tree의 depth ( 높이, 깊이 ) 를 줄이기 위해 폭을 늘려서 사용한다고 생각하시면 될것같습니다.