위 파일은 인터넷서 얻은 도식화 파일이다. 그림으로 설명이 참 깔끔하게 잘 된듯 하다. 참조... http://swblog.net/entry/B-Tree B트리의 처리 방식은 제각각인 듯 하다. B트리의 원칙만 잘 지키면 되는 듯 하다. 삽입의 경우 좀 특이하게 처리했던 경우는(이재규 알고리즘 강좌) 일단 위에서부터 아예 포화상태에 놓인 경우(5차원시 노드에 5개 요소가 있는경우) 먼저 분할시키면서 아래로 내려와서 마침내 들어갈 자리를 찾으면 해당 노드에 요소를 삽입하는 방식이다. 이때문에 해당 노드에서 분할시에 부모가 오버플로우될 상황은 없다.(부모노드 요소의 갯수는 모두 4개 이하이므로) 다른 방식은 위 도식화에서 표현하듯이 저질러놓고 수습하는 방식인 데 이게 일반적인 경우인 듯 하다. 일단 해당 값..

이분 검색의 삽입방식은 맨 끝에 요소를 놓고 노말하게 삽입정렬을 하는 방식이다. 이 부분을 조금 더 빨리 개선할 수 있는 점이 보인다. 이미 정렬된 상태이므로 find와 유사한 함수를 만들어 들어갈 자리를 쉽게 찾을 수 있으리라 본다. 가령 1,3,5,9,11 등에서 7을 집어 넣는다 할 때 우선 7을 찾아보면 인덱스 2 중간값 5보다 큰 수이므로 오른쪽으로 가고 인덱스 3 중간값 9보다는 작으므로 다시 찾는 루틴을 시도하지만 조건 불만족으로 탈출할 것이다. 탈출시 조사한 곳의 mid값을 가지고 위치판단이 가능할 것이다. 위와 같은 식으로 자리를 찾는 수고를 덜 수 있으리라 본다. 찾을 때 O(N)을 O(lon(2)N) 수준으로 줄인다. 그 뒷자리 메모리를 일괄적으로 한칸씩 미는 수고는 어쩔 수 없지만,..