C언어로 쉽게 풀어쓴 자료구조 연습문제 6장 4, 5, 6, 7 7장 1, 3, 8장 10, 11 9장 9, 10 10장 6, 13, 15 11장 2, 6, 7, 10 12장 5, 6, 12 13장 5-(1)(2), 6-(1)(2)

소개

"C언어로 쉽게 풀어쓴 자료구조 연습문제 6장 4, 5, 6, 7 7장 1, 3, 8장 10, 11 9장 9, 10 10장 6, 13, 15 11장 2, 6, 7, 10 12장 5, 6, 12 13장 5-(1)(2), 6-(1)(2)"에 대한 내용입니다.

목차

없음

본문내용

Chapter 13_05
문제 : 데이터 ( 60, 50, 20, 80, 90, 70, 55, 10, 40, 30 ) 를 차례대로 삽입하면서 다음과 같은 균형 트리를 구축하는 과정을 그림으로 설명하고 이들 3가지의 트리를 사용한 결과를 서로 비교하라
(a) 이진 탐색 트리
정답 및 풀이 : 이진 탐색 트리의 경우 왼쪽 서브 트리가 ROOT 노드 보다 작고 오른쪽 서브 트리가 ROOT 노드 보다 크게 구성되기 때문에 ( 60, 50, 20, 80, 90, 70, 55, 10, 40, 30 ) 데이터가 차례대로 삽입 되었을 경우 해당 그림과 같이 구성된다.

(b) AVL 트리
정답 및 풀이 : AVL트리는 모든 노드의 균형 인수가 1이거나 0이어야 한다. 즉 2를 넘지 않아야 하며, 2가넘을 경우 회전을 통해 균형 트리로 만들어야 한다. ( 60, 50, 20, 80, 90, 70, 55, 10, 40, 30 ) 데이터가 차례대로 삽입 되었을 경우 해당 그림과 같이 구성된다.

Chapter 13_06
문제 : 데이터 ( 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 ) 를 차례대로 삽입 했을 때의 결과 트리를 그려라.
어떤 트리가 탐색을 가장 효율적으로 수행하는가?
(a) 이진 탐색 트리
정답 및 풀이 : 이진 탐색 트리의 경우 왼쪽 서브 트리가 ROOT 노드 보다 작고 오른쪽 서브 트리가 ROOT 노드 보다 크게 구성되기 때문에 ( 60, 50, 20, 80, 90, 70, 55, 10, 40, 30 ) 데이터가 차례대로 삽입 되었을 경우 해당 그림과 같이 구성된다.

(b) AVL 트리
정답 및 풀이 : AVL트리는 모든 노드의 균형 인수가 1이거나 0이어야 한다. 즉 2를 넘지 않아야 하며, 2가넘을 경우 회전을 통해 균형 트리로 만들어야 한다. ( 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 ) 데이터가 차례대로 삽입 되었을 경우 해당 그림과 같이 구성된다.

참고자료

· 없음