※ '엔지니어대한민국' 유튜브 채널을 통해 공부하였습니다.
* 트리란?
먼저 트리란, 부모 자식 관계를 가지는 구조이다. 계층, 그룹 개념이 가능하다.
(배열, 연결리스트, 스택, 큐 자료구조는 일직선 상의 구조이다.)
* 트리의 종류
- 이진트리(binary tree) : 자식노드가 최대 2개까지만 붙는 구조.
- 이진검색트리(binary search tree) : 현재 위치 노드의 왼쪽과 아래 노드는 현재 노드값보다 작아야 하고, 현재 위치 노드의 오른쪽과 위 노드는 현재 노드값보다 커야 하는 구조.
-- 대표 balanced tree : red-black tree, AVL tree
- 완전이진트리(complete binary tree) : 층(level)마다 왼쪽부터 채워진 구조.
- Full Binary Tree : 이진트리에서 자식노드가 2개이거나 0개인 구조. 1개의 자식노드가 존재하지 않는 구조.
- Perfect Binary Tree : 이진트리에서 모든 노드가 2개의 자식을 가지는 구조.
* 이진 트리 3가지 순회방법
* 힙이란? 최솟값이나 최댓값을 찾아내는 연산을 빠르게 하기 위해 고안된 '완전이진트리'를 기본으로 한 자료구조.
- 최소힙과 최대힙으로 구분.
* Trie(트라이) 트리
* 그래프란?
트리는 그래프의 한 종류 (사이클이 없고 아래로 향하는 방향(Dirested) 그래프 = 트리)
*그래프의 특성
* 그래프검색(Graph Search)
- DFS : stack 이용하여 구현. DFS 구현 시 재귀 호출을 이용하면 코드가 간결해진다.
(inorder, preorder, postorder 순회방법이 DFS에 속한다.)
- BFS : queue 이용하여 구현
* 주어진 트리가 이진 검색트리인지 확인하는 알고리즘
: inorder 방식으로 순회하면 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 와 같이 이진검색트리를 ascending order된 배열로 구할 수 있다.
'자료구조' 카테고리의 다른 글
| lower bound, upper bound (0) | 2020.01.30 |
|---|
