- 이번 과제에서는 B-Tree 구조를 활용해 set 클래스 템플릿을 구현해야합니다. 그리고 set 클래스에는 총 세 개의 public 멤버 함수만 존재할 수 있습니다. > count, insert, erase - set 클래스에는 아래의 함수가 선언 및 정의되어야합니다. > count, insert, loose_insert, fix_excess, erase, loose_erase, fix_shortage, remove_biggest - 추가로, `show_contents`라는 이름의 public 멤버 함수를 선언 및 정의합니다. 이 함수는 여러분 set 클래스의 B-tree 구조로 저장된 데이터를 표준 출력에 출력하는 함수입니다. 예를 들어, 아래의 정보를 담고 있는 set 객체 S가 주어질 때, show_contents() 함수는 이렇게 표현됩니다. - 여러분이 set 클래스를 잘 구현했는지 확인하기 위해, 프로그램이 사용자와 상호작용하도록 구현해야합니다. 프로그램에 set 변수를 선언하고, 사용자가 'quit'란 명령을 입력하기 전까지 아래의 명령을 수행하도록 작성하세요. - insert x : set 변수에 x 값을 삽입합니다. - erase x : set 변수에서 x 값을 제거합니다. - count x : set 변수에 존재하는 x의 개수를 반환합니다. (중복을 허용하지 않으므로 0 또는 1) - quit : 프로그램 종료 여러분 프로그램은 각 명령을 시행할 때, 내부 데이터를 보여주어야 합니다. - ...
구현
삽입은 생각보다 쉽지만, B-Tree의 특성으로 인해 데이터를 삭제할 때는 고려할 부분이 삽입보다는 많다. `insert`와 `erase`는 외부에서 불러다 사용하기 위해 만들어졌다.[# 다만, 이 함수들도 아예 일을 하지 않는 것은 아니다.]
set 선언에서 MAXIMUM, MINIMUM은 왜 존재하는가? 하면, 이번 구현에는 B-Tree를 이용한다. 저 둘은 B-Tree를 위해 작성한 것인데, B-Tree 특성상 각 노드가 가져야 할 최소/최대 데이터 수를 저녀석들이 관리한다고 보면 되겠다.[# 멤버 중 `data`와 `subset`의 개수는 데이터 삽입/삭제시 조건 완화를 위한 일이라고...]
insert와 loose_inset, fix_excess는 서로 밀접한 연관이 있다. 실제 삽입은 loose_insert에서 이루어지지만, loose_insert가 작업하고 난 뒤의 뒷처리를 insert[# 사실 얘는 fix_excess의 뒷처리를 하는 개념]와 fix_excess가 해결한다고 보면 된다.
loose_insert
loose_insert의 pseudo-code는 아래와 같다.
bool loose_insert(value){
while(value와 같거나 작은 데이터의 인덱스 찾기);
if(현재 노드에 데이터가 있는가? && 찾은 인덱스의 데이터가 넣을 값 value와 같은가?) return false;
else if( 자식이 없나? ){
// 비집고 들어가야하니까
for(찾은 인덱스부터 끝까지 값을 하나씩 밀자)
data[인덱스] = value;
return true; // 넣었잖아! true.
}
// 데이터를 못찾았는데, 자식이 있어? 걔 좀 보자
bool b = subset[인덱스]->loose_insert(value);
// 추가 했으면 뒷처리 해야지
fix_excess(인덱스);
return b;
}
주의할 것은 fix_excess인데, 넣은 곳에서 fix_excess를 실행하면 안 된다. 각 노드가 최대 4개의 데이터만 존재할 수 있다고 하자, 그럼 <6 ~ 10>이 저장된 영역은 데이터가 다섯 개 저장되어 있으므로, 그 상위 노드(parent)든 좌우측 노드든 어찌 되거나 다른 노드와 상호작용을 해야한다.
그런데 만일, 재귀 호출로 <6 ~ 10>값이 this인 노드에서 fix_excess를 실행해버린다면? 그 상위 노드나 주변 형제 노드와 상호작용을 할 수가 없다. this 포인터 자체가 <6 ~ 10>을 저장하고 있는 set을 가리켜버리기 때문이다. 따라서 입력을 완료하고 그 상위 노드[# 5, 11이 저장된 set]로 들어간 다음 접근한 인덱스를 넘기는 방식으로 호출이 이루어져야 한다.
fix_excess를 완료한 뒤의 형태
fix_excess
fix_excess는 현재 노드의 데이터 수가 MAXIMUM을 넘겼을 때, 두 개의 하위 노드로 분할하는 작업을 한다. 가운데 값을 상위 노드의 데이터로 넣고, 나머지를 노드로 나누어 관리하는 방식으로.
void fix_excess(index){
if(접근할 subset의 데이터 수가 MAXIMUM 이하인가?) return;
set cur_set = subset[index];
set new_set = new set; // 새 노드
// 가운데 값을 부모 노드 데이터에 넣으려면 공간 만들어줘야지
for(data_count ~ index) data[i] = data[i-1];
data[index] = cur_set->data[middle_index]
// 이제 노드를 둘로 분할해줘야지
// 먼저 데이터부터
for(i = 0 ~ MINIMUM){
new_set->data[i] = cur_set->data[MINIMUM+1+i]; // new_set의 data_count 설정하는 거 잊지 말고
}
cur_set->data_count = MINIMUM; // 가진 데이터 반을 새로 만든 노드에 줬으니까 절반으로
// 이제 서브셋도 나누고
for(i = 0 ~ MINIMUM){
new_set->subset[i] = cur_set->subset[MINIMUM + 1 + i]; // new_set의 child_count 설정하는 거 잊지 말고..
}
cur_set->child_count = MINIMUM+1; // 가진 서브셋을 절반 나눠줬으니까 그것도 마찬가지로 설정
// 이제 부모 노드의 subset을 수정해줘야지.
for(i = child_count ~ index) subset[i] = subset[i - 1];
subset[index+1] = new_set;
}
insert
위의 두 함수를 작성하면 기본적인 작업은 완료가 된다. 그러나 root는 작업을 하지 않는데, 이유는 다들 알다시피 root에 추가가 될 때는 재귀호출을 진행하지 않는다. 따라서 fix_excess를 처리하지 않는다. 또, root를 고대로 fix_excess에 넣어도 문제가 되기도 하고... 그래서 root에 대한 작업은 insert 함수 안에서 처리한다.
bool insert(value){
// 일단 넣고
if(!loose_insert(value)) return false; // 실패했으면 false 반환하고 탈출
if( root의 데이터가 MAXIMUM을 초과해?){
// 하위로 둘 서브셋 데이터
set l_sub, r_sub;
// 데이터 분할하자
for(i = 0 ~ MINIMUM){
// 각 data_count 설정하는 거 잊지 맙시다..
l_sub->data[i] = data[i];
r_sub->data[i] = data[MINIMUM + 1 + i];
}
// 중간 값을 가장 첫번째로
data[0] = data[MINIMUM];
data_count = 1;
// 자식 서브셋이 있으면 분할해야지
if(child_count){
for(i = 0 ~ MINIMUM + 1){
// 여기서도 child_count 설정해주는 거 잊지 말고..
l_sub->subset[i] = subset[i];
r_sub->subset[i] = subset[MINIMUM+1+i];
}
}
// 다 분할 했으니까 지금 노드에 서브셋으로 넣어줘야지
subset[0] = l_sub;
subset[1] = r_sub;
child_count = 2;
}
}
Erase
Erase 명령을 구현하는 부분을 보면 오히려 <Insert> 부분의 구현이 쉬웠다고 느껴질 수 있다.
마찬가지로 <erase>는 <loose_erase>를 비롯한 여러 함수를 구현한 뒤 작성한다.
loose_erase
실질적인 삭제는 loose_erase에서 작업한다. 삭제 작업에서는 생각해야할 것이 두 개다. 하나는 leaf에서 값을 삭제하는 것, 두번째는 parents[# child_count > 0인 노드, not leaf]에서 값을 삭제하는 것이다.
leaf와 parents에서 작업하는 두 개의 방법을 별개로 작업하면 상당히 힘들어질 수 있다. 그래서 <remove_biggest> 함수가 존재한다. C++의 레퍼런스 접근을 통해 하위 노드에서 가장 큰 값을 불러오고 하위 노드의 데이터 수를 줄이는 방법이다.
삭제할 데이터가 하위 노드를 가진 parents에 있다
이 때, remove_biggest가 없다면 8을 삭제한 뒤, 그 하위노드[# 초록색으로 되어있는]를 합치고, 만일 MAXIMUM을 넘긴다면 다시 fix_excess를 진행해야한다. 그래서 remove_biggest 함수를 이용해 값 7을 8이 있는 위치에 올려버리는 식으로 삭제를 대신한다.
하위 노드의 데이터 길이가 변경되었으니 경우에 맞추어 fix_shortage를 진행하는 것으로 처리한다.
아래는 loose_erase의 슈도코드이다.
bool loose_erase(value){
while(삭제할 값보다 작은 인덱스 넘기기);
if(자식이 없다? > 내가 자식이다(leaf)){
if( 찾은 인덱스 위치의 데이터가 찾는 데이터value와 다른가?) return false; // 있지도 않네
// 찾았으니까 바로 다음 데이터들 끌어당겨서 덮어버리자
for(i = index ~ data_count) data[i] = data[i+1];
--data_count; // 데이터 하나 줄었으니까
return true;
}
bool result = true; // 지웠나?
if(data[index] == value){ // 자식이 있는데 삭제할 값을 찾아버렸다
subset[index]->remove_biggest(data[index]); // 자식 중에 제일 큰걸로 덮어버려
}else{
// 못찾았는데 자식은 있으면 자식을 훑으러 가야지
result = subset[index]->loose_erase(value);
}
// 삭제했으면 길이가 바뀌었을 수도 있으니까
if(subset[index]->data_Count < MINIMUM) fix_shotage(index);
return result;
}
remove_biggest
remove_biggest는 인자로 레퍼런스 타입을 가져온다. 즉, 넘겨주는 데이터를 복사하는 것이 아니라 해당 공간에 바로 접근이 가능하도록 하는 것[# https://pang2h.tistory.com/423]이다.
재귀 호출이 이루어지므로, child_count가 0일 때는 호출하지 않도록 구성해야 한다.
삭제한 뒤 작업할 때는 두 개의 경우를 고려할 수 있다. 하나는 merge(병합)이고, 다른 하나는 다른 곳에서 하나를 가져오는 것이다.
여기에서 대표적으로 6과 9를 삭제할 때 작업하는 내용이 달라진다. 9를 지우는 경우를 보자. 9를 지우게 되면 MINIMUM이 2인 현재 상태에서 10 하나만 남게 되므로 병합을 진행해야한다.
병합. parents의 데이터와 좌측 노드의 값을 합친다
다른 한편, 6을 지우는 경우를 보자, 이 경우 좌측의 <1~4>를 저장하는 노드에서 값 하나를 빼오더라도 MINIMUM보다 많은 수의 data를 보관하고 있게 된다. 따라서 병합을 하지 않고 값 하나를 가져오기만 해도 된다.
부모 노드의 값을 삭제할 데이터 위치로 옮기고, 부모 노드의 값은 다음 노드의 시작 부분을 가져오는 것으로 해결할 수 있다. 이를 슈도코드로 변경하면 다음과 같다.
void fix_shortage(index){
index // 작업할 인덱스
helper = index - 1 // 작업에 도울 인덱스
// 병합을 진행해야할까?
if(subset[helper]->data_count == MINIMUM){
merge(...);
}else{ // 왼쪽에서 가져와도 문제가 없다
// 첫 번째에 데이터 넣어야하니까 공간 만들기
// data 수 늘어나니까 data_count 값 조절하는 거 잊지 말고
for(i = subset[index]->data_count ~ 0 ) subset[index]->data[i] = subset[index]->data[i-1];
subset[index]->data[0] = data[helper];
// parents에서 값 가져왔으니까 helper subset 마지막 값을 parents로 넘겨줘야지
// subset[helper]->data_count 값 조정해야하는 것..
data[helper] = subset[helper]->data[subset[helper]->data_count];
// 자식이 있으면 하나 가져와야지
if(subset[helper]->child_count){
// 맨 앞에 공간 만들고
for(i = subset[index]->child_count ~ 0) subset[index]->subset[i] = subset[index]->subset[i-1];
// 값 가져오기
subset[index]->subset[0] = subset[helper]->subset[--subset[helper]->child_count];
}
}
}
이렇게만 하면 좋겠지만, 우리는 0번 subset에서도 작업이 이루어진다는 것을 잊지 말아야한다. 지금 상황에 `fix_shortage(0)`을 호출해버리면 helper는 -1이 되어서 out of index 오류가 발생한다. 따라서 0을 호출했을 때는 helper는 index - 1이 아니라 index + 1로 해서 작업을 진행해주어야한다. 그러니 분기구문으로 나눠버리자.
void fix_shortage(index){
index // 작업할 인덱스
// 첫 subset인가?
if(index == 0){
helper = index + 1;
if(subset[helper]->data_count == MINIMUM){ // 병합 조건을 만족하나
merge(...);
}else{
// 마지막에 데이터 넣어야하니까 공간 만들 필요가 없지
subset[index]->data[subset[index]->data_count++] = data[0];
// parents에서 값 가져와도 parents에는 다시 넣어줄거니까 값 변경할 필요가 없지
data[0] = subset[helper]->data[0];
// 0번 데이터 빼왔으니까 데이터 다시 정렬해줘야지
for(i = 0 ~ subset[helper]->data_count) subset[helper]->data[i] = subset[helper]->data[i+1];
--subset[helper]->data_count;
// subset이 있는가? 있으면 얘도 나눠줘야하니까
if(subset[helper]->child_count){
// subse 넘겨주고
subset[index]->subset[subset[index]->child_count++] = subset[helper]->subset[0];
// 빈공간 채우고
for(i = 0 ~ subset[helper]->child_count) subset[helper]->subset[i] = subset[helper]->subset[i+1];
--subset[helper]->child_count;
}
}
}else(
helper = index - 1;
// 병합을 진행해야할까?
if(subset[helper]->data_count == MINIMUM){
merge(...);
}else{ // 왼쪽에서 가져와도 문제가 없다
// 첫 번째에 데이터 넣어야하니까 공간 만들기
// data 수 늘어나니까 data_count 값 조절하는 거 잊지 말고
for(i = subset[index]->data_count ~ 0 ) subset[index]->data[i] = subset[index]->data[i-1];
subset[index]->data[0] = data[helper];
// parents에서 값 가져왔으니까 helper subset 마지막 값을 parents로 넘겨줘야지
// subset[helper]->data_count 값 조정해야하는 것..
data[helper] = subset[helper]->data[subset[helper]->data_count];
// 자식이 있으면 하나 가져와야지
if(subset[helper]->child_count){
// 맨 앞에 공간 만들고
for(i = subset[index]->child_count ~ 0) subset[index]->subset[i] = subset[index]->subset[i-1];
// 값 가져오기
subset[index]->subset[0] = subset[helper]->subset[--subset[helper]->child_count];
}
}
}
}
merge
만일 <fix_shortage>에서 작업을 진행하던 와중에 helper subset에서도 minimum이 나와버리면 가져오는 것 만으로는 문제를 해결할 수가 없다. 그래서 두 subset을 병합을 해주어야한다. 이 과정에서 joiner는 병합의 주체가 되고, joinee는 병합이 끝나면 더이상 사용되지 않고 버려지므로 메모리에서 해제해 누수를 방지한다.
