Tree
Tree는 비선형 자료구조이자 계층구조.
- 비선형 : 일직선으로 나타내지 못하는 방식
![]()
Tree는 나무를 거꾸로 뒤집어놓은 모습을 갖고있다.
- 하나의 뿌리로부터 가지가 뻗은 형태가 나무와 비슷하다고 해서 Tree구조라고 한다.
Tree구조의 각 데이터를 Node 노드라고 하고 최상단 노드를 Root 루트라고 한다. 루트를 시작으로 여러 노드들이 간선 으로 연결되어있는데 노드가 상하계층으로 연결되면 부모/자식 관계를 갖는다.
- Node : 트리구조의 각 데이터
- Root : 최상단에 위치한 데이터(노드)
- Parent Node : 노드가 상하계층으로 연결됐을때 위에 위치한 노드
- Child Node : 노드가 상하계층으로 연결됐을때 아래 위치한 노드
- Leaf Node : 자식이 없는 노드
Tree 구조는 높이, 레벨 등을 측정할 수 있다.
- depth(깊이) : 루트로부터 하위계층의 특정 노드까지의 깊이 표현 가능.
- Level(레벨) : 같은 깊이를 갖고있는 노드를 묶어서 레벨이라고 칭함.
- Height(높이) : 리프노드를 기준으로 루트까지의 높이.
- 서브트리 : 큰 트리 내부에 트리구조를 갖춘 작은 트리를 서브트리라고 함
- Degree(차수) : 어떤 노드가 갖고있는 자식노드의 개수
Tree구조의 실사용 예시
- 파일 시스템 / 월드컵 토너먼트 대진표 / 가계도 / 조직도 등
이진트리
이진트리는 공집합이거나 루트, 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한 집합이다.
이진트리 성질
- n개의 노드를 가진 이진트리는 n-1개의 간선을 갖는다.
- 부모와 자식간에는 하나의 간선만 가진다.
- 높이가 h인 이진트리는 최소 h개의 노드를 갖고, 최대 2h-1개의 노드를 가진다.
- n개의 노드를 가지면 높이는 최대 n이거나 최소 log(n + 1) 이 된다.
이진트리 종류
- 포화이진트리 : 각 레벨의 노드가 꽉차있는 노드
- 완전이진트리 : 높이가 x일때 1레벨부터 k-1레벨까지의 노드는 모두 채워져있고 x레벨부터는 왼쪽부터 오른쪽으로 순서대로 노드가 채워진다. 마지막 레벨의 노드는 꽉 차있지 않아도 되지만, 중간에 비어있으면 안된다.
Graph
Graph는 여러개의 점들이 서로 연결되어있는 관계를 표현.
- 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있음.
- 간접적인 관계라면 점과 선에 걸쳐짐
- 하나의 점을 정점(vertex), 하나의 선은 간선(edge)
Graph의 표현방식
- 인접행렬 : 두 정점을 바로 이어주는 간선이 있을때 인접하다고 함.
- 두 정점 사이에 관계가 있는지 확인하기에 용이
- 가장 빠른 경로를 찾는데 주로 사용.
- 인접 리스트 : 각 정점이 어떤 정점과 인접한지 리스트의 형태로 표현.
- 인접리스트를 구현할 때 정점별로 살펴봐야할 우선순위를 고려해야함.
- 우선순위가 없다면 정점들을 단순하게 나열.
- 메모리를 효율적으로 사용하고싶을때 사용
Graph의 실사용 예제
포털사이트의 검색엔진 / SNS의 사람관계 / 네비게이션 등
비가중치 그래프 : 가중치(연결강도)가 적혀있지 않은 그래프
Graph 용어
정점 (vertex) : 노드라고도 하며 데이터가 저장되는 그래프의 기본원소
간선 (edge) : 정점간의 관계 (정점을 이어주는 선)
인접정점 (adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결된 정점
가중치 그래프 (weighted Graph) : 연결강도가 적혀있는 그래프
비가중치 그래프 (unweighted Graph) : 연결강도가 적혀있지않은 그래프
무방향 그래프 (undirected Graph) : 왕복가능, 단방향 그래프는 일방통행
진입차수(in-degree) / 진출차수(out-degree) : 한 정점에 들어오고 나가는 간선이 몇개인지
인접 (adjacency) : 간선이 직접 연결
자기루프 (self Loop) : 정점에서 진출하는 간선이 바로 자신에게 진입하는 경우
사이클 (cycle) : 한 정점에서 출발하여 다시 해당정점으로 돌아갈 수 있는 경우
Binary Search Tree
트리구조를 효율적인 탐색을 위해 발전시켜 만든 여러 트리구조중 자주 쓰이는 이진트리와 이진탐색트리
- 이진트리(Binary Tree) : 자식노드가 최대 두개인 노드로 구성된 트리
- 이진탐색트리(Binary Search Tree) : 모든 왼쪽 자식의 값이 루트나 부모의 값보다 작고, 모든 오른쪽 자식의 값이 루트나 부모의 값보다 큰 특징.