[자료구조] 2-3 트리
·
CS/자료구조
기본적인 내용은 건너뛰겠습니다. 2-3 트리를 포함한 2-3-4 트리 혹은 Multi-way 탐색 트리 까지 공통점이 있습니다.한 노드에 들어갈 수 있는 자식 노드의 개수가 m개라고 하겠습니다. 1. 루트 노드는 적어도 2개의 자식 노드가 있어야 합니다.2. 모든 leaf 노드는 같은 높이에 위치해야합니다. 즉, 항상 균형잡힌 형태를 유지해야합니다.3. 루트 노드를 제외한 모든 노드는 $\lceil \frac{m}{2} \rceil$ 개의 자식 노드들이 있어야합니다. 이번에 소개할 내용은 2-3 트리이며, m이 3인 트리중 하나라고 할 수 있습니다. 위 공통점에 해당하는 내용을 잘 생각하고 읽어주세요. 아래 예시로 드는 모든 2-3 트리들의 그림은 다음과 같은 공통점이 있습니다. 박스가 하나인 경우 --..