이진트리, Red-Black 트리, AVL 트리에 대한 삽입, 탐색속도의 비교 문서

소개

이진트리, Red-Black 트리, AVL 트리에 대한 삽입, 탐색속도의 비교 결과를
그래프, 표 등을 통해 보여줍니다

목차

Ⅰ. Introduction

Ⅱ. 실험환경

Ⅲ. Search algorithms 소개

Ⅳ. Results
(1) 입력 파일이 random하게 구성되어 있는 경우
1)삽입시간 비교
2)탐색시간 비교
(2) 입력 파일이 정렬되게 구성되어 있는 경우
1)삽입시간 비교
2)탐색시간 비교

V.결론

본문내용

Ⅰ. Introduction
이 보고서의 목적은 3개의 다른 Search algorithms을 비교하기 위해서이다. 여기에서 이진트리, Red-Black 트리, AVL 트리에 대한 삽입, 탐색속도의 비교 결과를 보여주려고 한다. 측정에 사용되는 개수(N)과 입력 파일은 random하게 구성되어 있는 것과 정렬되어 있는 것을 사용하여 실행시간을 측정하였다.

Ⅱ. 실험환경
Sun Microsystems Inc. SunOS 5.7 Unix, g++컴파일러

Ⅲ. Search algorithms 소개
(1)이진트리
이진트리 탐색은 주어진 자료를 이진 탐색 트리(binary search tree)로 변환하여 탐색을 수행하는 것이다. 이진 탐색 트리는 동적이며 쉽게 구현할 수 있고, 이진 탐색 트리는 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조를 가지고 있다.

(2)Red-Black 트리
Red-Black 트리는 내부적으로 균형을 이룬(self-balancing) 이진 탐색 트리(binary search tree)로써, 대표적으로는 연관 배열 등을 구현하는데 쓰이는 자료구조이다. 최초의 구조는 1972년 루돌프 바이어가 창안했으며, 이를 "대칭형 이진 B-트리"(symmetric binary B-tree)라고 불렀고, 1978년 Leo J. Guibas와 로버트 세지윅이 발표한 논문에서 현재의 이름이 등장하게 되었다. 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에 있어서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다.

(3)AVL 트리
AVL이라는 용어는 이 알고리즘을 고안한 사람들(G. M. Adelson-Velskii, E. M. Landis)의 이름을 딴 것이다. AVL 트리는 “항상 균형을 유지하는 이진 탐색 트리”다. 이를 위해 AVL 트리는 삽입, 삭제가 일어날 때마다 트리의 균형 상태를 점검하고 혹 균형이 깨지면 트리 모습을 변형함으로써 다시 균형을 복원시킨다.

참고자료

· 없음