개발새발
#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)
'알고리즘' 카테고리의 다른 글
#탐욕알고리즘 #짐나르기 #편의점알바 #자리 옮기기# 금고털기 (0) | 2022.08.03 |
---|---|
탐욕 알고리즘(Greedy) (0) | 2022.08.03 |
#의사코드 #시간복잡도 (0) | 2022.08.03 |
# 스택 #큐 (0) | 2022.08.03 |
Comments