1. 개요

• 2-4 tree는 node 1개에 여러 데이터를 가질 수 있고, 그에따라 자식의 수도 다른 tree이다.

• Node의 데이터는 1개부터 3개까지이고, 자식의 수는 데이터의 수 + 1까지이다.

• 가장 중요한 특징은, 모든 leaf의 depth가 같아야 한다는 점이다.

2. 동작

• 2-4 tree도 search를 O(log n)으로 수행하기 위한 자료구조로, add/remove/search를 지원한다.

• 단, node가 제한은 있지만 여러 데이터를 가지고 있을 수 있고, leaf depth가 유지되어야하기에 add의 경우 promotion, remove의 경우 underflow과정이 필요하다.

• 데이터를 더할 때, 적절한 위치에 데이터를 더한 결과, node의 데이터 수가 제한을 넘는 경우가 발생할 수 있다. 이 경우, node의 중간에 위치하는 데이터를 상위의 node로 보내고, 해당 node를 자식으로 분리하는 과정이 필요하다.

• 데이터를 지울 경우, leaf인지 아닌지, node가 비는지 아닌지, 부모의 데이터 수에 따른 자식 수의 한계를 지키고 있는지, root인지 아닌지에 따라 처리가 달라진다.

출처: https://learning.edx.org/course/course-v1:GTx+CS1332xII+2T2020/home

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.