1. B트리란?
균형 트리 중 하나, BST에서 데이터가 한쪽으로 치우치는 것을 방지(치우치면 검색 성능이 안좋아짐)
2. B트리의 특징
| M | 입력받은 차수, 노드의 최대 자식 노드 수 |
| M - 1 | 각 노드에 저장될 수 있는 최대 데이터의 수 |
| M/2 올림 | 각 노드의 최소 자식 노드 수(루트 노드, 리프 노드 제외) |
| M/2 - 1올림 | 각 노드의 최소 데이터의 수(루트 노드) |
3. 구현(3차 B트리)
| 삽입 | 추가할 때는 항상 리프 노드에 데이터를 추가 |
| 노드에 저장할 수 있는 최대 데이터 수를 넘으면 가운데 데이터를 기준으로 | |
| 좌우 노드로 나눠주고 가운데 노드를 부모로 만들어준다. | |
| 노드 안에 데이터들은 오름차순으로 정렬해서 저장 |
1. B트리란?
균형 트리 중 하나, BST에서 데이터가 한쪽으로 치우치는 것을 방지(치우치면 검색 성능이 안좋아짐)
데이터
왼쪽 오른쪽
d1, d2
x<d1 d1<x<d2 x>d2
d1, d2, d3
x<d1 d1<x<d2 d2<x<d3 x>d3
2. B트리의 특징
M : 입력받은 차수, 노드의 최대 자식 노드 수
M - 1 : 각 노드에 저장될 수 있는 최대 데이터의 수
M/2 올림 : 각 노드의 최소 자식 노드 수(루트 노드, 리프 노드 제외)
M/2 - 1올림 : 각 노드의 최소 데이터의 수(루트 노드)
3. 구현(3차 B트리)
1) 삽입
추가할 때는 항상 리프 노드에 데이터를 추가
노드에 저장할 수 있는 최대 데이터 수를 넘으면 가운데 데이터를 기준으로
좌우 노드로 나눠주고 가운데 노드를 부모로 만들어준다.
노드 안에 데이터들은 오름차순으로 정렬해서 저장'bootcamp > Java' 카테고리의 다른 글
| 1206 AVL Tree (0) | 2023.12.22 |
|---|---|
| 1206 Red Black Tree (0) | 2023.12.22 |
| 1206 트리 (0) | 2023.12.22 |
| 1205 리스트 (0) | 2023.12.22 |
| 1204 스택(stack)/큐(queue)/재귀 (0) | 2023.12.22 |
