너비 우선 탐색 기반 비재귀 트리 탐색 알고리즘의 효율적 구현과 성능 비교

• 영문명: Efficient Non-Recursive Tree Traversal Algorithm: Implementation Based on Breadth First Search and Performance Comparison
• 발행기관: 한국과학영재교육학회
• 저자명: 이주형(Juhyeong Lee) 정상수(Sangsu Jeong)
• 간행물 정보: 『과학영재교육』제15권 제3호, 494~503쪽, 전체 10쪽
• 주제분류: 사회과학 > 교육학
• 파일형태: PDF
• 발행일자: 2023.12.31

국문 초록

본 연구의 목표는 실행 시간과 구현 복잡도 측면에서 효율적인 트리 순회 알고리즘을 제시하는 것이다. 트리는 사이클이 없는 연결 그래프의 한 형태로 컴퓨터 과학의 여러 분야에서 활용된다. 본 연구에서는, 기존의 재귀 함수나 깊이 우선 탐색을 이용한 구현이 아닌 너비 우선 탐색을 기반으로 한 구현 방법을 제시한다. 비재귀적인 방법을 사용하여 실행 시간을 개선하였고, 일차원 배열과 반복문만을 사용하여 구현 난도를 낮추었다. 또한 전처리 과정을 통해 알고리즘을 최적화하였다. 제안된 알고리즘과 기존 알고리즘의 성능 평가는 무작위 구조의 트리를 생성하고 실행 시간을 측정하였다. 측정 결과 제안한 알고리즘이 우수한 성능을 보였다.

영문 초록

The objective of this study is to present an efficient tree traversal algorithm in terms of execution time and implementation complexity. Trees, defined as acyclic connected graphs, are widely used in various fields of computer science. Unlike traditional recursive methods or depth first search implementations, this research proposes an implementation based on breadth first search. The algorithm improves execution time using a non-recursive approach and reduces implementation complexity by using only one-dimensional arrays and loops. Additionally, the algorithm has been optimized through a preprocessing phase. To evaluate the performance of the proposed algorithm compared to existing ones, trees with random structures were generated and their execution times were measured. The results demonstrated that the proposed algorithm exhibits efficient performance.

목차

Ⅰ. 연구의 필요성 및 목적

Ⅱ. 이론적 배경

Ⅲ. 연구 방법

Ⅳ. 연구 결과

Ⅴ. 결론 및 제언

참고문헌

키워드

트리 그래프 이론 자료 구조 재귀 너비 우선 탐색 tree graph theory data structure recursion breadth first search