B-트리 삭제 알고리즘
-
B-트리 #2. 삭제Programming/College 2010. 6. 3. 13:30
삽입 검색 알고리즘에 이어 삭제 알고리즘을 알아보자. 삭제가 수행된 B-트리가 계속 B-트리의 성질을 유지하기 위해서는 키가 삭제된 뒤에도 최소한의 키 수가 되는지를 확인해야 된다. 만일 해당 노드가 최소한으로 유지해야 될 키 수보다 작게 되는 경우에는 적절한 조치를 취해줘야 한다. 삭제를 위해서는 삽입에서와 같이 먼저 삭제하려는 키 값이 들어있는 노드를 탐색한다. 만일 삭제하려는 키 값이 내부 노드에 있다면 리프 노드에 있는 이 키 값의 후행(Successor) 키 값과 교환을 한 뒤에 리프 노드에서 삭제한다. 삭제 후 노드가 유지해야 될 최소 키 값의 수가 만족하지 않으며 재분배(Redistribution)나 합병(Merge) 방법을 이용하여 최소 키 값 수를 유지하도록 해야 한다. ▣ 재분배(Red..