Addition. 2-3-4 Trees

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요.

Add2. 2-3-4 Trees

- 추가로 4-노드 정의

- 자식 노드로 가는 링크가 4개이고, 키가 3개인 노드

- 2-3-4 트리를 쓰는 이유??? ⇒ 단일 패스 삽입 ⇒  레드-블랙 트리와의 연관성

  ( 조금 더 간단, 공간이 많아서 쉬움 (내가 필기 한건데 왜인지 아직 이해 못함))

  * 2-3 트리는 리프노드가 꽉 차면 중간 자식을 부모노드로 올리고, 만약 부모노드가 꽉 차면

    다시 부모노드의 중간 자식이 그 위로 올려짐.

  * 2-3-4 트리는 이러한 사태를 배제하기위해, 루트로 부터 삽입위치를 찾아서 내려가는 도중에

     4-노드를 만나면 무조건 제거하면서 내려감

  * 스택이 필요없음 ( 위에서부터 check)

  * 하나의 삽입 작업이 트리 모습을 바꾸면서 내려가는 동안, 동시에 이어서 두 번째 삽입 작업이

    루트로부터 내려올 수 있음 (파이프 라이닝)

 

 - 삽입시 4-노드의 제거

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요.