191230 TIL

오늘의 공부

 

1.Linked list(연결 리스트)

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되는 방식으로 데이터를 저장하는 자료 구조이다.

자바스크립트 배열로 비교하자면 array =  [1, 2, 3]이라는 배열이 있다면 여기서 1, 2, 3이 데이터고 array[0], array[1], array[2]가
주소이다.

자료의 처음을 head라 하고, 끝을 tail이라고 한다.Linked list의 method는 add(date 삽입), remove(data제거), search(position에 있는 노드를 찾기)가 있다.

 

 

12, 99, 37은 데이터 그리고 각 화살표는 포인터이다.

 

 

2.graph(그래프)

그래프 자료구조는 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료 구조로 연결되어 있는 객체 간의 관계를 표현할 수 있는

자료 구조이다.

지하철의 노선도로 비유할 수 있다.

이러한 그래프에서 사용되는 용어는 다음과 같다.

1. 정점(vertex): 위치의 개념으로 node라고도 부른다.
2. 간선(edge): 위치 간의 관계이며 노드를 연결하는 선이다.
3. 인접 정점(adjacent vertex):간선으로 직접 연결된 정점
4. 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
5. 진입 차수(in-degree):방향 그래프에서 외부에서 오는 간선의 수
6. 진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수
7. 경로 길이(path length): 경로를 구성하는데 사용된 간선의 수
8. 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
9. 사이클(cycle):단순 경로의 시작 정점과 종료 정점이 동일한 경우

위에 사진을 용어로 정리하자면 각각의 1, 2, 3, 4, 5, 6은 정점(vertex)이며 각 정점을 연결해주는 화살표가 간선(edge)이다.

1과 2는 간선으로 연결된 인접 정점(adjacent vertex)이고 사진은 방향 그래프이지만 만약 무방향 그래프라면 4의 정점의 차수(degree)는 2, 3, 5, 6 총 4개일 것이다.

1의 진입 차수(in-dgree)는 3에서 오는 간선하나가 있기에 하나가 될 것이고, 진출 차수(out-degree)도 1에서 2로 가는 간선 하나가 있기에 하나가 될 것이다.

그리고 사진에서 총 경로에 6개이므로 경로 길이(path length)는 6이다.

 

 

3.Tree(트리)

트리란??

트리구조는 방향 그래프의 한 종류라고 볼 수 있다.

스택과 큐가 데이터들을 순차적으로 나열시킨 선형 구조라면 트리는 데이터가 계층적으로 구성된 비선형 구조이다.

대표적인 예로 컴퓨터의 directory구조가 있다 Desktop -> myDocuments->myVideo처럼 폴더에서 폴더로 들어가는 구조이다.

조직도, 족보도 트리와 유사하다 볼 수 있다.

 

 

트리의 용어

• Root Node : 트리 구조에서 최상위에 존재하는 노드
• Node : 트리의 구성요소에 해당하는 요소
• Edge : 노드와 노드를 연결하는 연결선
• Terminal Node(Leaf Node) : 밑으로 또 다른 노드가 연결되어 있지 않은 노드
• Sub-Tree : 큰 트리에 속하는 작은 트리
• Level : 트리에서 각 층별로 매긴 숫자
• Height : 트리의 최고 레벨

Binary Search Tree(이진 트리)

이진트리는 모든 노드가 정확하게 두개의 서브트리를 가지고 있는 트리이다.

대신 서브트리는 공백이 될 수 있다.

그리고 왼쪽과 오른쪽 서브트리를 확실하게 구분한다.

이러한 이진트리는 다양한 형태가 존재한다.

1.편향 이진트리(skewed binary tree)

모든 노드가 부모의 왼쪽 자식이라 왼편으로 편향되거나, 반대로 모든 노드가 부모의 오른쪽 자식으로 되어 오른쪽으로 편향된 트리이다.

2.포화 이진트리(full binary tree)
포화 이진트리는 이진트리가 보유할 수 있는 최대의 노드를 가진 트리이다.

Height가 h인 이진 트리에서 가능한 최대 노드 수는 2의 h+1제곱 -1 이다. 즉 2이면 총 7개의 노드가 존재한다.

3.완전 이진트리(complete bunary tree)

높이가 h이고 노드 수가n 일 때 n <=(2의 h+1제곱 -1)인 이진트리에 Root Node를 1이라고 하고 그외에 모든 노드가 왼쪽에서 부터 오른쪽까지 꽉 차서 노드의 수가 n <=(2의 h+1제곱 -1)라면 완전 이진트리이다.