[기술면접/자료구조] 다원 탐색 트리 (Multiway Search Tree)

다원 탐색 트리 (Multiway Search Tree)에 대해 설명하세요

Keyword

sub tree 개수,요소의 개수,요소 내부 오름차순,균형, Tree height

Script

Multiway Search Tree는 한 Node 내에 최대 m-1개의 요소와 m개의 자식을 갖는 Tree 구조입니다. Binary Search Tree는 이 m 값이 2인 Tree라고 할 수 있습니다. 이 때 각 노드 내부의 원소들은 오름차순으로 정렬되어있고, 각 원소 사이의 sub tree에 포함된 모든 값은 해당 원소 사이의 값을 가지도록 설계되어있습니다. 각 노드에 저장되는 원소의 수를 늘림으로써, Tree의 높이를 줄일 수 있다는 장점이 있습니다.

Additional

k 개의 자식 노드를 가지는 노드는 k-1개의 요소를 보유

각 노드 안에 있는 키에 따라 정렬

Sub Tree의 key 값

Binary Search Tree와의 비교