🍀 Knowledge/자료구조
[자료구조] 탐색 트리 : 2-3 트리, B 트리에 관하여
2-3 트리 2-3 트리 정의 2-3 트리는 내부 노드의 차수가 2 또는 3인 균형 탐색 트리 차수가 2인 노드는 2-노드라고 부르고, 차수가 3인 노드는 3-노드라고 부른다. 2-노드는 1개의 키를 가지며, 3-노드는 2개의 키를 가진다. 2-3 트리는 루트로부터 각 이파리까지 경로의 길이가 같고, 모든 이파리가 같은 층에 있는 완전 균형 트리이다. 2-3 트리가 2-노드들로만 구성되면 포화 이진 트리와 동일한 형태를 가진다. 2-3 트리에서 중위 순회를 수행하면 키들이 정렬된다. 2-3 트리의 연산 탐색 연산 루트에서 시작하여 방문한 노드의 키들과 탐색하는 키를 비교하며 다음 레벨의 노드를 탐색한다. 삽입 연산 먼저, 탐색과 같은 과정을 거쳐 새로운 키가 삽입될 이파리를 찾아야 한다. 이파리를 찾았다..
