[Tree]
단방향 그래프. 계층적 자료구조. 비선형 구조 (하나의 데이터 아래 여러개 데이터 존재)
노드 (데이터)
루트 (꼭짓점. 트리 구조의 시작점)
노드 상하 계층으로 연결시 부모/ 자식 관계
부모 노드 : 두 노드 상하관계로 연결시 상대적으로 루트에서 가까운 노드
자식 노드 : 두 노드가 상하관계로 연결시 상대적으로 루트에서 먼 노드
리프 : 트리 구조의 끝 지점. 자식 노드가 없는 노드
깊이(루트는 0 이하 1씩 증가)
레벨 (같은 깊이 노드 묶은 것)
높이 (리프 노드 기준으로 루트까지의 높이. height 최대값 + 1)
서브 트리
ex. 컴퓨터 디렉토리 (루트 폴더 / 에서 시작), 가계도, 월드컵 토너먼트 대진표 등
[Graph]
여러 점이 서로 복잡하게 연결되어 있는 관계
네트워크망
직접적인 관계 있는 경우 두 점 사이 연결해주는 선 존재
간접적인 관계 몇 개의 점과 선에 걸쳐 이어짐
정점 (vertex) : 하나의 점 (= 노드)
간선 (edge) : 하나의 선
인접 행렬 : 두 정점 바로 이어주는 간선 존재. 2차원 배열 형태로 나타남. 가장 빠른 경로 찾을 때. 메모리 효율적으로 사용할 때
비가중치 그래프 : 추가적인 정보 파악할 수 없는 그래프. (갈 수 있다 없다만 존재)
가중치 그래프 : 연결의 강도 (추가적인 정보, 거리 등) 적혀있는 그래프
무(방)향 그래프 : 양방향 가능 (↔︎ 단방향. 일방통행)
진입차수, 진출차수 : 한 정점에 진입, 진출하는 간선이 몇 개인지
인접 : 두 정점간 간선이 직접 이어져 있는 경우
자기루프 : 정점에서 출발하는 간선이 곧바로 자기 자신에게 진입하는 경우
사이클 : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있는 경우
[Binary Search Tree] BST
효율적인 탐색 위해
이진 트리 : 자식 노드가 최대 두 개인 노드로 구성된 트리 ( 정 이진트리, 포화 이진 트리, 완전 이진 트리)
정 이진 트리 : 각 노드가 0 또는 2개의 자식 노드 가짐
포화 이진 트리 : 정 이진 트리이고 완전 이전 트리인 경우. 모든 리프 노드 레벨 동일하고 모든 레벨 가득 채워짐
완전 이진 트리 : 마지막 레벨 제외한 모든 노드가 가득 차있어야
이진 탐색 트리 : 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식 값은 루트나 부모보다 큰 값을 가진다
