Balanced Tree

이진트리검색의 문제점은 좌우 균형이 맞지 않으면 탐색에 있어 비효율적이다.

이러한 문제점을 해결하기 위해 Balanced Tree가 만들어졌다. Balanced Tree는 삽입, 제거 등이 발생했을 때 좌우 균형을 맞춰주는 것이 특징이다.

대표적인 예로 Red-Black Tree, B-Tree 자료구조가 있다.

 

한 노드에 들어갈 수 있는 최대 자료의 수에 따라 M차 B-Tree라고 부른다.

M 차수가 짝수냐 홀수냐에 따라 알고리즘이 다르다는 것이 특징이다.

 

또한, 이러한 자료구조 형을 유지하기 위한 까다로운 규칙들이 존재한다.

규칙에 대해 몇 가지를 살펴보면

1) 노드의 자료수가 N이라면, 자식의 수는 N+1이어야 한다.

2) 각 노드의 자료는 정렬된 상태여야 한다.

3) 루트 노드는 적어도 2개 이상의 자식을 가져야 한다

등등..

 

이미지 출처: 위키 백과, B 트리 

 

이정도만 알아두고 B-Tree 에 대해 자세히 공부해야 할 필요가 있을 경우 더 자세히 알아보려 한다.

 

출처 및 참고

- 위키 백과, B 트리

- https://www.cs.usfca.edu/~galles/visualization/BTree.html