2-3-4 트리에 삽입 할 때 노드를 분할하는 방법?

Question

2-3-4 트리에서 노드를 분할하는 방법에 대한 규칙이 있습니까?

예. 내가 삽입하면 3, 7은 2-3-4 트리로 4, 9 :

이이 (노란색)와 같이 분할 할 것인가 또는 그 (녹색) 다음과 같이 :

둘 다 유효합니까?

Answer 1

녹색. 알고리즘 단계를 고려해야합니다. 삽입 단계는 the wikipedia page을 확인하십시오. 핵심 부분은 다음 삽입을 고려하기 전에 중간 값을 한 단계 위로 이동하여 4- 노드 (3 개의 값이 있음)를 분할하는 것입니다.

1. Insert 3 into blank. Result: 3   (a 2-node) 
2. Insert 7.   Result: 3 - 7  (a 3-node) 
3. Insert 4.   Result: 3 - 4 - 7 (a 4-node) 
5. Insert 9. There is already a 4-node, so this must be split. 
    The split will be to move 4 up a level, and 3 and 7 are now child nodes of 4 
    (like your green diagram). 9 is then added next to the 7.