[D+50] Graph, Tree, BST (Binary Search Tree)

 

D+50

-  Graph, Tree, BST -

( Graph, Tree, BST )

 

---

 

 

Graph

 

 

Graph 특징

• 그래프는 노드와 노드와 노드를 연결하는 간선(edge)으로 구성되어있다.

 

•방향이 없는 무방향이거나, 방향을 가지는 방향성 둘다 가질 수 있다.

   무방향 (Undirected Graph) → 간선에 의해 연결된 2개의 노드가 대칭일 수 있다. (ex. A → B, B → A)

   방향 (Directed Graph) → 간선에 의해 연결된 2개의 노드가 비대칭이다. (ex. A → B, B ↛ A)

 

차수 degree

degree는 해당 노드의 연결된 엣지의 수를 가리킨다.

 

• 진입차수 (in-degree)

진입차수는 정점을 기준으로 들어오는 간선의 수로

정점에 부속된 간선의 방향이 머리로 하는 간선의 수이다.

 

• 진출차수 (out-degree)

진입차수는 정점을 기준으로 나가는 간선의 수로

정점에 부속된 간선의 방향이 꼬리로 하는 간선의 수이다.

 

ex)

A의 진입차수는 2이고, 진출차수는 1이다.

B의 집입차수는 1이고, 진출차수는 1이다.

C의 진입차수는 1이고, 진출차수는 1이다.

 

인접행렬방식과 인접리스트 방식

• 인접행렬방식

그래프를 2차원표로 표현하는 것으로

노드와 노드사이에 간선으로 연결되어 있다면 1, 그렇지 않으면 0을 넣어 표현하게 된다.

 

 

• 인접리스트방식

배열방에 모든 노드들을 집어넣고 각 배열방에 있는 해당노드와 인접한 노드들을

연결리스트로 쭉 나열해서 저장한다.

 

ex) 노드 1은 노드 2와 3이 간선으로 연결되어 있다.

 

 

---

Tree

 

 

Tree 특징

• 노드로 구성된 계층적인 자료구조이다.

 

• 최상위 노드(루트)를 만들고, 로트 노드의 child를 추가하고, 그 child에 그 child에 또 child를 추가하는 방식으로

트리구조를 구현할 수 있다.

 

Tree 관련 용어

• node - 트리의 구성요소

 

• root - 트리구조에서 최상위에 존재하는 노드

 

• depth - 루트를 기준으로 다른 노드로의 접근하기 위한 거리

 

• height - 로트로부터 가장 멀리 떨어진 노드의 깊이

 

• sibling - 같은 부모 같은 depth에 존재하는 노드

 

• edge - 노드와 노드를 잇는 선

 

• leaf - 자식이 없는 노드

 

 

---

BST ( Binary Search Tree )

 

 

BST 특징

• 최대 2개의 자식만을 가지는 트리이다.

 

• 이진 탐색 트리에서는 노드의 값이 정렬 방법에 따라 순서가 존재하는데,

노드의 왼쪽 서브트리에는 노드의 값보다 작은 값이 들어가고

오른쪽 서브트리에는 노드의 값보다 같거나 큰 값이 존재한다.

 

 

깊이 우선 탐색 (DFS)

특정 노드에서 시작해 다음 분기로 넘어가지 전에 해당분기를 맹목적으로 완벽하게 탐색하는 방법이다.

 

 

이진 탐색 트리 순회하기

• 전위 순회 (preorder traverse) 

   부모 → 왼쪽 → 오른쪽 순으로 방문힌다.

 

• 중위 순회 (inorder traverse) 

   왼쪽 → 부모 → 오른쪽 순으로 방문힌다.

 

• 후위 순회 (postorder traverse) 

   왼쪽 → 오른쪽 → 부모 순으로 방문힌다.

 

ex)

전위순회 : 0→1→3→7→8→4→9→10→2→5→11→6

 

중위순회 : 7→3→8→1→9→4→10→0→11→5→2→6

 

후위순회 : 7→8→3→9→10→4→1→11→5→6→2→0

 

이진 탐색 트리 종류

• 정 이진 트리 (Full Binary Tree)

   모든 노드가 0개나 2개의 자식노드를 가지는 트리

 

• 완전 이진 트리 (Complete Binary Tree)

   왼쪽자식노드부터 채워지며 마지막 레벨을 제외하고 모든 자식 노드가 채워져있는 트리

 

• 포화 이진 트리 ( Perfect Binary Tree)

   모든 leaf노드가 똑같은 레벨에 있는 트리