2-3 트리에 삽입하는 올바른 방법은 무엇입니까?

Question

수업 강사가 2-3 나무에서 삽입을 수행하는 질문을 받았습니다. 내가 무슨 짓을

는 상위 방법이었다. 그리고 그가 원했던 것은 아래의 방법입니다. 당신은 웹을 보았을 때 올바른 방법이 무엇인지 말해 주시겠습니까? 그리고 두 가지 방법을 모두 볼 수 있습니다. 그러나 나는 왜 내가 10 점을 잃었는지 모르겠다! 도움에 미리 감사드립니다.

Answer 1

2-3 개의 나무가 여러 가지 버전으로 나뉘어져 있다고 말하기 시작하면 혼란 스러울 수 있습니다. 실제로 상점 가치가 다른 점만 다릅니다. 일부는 모든 노드의 리프 값과 다른 저장소 값의 값만 저장합니다.

나는 선생님이 2-3 나무에 대해 후자의 정의를 사용하고 있다고 생각합니다. 따라서 트리의 문제는 "루트"노드가 자식 노드와 동일한 값을 가지므로 노드는 자식 노드와 동일한 값을 공유하지 않습니다. 나는 선생님이 제공 한 것이 진정한 2-3 나무라고 생각하지 않습니다. 노드가 3 개의 값을 포함하면 2-3 트리가 나뉘어집니다.

트리에 추가 4 :

(4) 

트리에 칠을 추가

(4,7) 

트리에 추가 6 :

(4,6,7) 
*splits* 
    (6) 
(4) (7) 

나는 적절한 출력 아래 기대 루트 노드가 3 개의 값을 얻으면 1-2 개의 트리로 나눕니다.

는 8 삽입한다면 : 당신이 구를 삽입한다면

(6) 
(4) (7,8) 

을 :

(6) 
(4) (7,8,9) 
*push-up* 
    (6,8) 
(4) (7) (9) 

루트가 아닌 노드 GET의 3 개 값; 중간 값을 상위 값까지 밀어 넣으면 값을 밀어 올리면 부모 값이 3이되어 부모가 분할됩니다.