자료구조 끝판왕인 b-tree, b+tree 구현 프로젝트를 진행했다.
📅 기간 : 2021.01.07 ~ 2021.01.14
b-tree, b+tree 이론은 구글링하면 많이 나온다.
프로젝트 진행하면서 에러났던 부분들에 대해 1. 에러가 발생한 이유, 2. 해결 방법 위주로 정리하려 한다.
지금은 이슈 위주로 글을 저장해두고 추후에 수정할 예정
B-tree
1. 왼쪽 자식, 오른쪽 자식 모두 최소 키수라서 병합할 때, 항상 오른쪽에 있는 형제와 병합하는데 맨오른쪽 노드는 오른쪽 노드가 없으므로 왼쪽 노드와 병합해야함
-> 분기해줘야 함
2. 자식을 옮겨주는 과정에서 자식이 자식을 덮어쓰는 에러가 발생함
-> 키가 i에서 끝났다면 자식은 i+1 부터 옮겨줬어야했는데 i부터 옮기니까 덮어쓰게되는 거였음. 인덱스 조심하자 !!!!!
3. 다 잘 돌아가는데 free하면서 쓰레기값이 생김
구조체 선언 시, linker[MAX+2] 로 선언했어야했는데 linker[MAX+1]로 선언하는 실수를 범함.. key[MAX+1]로 선언했으면 linker는 하나 더 많아야하는데 실수했다. 코드를 다 짜고 free에서 에러가 발생한 거라 계속 삭제 함수 로직에 오류가 있는 줄 알고 아래쪽에서만 찾았는데 알고보니 코드 맨 상단 구조체 선언부터 잘못된 것이었다.
-> 에러가 발생하면 맨위에서부터 차근차근 찾아가는 습관을 들이자.
4. 코드를 모두 완성했는데, 윈도우 + vscode 환경에선 잘 돌아가는데 맥 + clion 환경에서 루트노드 삭제 시, succ나 pred값을 찾지 못하고 쓰레기값을 들고 오는 에러가 발생함.
-> succ, pred를 찾는 함수에서 재귀호출 부분에 return을 붙였더니 해결됨. return이 없어서 함수 종료되면서 쓰레기값을 반환했던 것으로 생각됨. 윈도우+vscode 환경에서는 함수 종료시 return 값이 없어도 재귀함수 안에서 return했던 값을 반환해주는 반면, 맥+clion 환경에서는 더 엄격한 것으로 생각됨. 컴파일러가 알아서 해주겠지 라는 생각보다는 어떤 환경에서도 에러없는 완벽한 코드를 짜자!
B+ tree
1. 상황 : leaf node가 들고있는 value 값을 insert 함수의 인자로 전달해주면 어떻게 노드에 정보를 담을 것인가.
함수 : void node_insert(node *sub_root, int k, int v)
-
문제점
처음엔 이렇게 받아온 v를int *value = &v로 바로 주소값을 받으려고 했더니 계속 같은 주소값에 v값만 덮어씌워져서 leaf node에 같은 value값이 들어가는 현상이 발생했다. -
해결
함수가 선언될 때, 지역변수, 매개변수의 경우 스택 영역에 메모리가 할당되고, 함수가 종료되면 메모리가 해제된다. 원래의 방식대로하면 insert를 실행하면 stack에 쌓였다가 메모리가 해제되고, 다시 insert를 실행하면 그 자리에 쌓이기 때문에 같은 값이 들어가는 것이다.
동적 할당의 경우, 힙 영역에 메모리가 할당되고 free를 해야 메모리가 해제되므로 동적 할당으로 문제를 해결했다.
함수가 들고온 인자는 int형 포인터를 선언해서 malloc해주고, 그 포인터의 값에 전달받은 value값을 담음.
2. search 할 때, 그 값으로부터 일정 개수만큼 출력할 때, 노드가 두번째 분할되는 지점부터 출력이 안되는 현상 발생.
leaf node끼리 연결이 안돼서였음.
split node 함수에서 리프노드라면
right_child->right = left_child->right;
left_child->right = right_child;
right_child->left = left_child;위와 같이 right_child->right = left_child->right; 를 해주고 연결해줘야 리프노드 사이에 새로운 리프노드가 생길 때 연결됨
