2016/2/8

[S9S99]

진행 상황

• p.463 ~ p.475

  내용 정리

• 2-3-4 Trees and External Storage
  • 노드 당 4개의 자식과 3개의 아이템을 가지는 다중 경로 트리
• Introduction to 2-3-4 Trees
  • 하나의 데이터 항목이 있는 노드에는 두개의 자식, 둘일 경우 자식은 셋, 데이터가 셋이면 자식은 넷
  • 빈 노드는 허용되지 않음
  • 자식 0의 데이터는 모두 부모의 0번째 값 보다 작은 값, 자식 1은 부모의 0과 1 사이, 자식 2는 부모의 1과 2 사이, 자식 3은 보모의 2 보다 큰 값을 가지고 있다
• Searching a 2-3-4 Tree
  • 검색은 이진트리와 유사. 검색 값이 없으면 검색 값 범위의 하위 트리로 이동하는 형태
• Insertion
  • 삽입은 항상 맨 아래 행에 삽입 됨
  • 삽입 시 노드 내부에서 값 이동 가능
• Node Splits
  • 삽입 지점에서 가득찬 노드를 발견하면 노드를 분할해야함
  • 분할을 통해 트리의 밸런스를 유지
  • (왼쪽부터 A, B, C) 비어 있는 형제 노드가 오른쪽에 생성되서 C가 이동되고 B는 부모로 이동, A는 현위치. 그리고 가장 오른쪽에 있는 자식노드가 두개 분리 되서 C가 있는 새 노드의 자식이 됨
  • 데이터를 오른쪽으로 이동시킨다는 느낌
• Splitting the Root
  • B가 루트가 되고 A와 C가 각각 왼쪽 오른쪽 자식이 되어 기존의 자식 중 오른쪽 두개를 C가 가져간다