다원 탐색 트리 (Multiway search tree)
다원 탐색 트리(Multiway search tree)는 m-원 탐색 트리 (m-way search tree)라고도 합니다.
다원 탐색 트리는 한 노드안에 최대 m-1개의 요소와 m개의 자식을 가질 수 있습니다.
이진 탐색 트리는 m=2 인 다원 탐색 트리입니다.
다원 탐색 트리의 특징
다원 탐색 트리는 다음과 같은 특징이 있습니다.
1. 각 노드는 아래의 개수만큼 서브 트리를 갖습니다.
\(0 ≤ 서브트리 개수 ≤ m\)
2. k 개의 자식 노드를 가지는 노드는 k-1개의 요소를 갖습니다. (k ≤ m)
3. 각 노드 안에 있는 키는 오름차순으로 정렬되어 있습니다.
\(key_1 ≤ key_2 ≤ ... ≤ key_{(k-1)}\)
4. 다음 조건을 항상 만족합니다.
i 번째 key ≤ i 번째 서브 트리 내의 모든 키 값 < i+1 번째 key
5. 모든 서브 트리는 m-원 탐색 트리입니다.
장단점
트리의 높이를 h라 하면 트리의 작업 속도는 O(h)입니다.
h 높이를 낮춤으로써 작업 속도를 높일 수 있습니다. 노드에 저장할 수 있는 요소의 수를 늘림으로써 트리의 높이를 줄일 수 있습니다.
다원 검색 트리는 이진 검색 트리보다 많은 요소를 저장할 수 있어 낮은 높이를 유지할 수 있습니다.
다원 탐색 트리는 스스로 균형을 유지하지 못하기 때문에 불균형이 발생할 수 있다는 단점이 있습니다. 이럴 경우 검색 성능이 떨어지게 됩니다.
다윈 탐색 트리의 단점을 보완하기 위해 스스로 균형을 유지하는 기능이 필요합니다.
대표적으로 b-tree가 있습니다.
