StudyData Structure

균형 이진 트리(balanced-binary tree)

  • 이진 탐색 트리(BST)는 O(log(n))의 시간 복잡도를 가진다.
  • 이것은 탐색 트리가 균형 트리일 경우에만 해당된다.
출처 : https://github.com/ythwork/CS
  • 위 그림처럼 최악의 경우, O(n)의 시간 복잡도를 가지게 된다.

균형 이진 트리

  • self-balancing(balanced-binary tree)
  • 균형 이진 트리의 종류
    • AVL tree
    • Red - Black tree
  • AVL tree와 Red - Black tree 모두 Rotation 기반이다.
확장 이진 트리
레드 블랙 트리(Red - Black tree)
출처:https://github.com/ythwork/CS
  • 모든 노드의 컬러가 레드 혹은 블랙인 이진 탐색 트리
  • 균형 이진 트리
  • 루트 노드와 외부 노드의 컬러는 블랙
  • 루트 노드에서 외부 노드로의 경로 중에 레드 노드가 연속으로 나올 수 없다.
  • 루트 노드에서 외부 노드로의 모든 경로에서 블랙 노드의 수는 같다.
  • 다음 사이트에서 레드 블랙 트리 동작을 확인할 수 있다.

메모리 계층

출처:https://github.com/ythwork/CS
  • 메모리에서는 Red - Black tree 만으로도 충분하다.
  • 대량의 데이터를 처리하는 HDD에서는 B-tree가 적합하다.
  • B-tree의 경우
    • tree의 높이(height)를 줄여서 메모리 접근을 줄이고 비교 회수를 늘림
    • 외부 노드는 모두 같은 레벨이어야 한다.
    • insert를 할 때는 split 연산을 한다.

Tree 정리

  1. 순회

    • 전위 순회 - Stack
    • 중위 순회 - Stack
    • 후위 순회 - Stack
    • 레벨 순회 - Queue

  2. BST

    • insert, search, delete = O(log(n))
    • 최악의 경우 = O(n)

  3. Red-Black Tree

    • 균형 이진 트리
    • rotation
    • O(log(n))

  4. B-Tree

    • 대량의 데이터를 처리하는데 이용
    • 메모리의 접근 회수를 줄이고 비교 회수를 늘림
Share