3주

1. AVL TREE - 균형 마추기
2. RED-BLACK TREE - 기본 원리 구현
3. RED-BLACK 이용한 TREEMAP Collection 구현
4. TREE 를 이용한 산술

이론

회전

• 왼쪽 회전
  • X 의 오른쪽 노드를 X 자리로 옴기고 X 를 옴겨진 노드에 왼쪽으로 옴김

     A               C
    / \       ->    / \
   B   C           A   E
      / \         / \
     D   E       B   D

• 오른쪽 회전
  • X 왼쪽 노드를 X 자리로 옴기고 X 를 옴겨진 노드에 오른쪽으로 옴김

     A               B
    / \       ->    / \
   B   C           D   A
  / \                 / \
 D   E               E   C

AVL

• 회전 정리

    /      /      \      \
   /       \      /       \
  <LL>    <LR>   <RL>     <R>

• X 의 왼쪽 자식의 왼쪽 부속트리에 노드가 삽입된 경우 (LL)
  • ROTATE_LEFT(X)

• X 의 왼쪽 자식의 오른쪽 부속트리에 도드가 삽입된 경우(LR)
  • ROTATE_LEFT(X.LEFT) -> ROTATE_RIGHT(X)

• X 의 오른쪽 자식의 왼쪽 부속트리에 노드가 삽입된 경우(RL)
  • ROTATE_RIGHT(X.RIGHT) -> ROTATE_LEFT(X)

• X 의 오른쪽 자식의 오른쪽 부속트리에 노드가 삽입된 경우(RR)
  • ROTATE_RIGHT(X)

Red-Black Tree

• 조건
  • 1.노드는 레드 혹은 블랙 중의 하나이다.
  • 1. 루트 노드(시작점)은 블랙이다.
  • 3.모든 leaf node는 블랙이다.
  • 4.레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. 그러므로 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다.
  • 5.어떤 노드로부터 시작되어 leaf node에 도달하는 모든 경로에는 leaf node를 제외하면 모두 같은 개수의 블랙 노드가 있다.

심화내용

• Segment Tree
  • 특정 구간에 대한 질문을 빠르게 답하는데 사용됨
  • 배열에 구간의 합을 미리구해서 특정지점부터 특정 지점까지 합을 쉽게 구함
• Binary Indexed Tree(or Fenwik Tree)
  • Segment Tree 에 이진수를 이용해 업그레이드 시킴
• Splay Tree
  • self-adjust BST
• IntervalTree
• Trie
  • String 을 정렬해서 트리에 저장

이야기하면 좋은 내용

• Downcasting
• @SuppressWarnings("unchecked")