(2,3,4) Tree

자식 노드의 개수가 최소 2개 ~ 최대 4개인 탐색트리

• (2,3,4) 트리의 높이가 h, 노드의 개수가 N일 때,

  	log(4)N <= h <= log(2)N

연산

Insert

• key값의 삽입은 leaf node에서만 이루어진다.
  * root 노드에서부터 삽입될 위치를 탐색하면서, 노드가 4-노드(자식노드가 4개)일 경우 노드를 split한다.
• Split : 확인하는 노드가 (15,18,25) 라면, 가운뎃값 18을 윗 노드로 올리고, (15,,), (25,,) 두 노드로 쪼갠 후, key가 삽입될 위치를 탐색한다. (root노드가 4노드라면 가운뎃값이 올라가서 새 root가 된다.)

Delete

• 삭제할 key값의 위치를 탐색 후, predeccessor(키값 다음으로 작은 수) 혹은 successor(키값 다음으로 큰 수)의 위치를 찾아 swap 후 삭제한다.
  * swap되는 위치의 노드가 2-노드(swap된 키값만 있는 노드)일 경우, 이 노드가 삭제되면 다른 child노드의 링크가 끊기는 현상이 발생할 수 있다.
  이를 방지하기 위해 root 노드에서부터 삭제할 키값의 위치를 탐색하면서, 2-노드를 만나면 형제 노드에서 값을 가져와 3-노드로 fusion해주는 작업이 필요하다.
  (만약 양 옆 형제가 모두 2-노드라면, 부모노드 값을 내려 4-노드로 fusion한다.)

Red-Black Tree와의 연관성

2-노드는 h = 1인 Black 노드 1개, 3-노드와 4-노드는 2레벨에 걸쳐 1레벨은 Black, 2레벨은 Red인 노드로 변환시킬 수 있다.

따라서, (2,3,4) 트리의 레벨 하나 당, Red-Black Tree의 경로 상 Black노드가 하나씩 추가된다.