2016/2/7

[S9S99]

진행 상황

• p.437 ~ p.460

  내용 정리

• Red-Black Trees (이어서)
  • Rotations를 통해서 트리의 밸런스를 맞춤
  • 일부 노드를 올리고 다른 노드를 내리며 규칙 위반을 검사하는 과정
  • 오른쪽 회전의 경우 선택된 최상위 노드를 그 자신의 위치에서 오른쪽 자식 위치로 이동하고 선택된 최상단 노드의 왼쪽 자식을 최상단으로 이동 시킴(트리를 이미지로 본다면 마치 트리 전체가 오른쪽으로 회전하는 형태의 이동이 발생)
  • 왼쪽 회전은 그 반대.
  • 회전 시 색상 규칙 위반은 일단 무시
  • 삽입 시 붉은 아이를 둘 가진 검은 노드를 발견할 때 마다 color flip로 색상을 변경해서 색상 규칙을 유지함
  • 해당 교재의 내용만으로는 실제 구현이나 이해하기가 조금 힘드니 치후 인터넷 강의와 추가 자료로 복습 예정☆
• The Efficiency of Red-Black Trees
  • 각 노드에 색상을 저장하기 위한 부울 변수가 들어가는 것 이외에는 이진 트리와 동일.
  • 삽입 시 회전이 동작하기 때문에 이진트리와 같은 O(logN)이지만 시간이 조금 더 걸림
  • 밸런스가 잡혀있기 때문에 이진트리의 최악인 O(N)까지 성능이 떨어지지 않는 장점
• Other Balanced Trees
  • AVL, 2-3-4 트리 등이 존재하고 해당 교재에서 이후에 학습 예정