B tree
자가 균형 이진탐색트리(Self-Balancing Binary Search Tree)중 하나이다.
이진 트리의 경우 정렬된 데이터가 순서대로 삽입된 경우처럼
균형이 맞지 않으면 검색 효율이 선형 검색급으로 떨어진다.균형을 맞추기 위한 자료구조로 검색, 삽입, 삭제 모두 O(logN)의 성능을 보장한다.
이진 트리를 확장해서 더 많은 수의 자식을 가질 수 있게 만들어 졌다.
특징
- 노드의 데이터 수를 N이라고 하면 자식의 수는 N+1 이어야 한다.
- 각 노드의 자료는 정렬된 상태여야한다.
- 루트 노드는 적어도 2개 이상의 자식을 가져야한다.
- 루트노드가 leaf 노드인 경우 제외
- 루트 노드를 제외한 모든 노드는 적어도 M/2의 자료를 가지고 있어야한다.
- M은 차수(노드가 가질수 있는 최대 자식 수)를 말한다.
- 외부 노드로 가는 경로의 길이는 모두 같다.
- 입력 자료는 중복이 될 수 없다.
- 모든 leaf 노드는 같은 level에 있어야 한다.
검색
- 루트 노드부터 탐색을 시작한다.
- 노드의 key를 순회하며 원하는 값을 찾으면 종료한다.
- 원하는 값이 존재하지 않는다면 그 값이 존재하는 사이의 포인터로 이동하여 탐색한다.
아래는 14 라는 key를 검색하는 과정이다.
삽입
최대 key의 개수를 2으로 제한한다.
- 빈 트리인 경우 root node를 만들어 K를 삽입한다.
root node가 가득 찬 경우 node를 분할하여 leaf node를 생성한다.- K가 들어갈 leaf node를 검색 과정과 동일하게 탐색한다.
- 해당 leaf node에 자리가 남아있다면 정렬을 유지하도록 알맞은 위치에 삽입하고,
leaf node가 꽉 차 있다면 K를 삽입한 후 해당 node를 분할한다.- node가 분할되는 경우 node의 중앙값을 기준으로 분할한다.
중앙값은 부모 node로 합쳐지거나 새로운 node로 생성되고,
중앙값을 기준으로 왼쪽의 key는 왼쪽 자식, 오른쪽의 key는 오른쪽 자식으로 생성된다.
아래는 13 을 삽입하는 과정이다. 검색하는 과정은 생략한다.
깊이가 3이기 때문에 노드에 최대로 들어갈 수 있는 key의 수는 2이다.
삭제
삭제할 key가 리프 노드에 있는 경우
현재 노드의 key수가 최소보다 큰경우
단순 삭제해도 무방하다.
현재 노드의 key수가 최소이고, 왼쪽 또는 오른 쪽 형제의 노드의 key 수가 최소보다 큰 경우
삭제 데이터가 10이라고 가정
삭제 대상 key를 부모 노드에서 가장 큰 요소로 변경한다.
만약 대상 노드가 가장 오른쪽에 있는 노드라면 가장 작은 요소로 변경한다.
바꾼 대상이 왼쪽 형제의 key 수가 최소보다 크다면 왼쪽 형제 key 중 가장 큰 값으로 삽입하고 삭제한다.
바꾼 대상이 오른쪽 형제의 key 수가 최소보다 크다면 오른쪽 형제의 key 중 가장 작은 값으로 삽입하고 삭제한다.
현재는 오른쪽 형제 key 수가 최소보다 크다.
현재 node의 왼쪽, 오른쪽 형제 node의 key 수가 최소이고, 부모 node의 key수가 최소보다 큰 경우
대상 노드를 삭제한다.
부모 노드에서 가장 큰 값을 삭제 대상이 있는 노드에 합쳐준다.
만약 가장 우측에 있는 노드라면 가장 작은 값을 삭제 대상이 있는 노드에 합쳐준다.
현재 상황은 부모 노드가 가장 우측에 존재하기 때문에 가장 작은 값을 삭제 대상 노드에 합쳐준다.
현재 노드와 왼쪽, 오른쪽 형제 노드, 부모 노드 모두 key수가 최소 인경우
현재 node와 자식 node 모두 key 수가 최소인 경우(*) 와 동일
삭제할 key가 리프 노드를 제외한 node에 있는 경우
현재 노드 또는 자식의 노드의 key 수가 최소보다 큰 경우
왼쪽 자손 노드들 중 가장 큰 값 또는 오른쪽 자손 노드들 중 가장 작은 값으로 변경한다.
이후 삭제할 노드가 리프 노드의 있는 경우를 따른다.
현재 노드와 자식 모두 key 수가 최소인 경우(*)
대상 노드를 삭제하고 자식 노드들을 합친다.
합쳐진 노드를 n1이라고 한다.
삭제 대상 노드의 부모 노드에서 가장 가까운 키를 형제 노드(n2)에 합친다.
그리고 n2에 n1을 자식으로 합친다.
n2의 키의 수가 최대값을 넘으면 분할한다.
