데이터 처리중입니다. 잠시만 기다려 주세요... AI_Developer

[C언어로 쉽게 풀어쓴 자료구조] 8장 트리

8.1 트리의 개념노드(node) : 트리의 구성요소루트(root) : 부모가 없는 노드 서브트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리단말노드(terminal node) : 자식이 없는 노드비단말노드 : 적어도 하나의 자식을 가지는 노드레벨(level) : 트리의 각층의 번호높이(height) : 트리의 최대 레벨차수(degree) : 노드가 가지고 있는 자식 노드의 개수8.2 이진 트리 소개이진트리의 정의모든 노드가 2개의 서브 트리를 가지고 있는 트리서브트리는 공집합 일 수 있따.이진트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수가 2이하이진트리의 성질n개의 노드를 가진 이진트리 n-1의 간선을 가짐높이가 h인 이진트리의 경우 최소 h개의..

[C언어로 쉽게 풀어쓴 자료구조] 9장 우선순위 큐 문제 풀이

01. 히프 트리에서 노드가 삭제되는 위치는 어디 인가?→ (1) 루트 02. 히프를 배열로 표현할 수 있는 이유는 무엇인가?→ (1) 완전 이진 트리이기 때문에 03. 히프 연산 중에서 하나의 노드가 삽입되거나 삭제되는 시간은 무엇에 비례하는가?→ (2) 트리의 높이  04. 다음 중 히프 정렬이 특히 유용하게 사용될 수 있는 경우는?→ (1) 데이터 100개 중에서 오름차순으로 20개만 뽑고자 할때 05. 최소 히프에서 가장 작은 데이터가 있는 노드는?→ (2) 첫 번째 노드(루트 노드)  06. 최소 히프에서 2번쨰로 작은 데이터가 있는 노드는?→ 2번 노드와 3번 노드 중 더 작은 값을 가지고 있는 노드 07. 10개의 데이터를 저장하고 있는 히프트리의 높이는?→ log2 10 = 4 08.참고 ..

[C언어로 쉽게 풀어쓴 자료구조] 9장 우선순위 큐

9.1 우선순위 큐 추상 데이터 타입자료구조삭제되는 요소스택가장 최근에 들어온 데이터큐 가장 먼저 들어온 데이터우선순위 큐가장 우선순위가 높은 데이터 우선순위 큐는 배열, 연결 리스트 등의 여러가지 방법으로 구현이 가능한데, 가장 효율적인 구조는 히프 heap 9.2 우선순위 큐의 구현 방법배열을 사용하는 방법*정렬이 되어 있지 않는 경우- 삽입: 배열의 맨 끝에 새로운 요소 추가 ( 시간 복잡도 : O(1) ) - 삭제: 가장 우선 순위가 높은 요소 찾기 (정렬이 안 되어 있으므로 처음부터 끝까지 모든 요소들을 스캔해야함) ( 시간 복잡도 : O(n) )             → 요소가 삭제된 다음, 뒤에 있는 요소들을 앞으로 이동   *정렬이 되어 있는 경우- 삽입: 다른 요소와 값을 비교하여 적절한..