12,13 멀티웨이 탐색 트리

m원 탐색트리

   - 자식노드를 m개 까지 가질 수 있는 트리

  - 같은 수의 노드를 갖는 이진탐색트리보다 낮은 높이의  m원 트리

  - 하나의 노드에 여러개의 키값을 가져서 자식노드를 여러개 갖음 (3원탐색트리는 키값 2개 필요)

왼쪽 서브트리는 86보다 작은 애들

중간에는 86보다크고 90보다 작은애들

오른쪽서브트리는 90보다 큰 애들로 만든 서브트리

m원 트리는 서븥트리의 균형은 고려하지않음

 

 

B 트리

m원탐색트리를 개선한 B트리는 인덱스 구조를 구현하는데 가장 일반적으로 활용함  . 전체적으로 균형을 유지

-루트와 잎노드를 제외한 트리의 각 노드는 최소 [m/2] 개의 서브트리를 갖는다.

- 트리의 루트는 최소한 2개의 서브트리를 갖는다

- 트리의 모든 잎 노드는 같은 레벨에 있다.

B* 트리

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

 - 노드가 꽉 차면 분리하지않고, 키와 포인터를 재배치하여 다른 형제노드로 옮김

 -  B트리와 동일한 수의 노드를 갖는다면 높이가 낮고 삽입/삭제시 발생하는 노드분리를 줄이려고 고안됨

 - 모든 잎노드는 동일한 레벨에 놓임

B+ 트리

-잎노드를 순차적으로 연결하는 포인터 집합이 있다

- 잎노드의 마지막 포인터를 다음 키값을 갖는 노드를 가리킴

-순차 처리를 할때 이 포인터를 이용해서 차례로 다음 데이터에 접근해서 처리

- B트리와 같이 각 노드의 키가 적어도 1/2이 채워져야하는 점은 같음

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

 

ㅌ

2-3트리

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

 - 2-노드(2개의 자식 노드;차수가2) 와 3-노드만(3개의 자식노드;차수가3)으로 구성되는 특수한 형태의 B트리

-  2-노드 혹은 3-노드라는 제약이 내부노드에만 해당함 => 모든 잎노드는 같은 레벨에 있어야하는 제한만 존재

- 모든 잎 노드는 같은 레벨에 있다.

2-3-4트리

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

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

 

레드블랙트리

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

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

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

- 블랙간선은 2-3-4트리의 부모자식관계임