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) : 모든 왼쪽 자식의 값이 루트나 부모의 값보다 작고, 모든 오른쪽 자식의 값이 루트나 부모의 값보다 큰 특징.