자료구조/알고리즘 - Tree, Graph, Binary

1-3.트리(Tree)
 -그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
 -데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조
 -데이터를 순차적으로 나열시킨 선형 구조가 아닌, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조

트리 구조

 -Tree의 구조와 특징
 (1)루트(Root) : 하나의 꼭짓점 데이터
 (2)간선(Edge) : 여러 개의 데이터를 연결하는 선
 (3)노드(Node) : 각 데이터를 지칭하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가짐
  *부모 노드(Parent Node), 자식 노드(Child Node), 리프 노드(Leaf Node : 자식이 없는 노드)
 (4)깊이(Depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현하고, 루트 노드부터 0으로 시작함
 (5)레벨(Level) : 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현하고, 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node) 라고 부름
 (6)높이(Height) : 리프 노드를 기준으로 루트까지의 높이(height)를 표현하고, 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가짐
 (7)서브 트리(Sub tree) :  root에서 뻗어 나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리


1-4.그래프(Graph)
 -여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
 -직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있고, 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어짐

정점 A, B, C와 2개의 단방향 간선, 그리고 하나의 양방향 간선이 있는 그래프

 -Graph용어
 (1)정점(Vertex) : 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
 (2)간선(Edge) : 정점 간의 관계를 나타내는(정점을 이어주는) 선
 (3)인접(Adjacency) : 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점을 인접해 있다고 표현함
 (4)인접 정점(Adjacent Vertex) : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 의미
 (5)가중치 그래프(Weighted Graph) : 연결의 강도(추가적인 정보)가 얼마나 되는지 적혀져 있는 그래프
 (6)비가중치 그래프(Unweighted Graph) : 연결의 강도가 적혀져 있지 않는 그래프
 (7)무(방)향 그래프(Undirected graph) : 정점간의 방향이 없어 어떤 방향으로든 옮겨 다닐 수 있는 그래프 <-> 단방향 그래프(Directed Graph)
  *만약 왼쪽 정점에서 오른쪽 정점으로만 접근할 수 있는 경우, 방향성이 있다고 표현함
 (8)진입차수(In-Degree)/진출차수(Out-Degree) : 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냄
 (9)자기 루프(Self Loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 '자기 루프를 가졌다'라고 표현함
 (10)사이클(Cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현함

 -Graph의 표현 방식
 (1)인접 행렬
  -인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타냄
   *두 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)
  -인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이하며, 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용됨

 (2)인접 리스트
  -각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현
  -각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있음
  -메모리를 효율적으로 사용하고 싶을 때 사용함(인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 인접 리스트보다 상대적으로 메모리를 많이 차지)


1-5.이진 탐색 트리(Binary Search Tree)
 -트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해서도 사용함
 -트리 구조는 가지고 있는 특징에 따라 여러 가지 이름으로 불리고, 가장 간단하고 많이 사용하는 이진트리와 이진탐색트리를 알아볼 예정

이진 트리의 종류에 따른 특징

 (1)이진 트리(Binary Tree) : 자식 노드가 최대 두 개(왼쪽 자식 노드와 오른쪽 자식 노드)인 노드들로 구성된 트리
 (2)이진 탐색 트리(Binary Search Tree) : 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 이진 트리

 

 

 

 

이미지 및 내용 출처 - code states