Day3

DAY3 - TREE (AVL TREE, RB TREE)

공부한것

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

TODO

• B+ TREE
• B* 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.노드는 레드 혹은 블랙 중의 하나이다.
  • 2. 루트 노드(시작점)은 블랙이다.
  • 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

  • 단어를 정렬된 트리에 저장시킴

• Treap

  • BST 가 밸런스를 맞추지 못하는 문제를 해결하기위해 값에 대한 랜덤 값을 주어서 균형을 마추도록 한다.
  • 삽입 삭제될때 랜덤으로정해진 priority 를 이용해 삽입 삭제가된다. 랜덤값이 잘 분포되어있으므로 어느정도 균형을 맞춘다.

• SkipList

  • 링크드 리스트 인데 n 개의 next 포인터를 가져서 빨리 찾음

이야기하면 좋은 내용

• Downcasting
• @SuppressWarnings("unchecked")