B tree

이진 트리(Binary Tree)

자식 노드가 최대 2개인 노드들로 구성된 트리로, 각 자식 노드는 왼쪽 자식 노드, 오른쪽 자식 노드로 나눌 수 있다.

또한 자료의 삽입, 삭제 방법에 따라서 다음과 같이 나뉘어질 수 있다.

• Full Binary Tree : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
• Complete Binary Tree (완전 이진 트리) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 왼쪽부터 노드가 순서대로 채워진 이진트리이다.
• Perfect Binary Tree (포화 이진 트리) : Full Binary Tree 이면서, Complete Binary Tree 인 경우이다. 모든 leaf node의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다.

이진 탐색 트리(Binary Search Tree)

binary search와 linked list를 결합한 이진트리이다.

• 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고, 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가진다.
• 자녀 노드는 최대 2개까지 가질 수 있다.
• 이진 탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료 입력과 삭제를 가능하게끔 고안되었다.
• 즉, Binary Search Tree는 모든 왼쪽 자식의 값이 root나 부모보다 작고, 모든 오른쪽 자식의 값이 root나 부모보다 큰 값을 가진다.

B tree

자녀 노드를 3개 가지고 싶다면? -> 부모 노드에 key를 2개저장한다.

BST를 일반화한 트리이다. -> 부모 노드는 자녀 노드를 2개이상 가질 수 있다.

• 특징 정리
  • 모든 leaf 노드들은 같은 레벨에 있다. -> balanced tree 
    • 검색의 average, worst case의 시간 복잡도가 항상 O(log N)이다.  
  • 노드가 자녀를 x개 가졌다면 key는 x-1개를 가진다.
    • 부모 노드에 key를 하나 이상 저장한다.
  • 노드내의 key들은 오름차순으로 정렬된다.
  • 정렬된 순서에 따라 자녀 노드들의 key 값의 범위가 결정된다.
  • 이런 방식을 사용하면 자녀 노드의 최대 개수를 입맞에 맞게 결정해서 쓸 수 있다.
  • B tree 는 BST를 일반화한 tree라고도 한다.

이때, 최대 몇 개의 자녀 노드를 가질 것인가가 B tree를 사용할 때 중요한 파라미터이다.

B tree 파라미터

• 각 노드의 최대 자녀 노드 수 = M 개
  • 이때, 최대 M개의 자녀를 가질 수 있는 B tree를 M차 B tree라고 부른다.
• 각 노드의 최대 key의 수 = M - 1 개
• 각 노드의 최소 자녀 노드의 수 = 올림(M/2) 개
  • root node 및 leaf node는 제외
• 각 노드의 최소 key 수 = 올림(M/2) - 1 개
  • root node는 제외
• 일반적으로, interanl 노드의 key 수가 x개라면, 자녀 노드의 수는 언제나 x+1 개이다.
  • 따라서 각 노드가 최소 하나의 key는 가지기 때문에 몇 차 B tree 인지와는 상관없이 internal 노드는 최소 2개의 자녀는 가진다.
• M이 정해지면, root 노드를 제외하고 internal 노드는 최소 올림(M/2)개의 자녀 노드를 가질 수 있게된다.

B tree 의 데이터 삽입

• 데이터 삽입은 항상 leaf 노드에 한다.
• 노드가 넘치면(최대 key 개수보다 크면) 가운데(median) key를 기준으로 좌우 key들은 분할하고 가운데 key는 승진한다.
• key들을 오름차순 정렬한다.

B tree 의 데이터 삭제

• 삭제도 항상 leaf 노드에서 발생한다.
• 삭제 후 최소 key 수보다 적어졌다면 재조정한다.
  • B tree에서 각 노드의 최소 key 수는 올림(M/2) - 1개이다.
  • EX) 3차 B tree의 각 노드의 최소 key의 개수는 1개이다.(root node는 제외)

• 삭제 후 최소 key 수(1개)보다 적어졌다면 재조정한다.
  1. key 수가 여유있는 형제의 지원을 받는다.
  2. 1번이 불가능하면 부모의 지원을 받고, 형제와 합친다.
  3. 2번 수행 후 부모에서 문제가 발생하면, 그 위치에서 다시 재조정이 필요하다.

형제의 지원이 불가능하면 부모의 지원을 받고 형제와 합쳐야 한다. 이때, 중요한 점은 왼쪽 방향으로 합치는 것이다.

• 동생이 있으면 동생과 나 사이의 key를 부모로부터 받는다.
  • 그 key와 나의 key를 차례대로 동생에게 합친다.
  • 나의 노드를 삭제한다.
• 동생이 없으면 형과 나 사이의 key를 부모로부터 받는다.
  • 그 key와 형의 key를 차례대로 나에게 합친다.
  • 형의 노드를 삭제한다.

여기에서 차례대로 2 -> 1 삭제시, 부모가 지원한 후에 부모에 문제가 발생하면 상황에 맞게 대응하는 방법을 수행한다.

• 부모가 root 노드가 아니라면
  • 그 위치에서부터 다시 1번부터 재조정을 시작한다.
• 부모가 root 노드이고 비어있다면
  • 부모 노드를 삭제한다.
  • 직전에 합쳐진 노드가 root 노드가 된다.

internal 노드 데이터 삭제

• leaf 노드에서 삭제하고 필요하면 재조정한다.
• internal 노드에 있는 데이터를 삭제하려면 leaf 노드에 있는 데이터와 위치를 바꾼 후 삭제한다.
  • leaf 노드에 있는 데이터 중에 어떤 데이터와 위치를 바꿔줄 것인지가 이슈가 된다.
  • 선임자나 후임자는 항상 leaf 노드에 있으므로, 삭제할 데이터의 선임자나 후임자와 위치를 바꿔준다.
  • 선임자(predecessor) : 나보다 작은 데이터들 중에서 가장 큰 데이터
  • 후임자(successor) : 나보다 큰 데이터들 중에서 가장 작은 데이터

 B tree 데이터 삭제 방법 정리

• 삭제는 항상 leaf 노드에서 발생한다.
• internal 노드의 경우, 선임자와 위치를 바꾼 후 삭제한다.
•  삭제 후 최소 key의 수보다 적어졌다면 재조정한다.
  • 형제의 지원을 받는다.
  • 부모의 지원을 받고, 형제를 합친다.
  • 부모의 도움 후 부모도 문제가 발생하면 재차 조정한다.

5차 B tree에서 데이터 삭제

• 5차 B tree에서 각 노드의 최소 key의 수 = 2개 (root node 제외)

인용

https://velog.io/@yeonkr/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%99%80-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8A%B8%EB%A6%AC-BST-Binary-Search-Tree

[자료구조] 이진 트리와 이진 탐색 트리 (BST: Binary Search Tree)

https://www.youtube.com/watch?v=bqkcoSm_rCs&ab_channel=%EC%89%AC%EC%9A%B4%EC%BD%94%EB%93%9C 

https://velog.io/@yeonkr/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%99%80-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8A%B8%EB%A6%AC-BST-Binary-Search-Tree

[자료구조] 이진 트리와 이진 탐색 트리 (BST: Binary Search Tree)