Binary Tree(이진트리) - 각 노드가 최대 두개의 자식을 갖는 트리
Binary Search Tree(이진 탐색 트리) - 노드 n에 대해 모든 왼쪽 자식들이 n 보다 작거나 같고 오른쪽 자식들은 n 보다 큰 속성.
균형 트리의 유형 - 레드-블랙트리, AVL 트리
완전 이진 트리 - 트리의 모든 높이에서 노드가 꽉 차 있는것
전 이진 트리 - 자식이 없거나 정확히 두 개 있는 경우
포화 이진 트리 - 전 이진 트리이면서 완전 이진 트리인 경우
순회 방식 - 중위 순회(왼쪽-현재-오른쪽), 전위 순회(현재 노드 먼저), 후위 순회(모든 자식 노드 먼저)
Graph - 노드와 간선으로 구성된 비선형 데이터 구조, 그래프는 유한한 정점 세트와 노드 쌍을 연결하는 에지 세트로 구성된다.
DFS (인접 노드 차례로 순회), BFS(큐를 사용)
연습문제
- 노드 사의이 경로 확인
- 높이가 최소가 되는 이진 탐색 트리
- 같은 깊이에 있는 노드를 연결 리스트로 연결
- 이진 트리가 균형이 잡혀져 있는지 확인
- 이진 탐색 트리 인지 확인
- 이진 탐색 트리에서 주어진 노드의 다음 노드를 찾는 알고리즘
- 두 노드의 첫번째 공통 조상을 찾는 알고리즘
- 트리를 만들어 낼 수 있는 모든 가능한 수
- 하위 트리 확인
- 임의의 노드
- 합의 경로
출처