Tree, Graph, Hash Table, Binary Search Tree 란?

*Tree

: 구조가 나무의 뿌리 같이 생긴 구조

: 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프

: 부모노드에서 자식노드로 갈 수 있지만 자식 노드는 부모노드로 불가능

(위에서 아래는 가능, 아래에서 위로는 불가능)

: 회사 조직도와 비슷함

출처: https://spaghetti-code.tistory.com/23

- property

: 루트 노드(최상위 노드)

: 단말 노드(노드가 연결되지 않은 노드 - 자식 노드가 없음)

: 내부 노드(단말 노드를 제외한 모든 노드)

: 일반 트리(자신의 자식 노드의 수가 제한이 없음)

: 이진 트리(자신의 자식 노드의 수를 최대 2개로 제한)

​

*Graph

: 노드들이 선으로 연결되어 삼각형의 형태를 띄고 있는 자료구조

: tree 구조와는 다르게 노드가 하나 이상의 in-degree, out-degree를 가짐

: 어떤 규칙성 없이 필요할 때마다 연결하여 사용

: 전기회로, 놀이동산의 놀이기구 표시, 지하철 노선도 등과 같음

: 망구조와 같이 자료와 자료들 사이의 구조가 복잡한 경우에 사용

출처: https://stackoverflow.com/questions/20556802/determining-whether-or-not-a-directed-or-undirected-graph-is-a-tree

- directed graph

: degree가 방향성을 가지고 있음

: 2번의 B는 1개의 in-degree, 1개의 out-degree를 가짐

​

- undirected graph

: degree가 방향성이 없음

: 5번의 B는 degree가 2개라고 표현

​

*Hash table

: 여러 개의 통에 번호를 붙인 뒤, 키 값을 이용해 데이터가 들어갈 통 번호를 계산

(즉, 키를 해시 알고리즘으로 해시해 배열의 위치를 계산하고 값을 그 위치에 저장하는 자료 구조 )

: 다음에 접근 할 때 키 값을 이용하여 바로 접근가능

: 키 값이 겹치지 않게 회피 알고리즘도 고려해야 함

: 스마트폰의 연락처 정렬과 비슷

출처: https://www.wisdomjobs.com/e-university/data-structure-algorithms-tutorial-1541/data-structure-algorithms-hash-table-18004.html

 

: put, get method를 이용, 두 가지 파라미터(키 값, 데이터 값)

​

* Binary Search Tree(이진 탐색 트리)

: 이진트리를 노드의 데이터 크기에 따라서 노드의 위치를 재배치한 트리

: 이진트리와는 다르게 규칙이 존재(따르지 않으면 이진 트리)

- 규칙

1)루트 노드의 왼쪽 자식 노드가 있을 경우 왼쪽 자식 노드가 루트 노드보다 작다

2) 루트 노드의 오른쪽 자식 노드가 있을 경우 오른쪽 자식 노드가 루트 노드보다 크다.

3) 값이 중복된 노드가 없어야 한다.

4) 해당 노드의 하위 노드도 이진 탐색 트리다.

​

-탐색 과정

1) 루트 노드와 찾고자 하는 값 비교

2) 같은 경우 그대로 리턴, 다를 경우 루트 노드와 비교

3) 루트 노드보다 작으면 왼쪽 자식 노드를 탐색, 크면 오른쪽 자식 노드를 탐색

4) 찾고자 하는 값을 찾을 때까지 1, 2, 3을 반복

출처: https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC

 

​