오픈소스인 C++ STL(Standard Template Library)의 set을 AVL Tree를 이용하여 구현한 프로젝트입니다.
과목: CSE3210 - 오픈소스 응용 프로그래밍
팀명: INHA_OSAP_003_2
팀원: 정예원, 박수현, 임수범, 세라
기간: 2025년 9월 ~ 12월
INHA_OSAP_003_2/
├── .clang-format # 코드 포맷 설정
├── CMakeLists.txt # CMake 빌드 설정
├── LICENSE # GPL v3.0 라이선스
├── README.md # 프로젝트 설명서 (이 파일)
├── src/
│ ├── node.h # Node 구조체 정의
│ ├── avl_tree.h # AvlTree 클래스 선언
│ ├── avl_tree.cpp # AvlTree 클래스 구현 (520줄)
│ └── main.cpp # 메인 프로그램
└── tests/
└── avl_tree_test.cpp # Google Test 테스트 코드 (29개)
- Empty: 트리가 비어있는지 확인 - O(1)
- Size: 트리에 저장된 노드 개수 - O(1)
- Insert K: 키 K를 삽입 - O(log n)
- Find K: 키 K 검색 - O(log n)
- Prev K: K보다 작은 원소 중 가장 큰 값 - O(log n)
- Next K: K보다 큰 원소 중 가장 작은 값 - O(log n)
- UpperBound K: K보다 큰 원소 중 가장 작은 값 - O(log n)
- Rank K: K의 순위 계산 (K보다 작은 원소 수 + 1) - O(log n)
- Erase K: K 삭제 - O(log n)
- 언어: C++ (C++17)
- 빌드 시스템: CMake 3.14+
- 컴파일러: GCC 7.5.0+
- 테스트 프레임워크: Google Test 1.12.1
- 버전 관리: Git & GitHub
- 코드 포맷: clang-format
- AVL Tree: 자가 균형 이진 탐색 트리
- 리밸런싱: LL, RR, LR, RL 4가지 회전
- 부모 포인터: 양방향 탐색 지원
- Size 필드: O(log n) Rank 연산 지원
sudo apt-get update
sudo apt-get install cmake g++ libgtest-devbrew install cmake googletest# 1. 프로젝트 클론
git clone https://github.com/[팀-레포지토리]/INHA_OSAP_003_2.git
cd INHA_OSAP_003_2
# 2. 빌드 디렉토리 생성
mkdir build && cd build
# 3. CMake 설정 및 빌드
cmake ..
make
# 4. 테스트 실행
./avl_testmkdir build && cd build && cmake .. && make && ./avl_testcd build
./avl_test[==========] Running 29 tests from 4 test suites.
[----------] 15 tests from AvlTreeTest
[ RUN ] AvlTreeTest.Constructor
[ OK ] AvlTreeTest.Constructor
...
[ PASSED ] 29 tests.
- Fixture 테스트 (15개): 모든 public 함수 테스트
- Value-Parameterized 테스트 (14개): 여러 값으로 자동 반복 테스트
- InsertParamTest: 9개 값으로 삽입 테스트
- EraseParamTest: 5개 값으로 삭제 테스트
# Insert 관련만
./avl_test --gtest_filter=*Insert*
# Rank 관련만
./avl_test --gtest_filter=*Rank*// 4가지 회전 케이스 완벽 구현
- LL (Left-Left): Single Right Rotation
- RR (Right-Right): Single Left Rotation
- LR (Left-Right): Double Rotation
- RL (Right-Left): Double Rotation// Node에 size 필드 추가하여 효율적인 순위 계산
struct Node {
int size; // 서브트리 크기
};
// 조상을 따라 올라가며 O(log n)에 순위 계산// 부모-자식 포인터를 항상 양방향으로 유지
struct Node {
Node *parent; // 부모 포인터
Node *left; // 왼쪽 자식
Node *right; // 오른쪽 자식
};| 연산 | 시간 복잡도 | 공간 복잡도 | 비고 |
|---|---|---|---|
| Empty | O(1) | O(1) | count_ 변수 확인 |
| Size | O(1) | O(1) | count_ 변수 반환 |
| Insert | O(log n) | O(1) | 리밸런싱 포함 |
| Find | O(log n) | O(1) | BST 탐색 |
| Prev/Next | O(log n) | O(1) | 전임자/후임자 |
| UpperBound | O(log n) | O(1) | BST 탐색 |
| Rank | O(log n) | O(1) | size 필드 활용 |
| Erase | O(log n) | O(1) | 리밸런싱 포함 |
- 기준: CSE3210 C++ 스타일 가이드 준수
- 포맷 도구: clang-format 사용
- 주석: 각 함수 및 복잡한 로직에 설명 추가
- 라이선스: 모든 파일 상단에 GPL v3.0 명시
// 클래스: PascalCase
class AvlTree { ... };
// 함수: PascalCase
void Insert(const int key);
// 변수: snake_case with trailing underscore
Node *root_;
int count_;
// 파라미터: snake_case
void Rebalancing(Node *current_node);이 프로젝트는 GNU General Public License v3.0 라이선스 하에 배포됩니다.
Copyright (c) 2025 정예원, 박수현, 임수범, 세라
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
자세한 내용은 LICENSE 파일을 참조하세요.
| 이름 | 역할 | 담당 업무 |
|---|---|---|
| 정예원 | 팀장 | 프로젝트 총괄, AVL 리밸런싱 구현, 테스트 설계 |
| 박수현 | 개발자 | 기본 기능 구현, 코드 리뷰 |
| 임수범 | 개발자 | 고급 기능 구현, 디버깅 |
| 세라 | 개발자 | 테스트 코드 작성, 문서화 |
- Git: Fork & Pull Request 방식
- GitHub: Private Repository
- 코드 리뷰: 모든 PR에 최소 1명 이상 리뷰어 지정
- 9월 23일: 과제 공지
- 11월 18~12월 2일: 중간 발표
- 12월 19일: 최종 제출
- 모든 기본 기능 구현 및 테스트 통과
- 모든 고급 기능 구현 및 테스트 통과
- Google Test 29개 모두 통과
- 스타일 가이드 준수
- 라이선스 및 작성자 명시
- Fork & Pull Request 과정 문서화
- README.md 작성
- 중간 발표 완료
- 최종 보고서 작성
프로젝트에 대한 문의사항이 있으시면 다음으로 연락 주세요:
- 팀장: 정예원 (12223815@inha.edu)
- GitHub: https://github.com/aeongiing/INHA_OSAP_003_2
이 프로젝트를 통해 다음을 학습했습니다:
- 자료구조: AVL Tree의 완전한 구현
- 알고리즘: 4가지 회전, O(log n) 순위 계산
- 소프트웨어 공학: Git/GitHub를 활용한 협업
- 테스트: Google Test를 이용한 TDD
- 빌드 시스템: CMake 활용
- 오픈소스: 라이선스 이해 및 적용
Copyright © 2025 Yewon Jeong. All rights reserved.