이진 탐색 트리 규칙 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼 각각의 서브 트리도 이진 탐색 트리를 유지 중복된 키를 허용하지 않음 특징 이진 탐색 트리 규칙에 의해 데이터가 정렬됨 이진 트리에 비해 탐색이 빠름
노드의 링크로 구성된 자료구조 (그래프의 일종, Cycle 없음)계층적 구조를 나타낼 때 사용 \- 폴더 구조(디렉토리, 서브 디렉토리) \- 조직도, 가계도 노드(Node): 트리 구조의 자료 값을 담고 있는 단위에지(Edge): 노드 간의 연결선 (=link,
모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리이진 탐색 트리에 삽입되는 순서에 따라 편향이 발생할 수 있다.예시 1) 삽입 순서: 20 -> 10 -> 30 -> 5 2) 삽입 순서: 5 -> 10 -> 20 -> 30 (편항 발생) 이런 편
정점과 간선으로 이루어진 자료구조 (Cyclic) \- 연결된 정점간의 관계를 표현할 수 있는 자료구조용도: 지하철 노선도, 통신 네트워크...정점(Vertex): 각 노드간선(Edge): 노드와 노드를 연결하는 선 (link, branch)인접 정점(Adjacent
완전 이진 트리 형태마지막 레벨을 제외하고 모든 노드가 채워져 있는 것마지막 레벨은 좌측부터 채워져야 함중복 값 허용반 정렬 상태형제 노드간의 크기 우선 순위는 없음최소값 또는 최대값을 빠르게 찾아내는데 유용한 자료구조최소힙, 최대힙부모 노드의 키가 자식 노드의 키보다
우선순위가 높은 데이터가 먼저나옴. FIFO가 아님우선 순위가 같은 경우는 FIFO우선순위 큐를 힙으로 구성하면, 최소 힙 및 최대 힙의 삽입 삭제와 같음1) 배열2) 연결리스트 \- 추가할 때 링크로 끼워넣으면 되지만, 전체와 하나하나 비교해야하는 상황도 생기기때문에
문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조정렬된 트리 구조문자열 저장을 위한 메모리가 필요하지만 탐색이 빠름길이가 N인 문자열 탐색의 시간 복잡도: O(N)문자열 개수가 M일때, 생성 복잡도: O(M\*N) \- 하지만 한번 생성해놓으면 빠르게 탐색