2016/2/16

[S9S99]

진행 상황

• p.486 ~ p.492

  내용 정리

• 2-3-4 Trees and Red-Black Trees
  • 레드블랙 트리와 234 트리는 사실상 같은 형태로 서로 변형이 가능
  • 2-node를 검은색으로, 3-node는 부모자식 관계로 (어느쪽이 부모가 되든 상관 없음) 부모가 검정, 4-node는 가운데가 부모+블랙이 되고 좌우 자식이 되는 형태로 변형해서 레드블랙 트리로 만들 수 있다.
  • 분할과 회전도 비슷한 형태로 동작
• Efficiency of 2-3-4 Trees
  • 균형 잡혔을 경우 레드블랙과 마찬가지로 O(logN)
  • 데이터 항목이 적은 노드들은 공간 낭비가 발생. 평균 2/7 정도가 낭비