[자료구조#12, 13] 멀티웨이 탐색트리

m원 탐색 트리

노드의 가지 개수가 많을 수록 최대 탐색 길이는 짧아짐

 

B트리

 

 

 

 

 

 

 

 

B*트리, B+트리

B* 트리

- 노드의 약 2/3 이상이 채워지는 B트리

-

 

 

 

B+트리

- 탐색 트리로 구성하면 매우 빠르게 탐색할 수 있지만 전체 데이터를 차례로 처리하기는 불편함

- 잎노드를 연결하는 포인터를 가짐

- 모든 키값이 잎노드에 있고 그 그 키값에 대응하는 실제 데이터 (파일 내용)에 대한 주소를 잎노드만이 가지고 있음

 

2-3트리

차수가 2 또는 3인 내부 노드를 갖는 탐색 트리

2-노드와 3-노드만으로 구성되는 특수한 형태의 B 트리

2-3-4트리

2-3 트리를 확장하여 4개의 자식을 가진 4-노드를 허용하는 탐색 트리

2-3 트리보다 삽입과 삭제가 용이

삽입 및 삭제 연산을 수행하는데 더 효율적

 

레드 블랙 트리

효율적인 기억 장소 사용을 위해 2-3-4 트리를 이진트리로 나타낸 것

레드 간선과 블랙 간선의 서브트리 포인터를 가짐

레드 간선은 2-3-4 트리의 한 노드 내에 있던 노드 관계

블랙 간선은 2-3-4 트리의 부모 노드