나무
그래프의 여러 구조 중 단방향 그래프의 구조로, 한 뿌리에서 가지가 사방으로 뻗은 모양
데이터가 바로 아래에 있는 하나 이상의 데이터에 하나의 경로와 한 방향으로만 연결 계층적 데이터 구조
하나의 데이터 아래에 여러 데이터가 있을 수 있습니다.
비선형 구조
아래로만 늘어나기 때문에 사이클이 없다.
트리의 구조와 특징
루트 하나의 정점 데이터를 비롯한 여러 데이터 간선(edge)으로 연결
인기글
데이터 노드
깊이(depth)
트리 구조에서 루트에서 하위 계층의 특정 노드까지의 깊이표현
레벨(Level)
트리 구조로 같은 깊이를 가진 노드를 모아서 레벨로 표현
같은 레벨에 늘어서 있는 노드를 형제 노드(Sibling Node)
높이
트리 구조로 리프 노드를 기준으로 루트까지의 높이표현
서브트리(Sub tree)
나무 구조의 뿌리에서 뻗어있는 큰 나무의 내부에, 트리 구조와 작은 트리를 하위 트리 라고 부릅니다.
용어 정리
- 노드: 트리 구조를 구성하는 모든 개별 데이터
- 루트: 트리 구조의 시작점이 되는 노드
- 상위 노드(Parent node): 두 노드가 상하 관계로 연결될 때 상대적으로 루트에서 가까운 노드
- 자식 노드(Child node): 두 노드가 상하 관계로 연결되어 있는 경우 상대적으로 루트에서 먼 노드
- 리프 : 트리 구조의 끝점이며 자식 노드가없는 노드
바이너리 트리
자식 노드가 최대 2개의 개인 노드로 구성된 트리
바이너리 트리의 특징
- 포지티브 바이너리 트리(Full binary tree): 각 노드가 0개 또는 2개인 자식 노드
- 포화 바이너리 트리 (Perfect binary tree) : 포지티브 바이너리 트리이면서 완전 바이너리 트리 인 경우. 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 찬 트리.
- 완전 이진 트리(Complete binary tree): 마지막 레벨을 제외한 모든 노드가 가득 찼습니다.
바이너리 네비게이션 트리
먼저 루트 노드와 값 비교
왼쪽 하위 트리로 이동
트리 안에 찾고 싶은 값이 없어도, 최대 h번(트리의 높이)만의 연산 및 탐색이 진행
바이너리 네비게이션 트리의 특징
- 루트 노드의 키와 원하는 값을 비교합니다.
원하는 값의 경우 탐색을 종료합니다. - 원하는 값이 루트 노드의 키보다 작으면 왼쪽 하위 트리로 이동합니다.
- 원하는 값이 루트 노드의 키보다 크면 오른쪽의 하위 트리로 이동합니다.
전위 순회 (preorder traverse)
전위 순회에서 처음 방문하는 노드는 루트
루트 – 왼쪽 – 오른쪽
전위 1-6-4-7-9-8-10-2-3-11
중위 순회 (inorder traverse)
중위 순회는 루트를 중앙에 두고 순회
왼쪽 – 루트 – 오른쪽
중위 7-4-8-9-10-6-5-1-3-2-11
후위 순회 (postorder traverse)
후위 순회는 루트를 마지막으로 순회
왼쪽 – 오른쪽 – 루트
후위 7-8-10-9-4-5-6-3-11-2-1
레벨 순회(levelorder traverse)
레벨 순회는 루트를 방문하는 기준으로 순회를 하는 것이 아니라
트리 레벨을 기반으로 노드를 방문하는 순회 방법
순회 방식을 나누는 이유
모든 노드에 액세스하려면 특정 조건이 필요합니다.
Graph
여러 점이 서로 복잡하게 연결된 관계를 나타내는 데이터 구조
Graph의 구조
- 직접적인 관계있다면 두 점 사이를 연결하는 선
- 간접적인 관계라면은 여러 점과 선에 걸쳐 있습니다.
- 한 점을 그래프로 정점(vertex)라고 표현하고 하나의 선은 간선(edge)
알아야 할 Graph 용어
- 정점(vertex): 노드라고도 하며 데이터가 저장되는 그래프의 기본 요소입니다.
- 간선(edge): 정점 간의 관계를 나타냅니다.
(정점을 연결하는 선) - 인접 정점(adjacent vertex): 하나의 정점에서 간선으로 직접 연결된 정점을 의미합니다.
- 가중치 그래프 (weighted Graph): 연결의 강도(추가 정보, ex. 서울-부산까지의 거리 등)가 얼마나 되는지가 적혀 있는 그래프를 의미합니다.
- 비가중 그래프 (unweighted Graph): 연결 강도가 작성되지 않은 그래프를 의미합니다.
- 무(방향) 방향 그래프 (undirected graph): 앞에서 본 네비게이션의 예는 무(방향) 방향의 그래프입니다.
서울에서 부산으로 가는 것처럼 반대로 부산에서 서울로 갈 수도 있습니다.
그러나 단방향 그래프로 구현하면 서울에서 부산으로 갈 수 있지만 부산에서 서울로 가는 것은 불가능합니다 (또는 그 반대). 두 가지 포인트 일방통행 도로에 연결되어 있으면 한 방향의 간선으로 표현할 수 있습니다. - 진입 차수(in-degree) / 진출 차수(out-degree): 어느 정점에 진입( 들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇개인가를 나타냅니다.
- 인접 (adjacency): 두 정점 사이에 간선이 직접 연결되어 있는 경우 이 두 정점은 인접한 정점입니다.
- 자기 루프(self loop): 정점에서 진출하는 간선이 바로 자신에게 진입하는 경우 자기 루프를 가진 라고 표현합니다.
다른 정점을 통과하지 않는 것이 특징입니다. - 사이클(cycle): 한 정점에서 출발하여 그 정점으로 돌아갈 수 있다면 사이클이 있다라고 표현합니다.
네비게이션 그래프는 서울→대전→부산→서울로 이동 가능하므로 사이클이 존재하는 그래프입니다.