트리
각 노드들이 나무처럼 계층 구조를 가진 자료 구조. 상위 노드를 부모, 하위 노드를 자식, 동일 계층의 노드를 형제라고 부른다.
이진 트리 (Binary Tree)
트리 구조 중에서 자식 노드를 최대 2개까지만 갖는 경우를 이진트리라고 한다.
이진 검색 트리 (Binary Search Tree)
이진 검색 트리는 이진 트리 중에서 값의 배치를 일정한 규칙에 의거하여 배치한 이진 트리를 의미하는데, 임의의 노드의 왼쪽 자식은 해당 노드 보다 작은 값을 가지며, 오른쪽 자식은 해당 노드보다 큰 값을 갖는다.
이렇게 구성된 트리는 특정 값을 찾을 때 현재 노드의 값보다 큰지, 작은지에 따라 어느쪽 노드를 찾을지를 빠르게 결정 할 수 있다.
힙 (Heap)
힙은 이진 트리 중에서 부모와 자식 간에 대소 관계가 성립하는 트리를 말하는데 –형제 간의 대소 관계는 없다– 부모가 자식보다 큰 값을 가질 때 ‘최대 힙’, 부모가 자식보다 작은 값을 가질 때 ‘최소 힙’이라고 부른다.
해시 테이블
키(key)-값(value)으로 구성된 자료구조. 해시 맵이라고도 한다. 저장된 자료와의 비교를 통해 자료를 찾지 않고, 해시 함수를 통해 만들어진 키 값을 이용하여 원하는 값을 단 한 번에 찾을 수 있는 자료구조이다.
그래프
각 노드(Node)들과 노드들을 잇는 선(Edge)로 이루어진 집합. 노드와 노드를 잇는 선에 방향이 없는 그래프를 무향 그래프, 있는 그래프를 유향 그래프라고 한다.
노드와 노드를 잇는 선에 가중치가 존재할 수도 있고 없을 수도 있다.
행렬을 이용한 그래프 표현
노드와 노드의 관계는 행렬을 이용해서 표현할 수 있다. 행렬상의 0은 노드간의 연결이 없음을 의미하며, 1이상의 숫자가 있으면 노드간에 연결이 있음을 뜻한다.
리스트를 이용한 그래프 표현
노드와 노드의 관계는 리스트를 이용해서도 표현할 수 있다.
