자료구조 Graph / Tree / Binary Search Tree

오늘은 자료구조 Graph / Tree / Binary Search Tree 에 대해 학습했다. 

내가 아는 지식 선에서 개념만 정리 해보고자 한다.

 

 Tree 

먼저 앞에서 Array, Stack, Queue 에서 배웠는데 이것들은 일직선 데이터 구조이지만

Tree는 부모 자식이 관계를 가짐.. 계층이고 그룹이다. 이것이 가능한 것은 노드가 하나 이상의 child를 갖기 때문

 

데이터가 바로 아래에 있는 하나 이상의 데이터에 단반향으로 연결되는 계층적 자료구조

데이터를 순차적으로 나열시킨 형태인 선형 구조 x, 하나의 데이터 뒤에 여려 개의 데이터가 존재할 수 있는 비선형 구조

계층적으로 표현이 되며 아래로만 뻗기 때문에 사이클 x

 

트리 구조는 루트(Root) 라는 하나의 꼭지점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결,

이 데이터들을 노드(Node)라고 하며 상위 노드와 하위 노드가 연결이 되면 부모/자식관계 가진다.

A는 B와 C의 부모노드(Parent Node)가 되고, B와 C는 A의 자식노드(Child Node)가 된다.

자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(leaf Node)라고 한다.

 

높이와 깊이 측정 가능!

주트에서 자신에게 걸리는 거리를 레벨(Level)이라고 부르고, 루트를 Level 1로 설정

노드와 노드의 간격(거리)를 레벨(Level)이라고 부른다.

첫번째 노드인 루트를 Level 1로 설정

루트부터 가장 안쪽에 있는 노드까지의 레벨을 트리의 높이라고 하고 반대로 특정 노드부터 시작하여 루트까지의 레벨을 노드의 깊이라고 표현

같은 레벨에 나란히 있는 노드 = 형제 노드(sibling Node)

 

root 에서 뻗어 나오는 큰 트리의 내부에 트리의 모양새를 갖춘 작은 트리를 서브 트리라고 한다.

비단 D,H,I만 작은 트리가 아닌

B,D,E 나 C,F,G,J 도 서브 트리라고 할 수 있다.

 

 

 Binary Search Tree 

 

child 노드가 최대  두 개까지 붙는 트리는 Bainary Tree(이진 트리)라고 한다.

(세 개가 붙으면 Ternary Tree라고 한다.)

 

Bainary Tree(이진 트리)

다른 조건 없이 노드에 child가 최대 두개씩 붙어있는 것

 

Bainary  Search Tree

그 안에 데이터가 왼쪽 노드와 그 이하 child 들은 현재 노드보다 작아야하고 오른쪽 노드와 그 이하 child 들은 현재 노드보다 커야한다.

완전 이진 트리 : 마지막 레벨을 제외한 모든 노그가 가득 차 있어야 하고,

마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져 있어야 한다.

 

 

Perfect binary Tree (포화이진트리)

레벨의 개수를 n으로 가정할 때 2n 승- 1개의 노드를 가지는 것

포화 이진 트리 : 정 이진 트리이면서 완전 이든 트리인 경우

모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있는 트리

 

 

 Graph 

  - 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조

 

컴퓨터 공학에서 이야기 하는 그래프는 우리가 아는 그래프의 모양이 아니었다.

거미줄 처럼 여러 개의 점들이 선으로 이어져 있는 복잡한 네트워크 망과 같은 모습이었다.

 

서로 다른 점들이 직접적인 관계를 가지고 있다면 바로 이어주는 선이 존재하고,

간접적인 관계를 가지고 있다면 다른 여러 점을 거쳐서 이어지는 선이 존대할 수 있다.

점 = 정점(Vertex), 선 = 간선(edge)

방향이 있으면 = directed,  Tree는 directed

없으면 = undirected

하나 이상의 서클이있는 경우 = cyclic

서클이 없는 경우 = Acyclic

 

* Adjacency Matrix = 2차원 배열에 쓰임, 그래프를 표로 나타냄 연결이 되면 1, 안되면 0으로 표현한다.

* Adjacency List = 배열의 노드 나열하고 관계를 리스트로 나타냄

배열 방에 모든 노드를 집어 넣고 각 배열받은 해당 노드와 인접한 노드를 쭉 나열

노드들이 관계나타내는데 edge의 개수가 n 개 일 때

총 노드의 개수는 2n 개가 된다.

why??

=> 연결은 두 개의 노드가 연결되는 것이기 때문에 서로 연결되어 원래 edge보다 2배 많아짐.

 

 

참고

www.youtube.com/watch?v=fVcKN42YXXI

www.youtube.com/watch?v=LnxEBW29DOw&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP