#Tree #Graph # BST

Tree & Graph & Binary Search Tree

Tree

• 나무 뒤집어놓은 형태를 가지고 있는 자료구조
• 단방향 그래프
• 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조
• 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조

• 루트(root) : 가장 위 꼭지점
• 간선(edge) : 노드간을 연결하는 선
• 노드(node) : 각 데이터
• 리프 노드(leaf node) : 자식이 없는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드

• 두개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다
• 깊이(depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이
• 레벨(level) : 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현
• 높이(height) : 리프 노드를 기준으로 루트까지의 높이
• 서브 트리(sub tree) : root에서 뻗어 나오는 큰 크리의 내부에, 트리 구조를 갖춘 작은 트리
• 노드의 차수(degree) 는 어떤 노드가 가지고 있는 자식 노드의 개수이다.
• • A의 경우 차수는 3 , C의 경우 차수는 1이다.
• • 단말노드는 차수가 0, 즉 자식이 없는 노드이다.
• 트리의 차수 는 트리가 가지고 있는 노드의 차수 중에서 가장 큰 값이다.
  

Graph

• 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있음
• 간접적인 관계라면 몇 개의 점과 선에 걸쳐있음
• 그래프에서 하나의 점을 정점(vertex) // 선은 간선(edge)
  

  

• 인접 행렬 : 서로 선으로 연결되면 1(true) // 연결되지 않으면 0(false)라고 표현
• 인접 리스트 : 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현

• 각 정점마다 리스트를 가짐
• 자신과 인점한 다른 정점을 담고 있다
• 순서는 보통 중요하지 않다 // 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제 가능

• 

• 인접(adjacent): 그래프의 두 정점이 연결되어 간선이 있을 때, 두 정점을 인접되어 있다고 함
• 부속(incident): 두 정점이 인접되어 있을 때, 간선은 두 정점에 부속되어 있다고 함
• 차수(degree): 정점에 부속되어 있는 간선의 수
• 경로(path): 간선을 따라갈 수 있는 길
• 경로 길이(path length): 경로를 구성하는 간선의 수
• 단순 경로(simple path): 모두 다른 정점으로 구성된 경로
• 사이클(cycle): 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로
• DAG(Directed Acyclic Graph): 방향 그래프이면서 사이클이 없는 그래프

Binary Search Tree

• 자식 노드가 최대 두개인 노드들로 구성된 트리
• 두 개의 자식 노드는 왼쪽//오른쪽 자식 노드로 나눌 수 있다
• 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값은 루트나 부모보다 크다
• 균형잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있다

• 삽입, 삭제 방법에 따라

• 정 이진 트리(Full binary tree)
• 완전 이진 트리(Complete binary tree)
• 포화 이진 트리(Perfect binary tree)