[자료구조]BST(Binary Search Tree) 설계

소개글

자료구조 중 하나인 Binary Search Tree에 대한 설계 레포트입니다.

목차

1. Instruction
1.1 overall descriptioin
1.2 requirements
1.3 sample input/output

2. Overall System Class Design
2.1 Relationships between classes
2.2 Present class ADTs

3. Data Structure Diagram
3.1 Stack
3.2 Binary Search Tree : Insert
3.3 Binary Search Tree : Delete
3.4 Binary Search Tree : Update
3.5 Binary Search Tree : Search & Print

4. Algorithm Specfication
4.1 Pseudocodes
4.2 Performance Evaluation

5. Discussion and Conclusion

본문내용

[클래스 구성]
본 프로그램은 총 7개의 클래스로 구성되어 있다. 처음 메인함수에서 CManager의 Run 함수가 실행되면 CManager클래스는 CFile, CData, CBST 클래스의 객체를 생성하고 파일로부터 레코드를 읽어들여온다. 읽어온 레코드는 CData객체의 SplitSaveData 함수를 통해 CData객체의 멤버변수로 저장되며 레코드의 command 필드값에 의해서 CData객체를 매개인자로 가지는 CBST의 Insert, Delete, Update, Print 함수가 실행된다. Print함수가 실행되면 BST의 각 노드들을 파일에 출력하게 되며, 모든 레코드를 다 읽어들이게 되면 파일을 닫고 프로그램을 종료하게 된다.

[복잡도 계산]
Insert Node to BST
트리의 노드 수를 n이라고 하자.
삽입될 노드는 loop 내에서 현재 위치한 트리의 노드의 크기와 작은지 큰지를 비교하며 한쪽 트리로만 이동하게 된다. 즉, 트리의 균형이 최악의 경우가 아니라면 트리의 높이는 log2c1(n+c2)을 가지게 되는데(완전 이진트리의 높이는 log2(n+1)이다) 중간에 같은 값의 노드가 있다면 비교 loop를 빠져나오게 되므로 전체적으로 log2c1(n+c2-c3)의 시간복잡도를 가진다. 그런데 삽입시 이름트리와 전화번호트리 두 곳에서 삽입을 하므로 log2c1(n+c2-c3) * 2 = 2log2c1(n+c2-c3) = 2log2n = O(log2n)의 시간복잡도를 가진다.
하지만 트리의 균형이 최악이라면 트리는 선형리스트와 같은 구조를 지니게 되므로 삽입시 n-c1 = O(n)의 시간복잡도를 가지게 된다

등등...

참고 자료

없음