트리에 관하여

목차

◈ 트리(tree)

◆ 트리의 정의

◆ 용어설명

◆ 트리의 목적

◆ 트리의 종류

◆ B트리

본문내용

분할하며, 이 때 m/2 번째 키와 새로운 노드를 가리키는 포인터를 부모노드에 삽입.
(2) m차 B트리에서 삭제 알고리즘
① 리프노드는 그냥 삭제
② 삭제노드가 리프가 아니면 리프에 존재하는 선행키(또는 후행키)로 대치하고 리프에서 선행키(또는 후행키)를 삭제.
③ 삭제한 후 남은 키의 수가 최소 키 수인 (m/2 - 1)보다 적으면 언더플로 발생
(3) 언더플로 처리 방법
① 인접 형제노드에 여분의 키가 있는 경우(m/2 - 1개 보다 많은 키가 있음), 키를 나누어 저장(재분배).
② 인접 형제노드에 최소 개수의 키가 있는 경우(m/2 - 1개의 키가 있음), 인접 형제노드와 합병. 부모노드의 분리키가 필요 없어지므로 이 키도 함께 합병.
5. B트리와 B+트리 삽입 알고리즘의 차이점
- 노드 단순 삽입시
B트리에서 삽입은 항상 리프에서만 이루어진다. 리프노드가 삽입할 공간이 비어있다면 해당 노드에 단순 삽입시키면 된다.
예를 들면, 22를 삽입하고자 할 때 검색에 의하여 해당 리프노드 l이 20만 들어있고 비어있다면 그대로 빈 공간에 22를 삽입하면 된다.
l l
20
20
22
또한 노드의 값들을 항상 오름차순을 유지해야 하므로 만약 19를 삽입하고자 할 때에는 키값 20이 오른쪽으로 이동하고 그 자리에 19가 삽입되어야 한다.
l l
20
19
20
B+트리에서의 노드의 단순삽입은 B트리와 동일하다. 즉, 삽입은 항상 리프노드에서만 이루어지며 삽입시 노드의 킷값은 오름차순을 유지할 수 있게 삽입된다.
- 노드 분열 삽입시
삽입해야 할 리프노드가 가득 차 있다면 해당 노드를 분열(split)시켜야 한다. B트리에서는 해당 노드를 두 개의 노드로 분할하여 키값의 절반은 한쪽 노드에 들어가고 나머지 반은 다른 노드에 들어가며 중간키 값은 부모노드에 삽입된다.
이때 부모노드에서는 분열된 노드들을 가리키는 포인터가 첨가되고 순서가 조정된다.
예를 들어, 노드 o가 가득 차 있는데 여기에 25를 삽입할 때에는
f f
30
22
30
o p o o' p
20
22
20
25
만약 부모노드 역시 가득 차 있다면 부모노드 역시 분할하게 되며 이때 부모노드의 포인트들은 조정되게 되며 부모노드의 중간키 값은 해당노드의 부모노드에게 또 삽입된다.
B+트리에서의 분할은 B트리와 다르다. 모든 킷값은 리프노드에서만 가지고 있기 때문에 분열시 중간키 값이 부모노드에 저장되고 동시에 리프노드에도 그 키값을 가지고 있게 된다.
예를 들면, 다음과 같다.
f f
30
22
30
o p o o' p
20
22
20
22
25
따라서 B+트리에서의 리프노드가 아닌 곳, 즉 인덱스 노드에서의 키값은 검색을 위한 키값이지 실제 데이터를 가리키는 포인터를 가지지 못하고 리프노드에서만 가지게 된다.
또한 B+트리의 자료구조상 각 리프노드들은 서로 오름차순으로 순차세트의 연결리스트를 가지고 있어야 되므로 노드가 분열된 뒤 순차세트의 연결리스트에 순차성이 유지되도록 포인터들이 적절히 삽입되어야 한다.
6. B트리와 B+트리 삭제 알고리즘의 차이점
<노드 단순 삭제시>
B트리에서의 삭제도 삽입에서와 같이 리프노드에서 수행된다. 삽입에서와 같이 먼저 삭제하려는 킷값이 들어 있는 노드를 찾기 위해 B트리를 탐색한다. 만일 삭제하려는 킷값이 리프가 아닌 노드에 있다면 그 킷값의 후행키값 (B트리의 특성상 이 후행 키값은 항상 리프노드에 있게 된다)과 일단 자리를 바꾸어 리프노드로 옮긴 형태의 트리로 만든 뒤 삭제한다. 왜냐하면 이 방법이 삭제연산을 훨씬 간단하게 만들기 때문이다. 물론 이 후행키값 대신에 선행키 값을 사용할 수도 있다.
예를 들면, 리프노드에 삭제할 킷값이 존재한다면
l l
20
22
20
(노드 l에서 킷값 22의 삭제)
l l
20
22
22
(노드 l에서 킷값 20의 삭제)
만약 삭제할 키값이 부모노드에 존재한다면
f f f
30
31
31
o p o p o p
20
22
31
32
20
22
30
32
20
22
32
(노드 f에서 킷값 30의 삭제)
B+트리에서는 삭제방법이 좀 다르다. 왜냐하면 모든 킷값은 리프노드에만 존재하기 때
문에 삭제는 리프노드에서만 이루어지게 된다. 만약 인덱스 노드에서 해당 킷값을 찾았다해
도 그 값은 인덱스 값이지 실제 킷값이 아니므로 리프노드까지 검색해서 해당노드에서 삭제해야만 된다. 또한 인덱스노드의 킷값은 리프노드에서 그 킷값이 삭제되었다 하더라도 인덱스노드에서 제거되지 않는다. 왜냐하면 그 값은 다른 키를 찾기 위한 인덱스 값이 되기 때문이다. 따라서 인덱스 노드에 킷값이 존재한다고 해서 반드시 리프노드에 킷값이 있다고 할 수는 없게 된다.
예를 들어보면, 삭제할 키값이 인덱스 노드와 리프노드에 있다면 다음과 같이 된다.
f f
30
30
o p o p
20
30
20
(B+트리에서 킷값30의 삭제)
<노드 삭제시 언더플로우 발생했을 경우>
☞ 언더플로우 발생시 B트리와 B+트리의 대처방법은 비슷하다. 먼저 언더플로우가 발생한 노드이 형제노드를 살펴서 재분배가 가능하면 재분배를 하며 재분배가 불가능하다면 형제노드와 합병을 하게 된다.
재분배시 B트리에서는 양 형제노드와 부모노드의 값을 모아서 그 중 중간값을 부모노드의 값과 교체시키고 그 값보다 작은 키들은 왼쪽 노드에 큰 키들은 오른쪽 노드에 넣게
된다. 하지만 B+트리에서는 부모노드의 값은 인덱스 값에 불과하므로 양쪽 노드의 값만 모아서 그 중 중간 인덱스 값을 부모노드에 넣고 그 값보다 적거나 같은 키는 왼쪽노드에 큰 키들은 오른쪽 노드에 넣게 된다.
합병시 B트리에서는 양 형제노드와 부모노드의 값을 한쪽 형제 노드에 넣고 다른 형제노드는 삭제시키고 부모노드의 킷값들을 정렬한다. 그러나 B+트리에서는 양 형제노드를 하나의 노드로 합병한 후 부모노드의 킷값만 삭제하면 된다. 왜냐하면 부모노드의 값은 인덱스 값이므로 합병된 노드의 값보다 가장 큰 값이 부모노드의 다음 키값이 되므로 해당 형제노드의 부모노드의 킷값만 삭제되면 트리구조상 문제없게 된다.
예를 들어보면, 다음과 같다.
f f
30
40
40
o p q op p
10
35
20
(B+트리에서 킷값35의 삭제 후 합병)

키워드

트리,   이진트리 ,   루트,   노드