Multi-way Tree

Multiway Tree는 BST의 변형이라고 생각하면 된다.

• Binary Search Tree?
  
  모든 노드의 left sub tree들은 해당 노드의 값보다 작은 값들만 가지고,
  모든 노드의 right sub tree들은 해당 노드의 값보다 큰 값들만 가진다.
  

• Multiway Search Tree?
  
  한 Node 내에 최대 m-1개의 요소와 m개의 자식을 갖는 Tree 구조
  

Q. 그렇다면 Multiway Search Tree의 특징은 무엇일까?

① 각 노드 내부의 원소들(keys)은 오름차순으로 정렬
② 각 원소 사이의 sub tree에 포함된 모든 값은 해당 원소 사이의 값을 가지도록 설계

Multiway Search Tree 예시

지금까지 Multiway tree가 무엇인지 알아봤는데, 이를 사용하는 장점은 무엇인지 살펴보자.
장점 : 각 노드에 저장되는 원소의 수를 늘림으로써, Tree의 높이를 줄일 수 있다는 장점이 존재

자료구조 중 선형이 아닌 비선형의 tree를 기준으로 아래와 같이 살펴봤다.

Multiway Tree의 활용

Multi-way Tree는 어디에 쓰일까?

바로 문자열 탐색에 주로 쓰인다.
Lexical Search Tree라고 하는데 아래와 같이 A to Z의 key값들을 통해 단어장과 같이 구성할 수 있는 것이다.

이러한 문자열은 Multi-way Tree에 너무나 적합하다.

하지만 이 Lexical Search Tree는 단점이 존재한다. 바로 A to Z까지 모든 Key값들을 보유하고 있어야 한다는 것이다. 즉, 쓸모 없는 공간이 너무나 많이 생겨버리게 된다.

=> 이를 보완하기 위해 나온 것이 바로 Trie 다.

이 Trie는 Lexical Search Tree와 유사하지만, A to Z의 단점을 보완하고자 단어가 들어올 때 마다 단어를 하나씩 저장하며 link를 뻗어나가 단어장을 구성하게 된다.

이를 통해 비효율적인 공간을 줄일 수 있게 되는데, 예시를 한 번 살펴보자.

'abc', 'ab', 'car' 단어들을 'abc'부터 트라이에 하나씩 저장해보자.

우선 head 노드가 있을 것이다.

a의 key값을 생성함과 동시에 다음 b의 자식노드 링크를 걸어준다.

b의 key값을 생성함과 동시에 다음 c의 자식노드 링크를 걸어준다.

c의 key값을 생성함과 동시에 c로 도착했기에 abc라는 단어를 data로 저장해주면 된다.

이렇게 단어장에 하나의 단어가 저장되었다!

이번에는 ab 를 저장할건데, head node에서 이미 자식노드로 a가 있기에 따라가고 다시 a에서는 b라는 자식노드가 있기에 따라간 후 ab라는 단어를 data로 저장한다.

이렇게 단어장에 ab라는 단어가 저장되었다!

마지막으로 car를 저장해보자.

car는 처음에 head node에서 c라는 자식노드를 가리키게 만들고, c에서 a로 a에서 r로 key와 link를 만들며 따라간다. 그 후 r에 도착했을 때, car라는 단어를 저장해주면 되는 것이다.

이렇게 단어를 하나하나 key와 link를 따라 구성하며 단어를 저장하고 단어장을 구상하면 되는 것이다!