2023년도 2학기 오픈소스응용프로그래밍 KeyLimePie 팀의 프로젝트입니다.
AVLtree를 이용한 set STL 관련 기능을 구현하였습니다.
해당 프로젝트에서 구현한 Set클래스는 내부적으로 int타입 노드를 저장하는 AVLtree를 멤버변수로 가지고 있습니다.
AVLtree의 특성상 삽입, 삭제 이후 각 노드들의 height를 이용해 Balance Facotr을 구해 구조를 스스로 수정해 항상 O(log(n)) 시간에 연산이 가능합니다.
1.첫번째 줄에는 몇번의 테스트케이스 (T) 를 수행할 지 입력해줍니다.
2.두번째 줄에는 해당 테스트 케이스에서 입력 할 명령어의 수 (n) 를 입력해줍니다.
3.이후 n번의 줄에 걸쳐 명령어를 입력한 즉시 출력이 나오게 됩니다.
(x 와 y는 정수입니다)
insert x
Set에 x값을 가진 노드를 삽입합니다.
이후 노드 x의 depth를 출력합니다.
erase x
Set의 x값을 가진 노드를 삭제합니다.
이후 그 노드의 depth를 출력합니다.
x값을 가진 노드가 없다면 0을 출력합니다.
find x
Set의 x값을 가진 노드의 depth를 출력합니다.
x값을 가진 노드가 없다면 0을 출력합니다.
rank x
Set의 x값을 가진 노드의 depth와 rank(x보다 작은 원소의 수 + 1)를 공백으로 구분하여 출력합니다.
x값을 가진 노드가 없다면 0을 출력합니다.
minimum x
x값을 가진노드가 루트인 부분트리에서 최소 값을 가지는 노드의 값과 depth를 공백으로 구분하여 출력합니다.
maximum x
x값을 가진노드가 루트인 부분트리에서 최대 값을 가지는 노드의 값과 depth를 공백으로 구분하여 출력합니다.
empty
현재 Set이 비어있다면 1을 출력하고 비어있지 않다면 0을 출력합니다.
size
현재 Set에 저장되어있는 원소의 수를 출력합니다.