https://github.com/raywenderlich/swift-algorithm-club/tree/master/B-Tree

B-Tree

B-Tree 는 AVL Tree와 마찬가지로 self-balancing하는 탐색트리지만 children의 개수가 2개보다 많은 트리이다.

요소

N차 B트리는 다음과 같은 특징을 만족한다.

• 모든 노드는 최대 2n개의 key를 가진다.
• 루트를 제외한 모든 노드는 최소 n개의 key를 가진다.
• 리프노드가 아닌 모든 k 키는 k+1개의 자식을 가진다.
• 모든 노드의 키는 increasing order로 정렬된다.
• 모든 리프들은 같은 level에 나타난다.

탐색

1. k를 찾을 때 루트 노트에서 시작한다.
2. linear 탐색을 해 k보다 작지 않은 l을 찾거나 배열의 끝에 도달할때 까지 찾는다.
3. k==l 이면 키를 찾았다.
4. k<l 이면
   • 현재 노드가 leaf가 아니면 l의 왼쪽 자식으로 가서 3번부터 실행
   • leaf노드이면 k가 현재 트리에 없음
5. 배열의 끝에 도달했다면
   • leaf노드가 아니면 마지막 자식노드로 가서 3~5 실행
   • leaf노드이면 k가 현재 트리에 없음

삽입

삭제

병합

B+ Tree

B+ Tree는 B Tree를 개량한 Tree이다. B Tree와의 차이점은 Inner Node에는 Key만 저장되고 Leaf Node에 Key와 data가 함께 저장된다. 따라서 순회가 쉽다.