Tree

image.png

1. 노드(node) 가 하나 이상의 자식을 가지면 tree 라고 한다.

  1. 한 개의 루트 노드만이 존재
  2. 모든 자식 노드는 한 개의 부모 노드만을 가짐
  3. 계층 모델
  4. 부모 - 자식 관계
  5. 비순환 그래프 && 방향 그래프 (top - bottom)
  6. 그래프의 한 종류

2. 트리의 구성 요소

  • Root
    • 부모가 없는 노드 (최상단에 위치한 노드)
    • 한 트리에 단 하나만 존재 (뿌리)
  • Branch
    • 부모와 자식을 모두 가지고 있는 노드
  • Leaf
    • 자식이 없으며 가장 마지막에 있는 노드

Binary Search Tree

아래 gif 참고하면 트리의 효과에 대해 100% 이해 가능
https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#-code-gif

image.png

출처 : http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/bin-tree-review.html

Binary Search Tree 특징

  • 부모의 노드보다 작으면 왼쪽에 데이터가 위치
    • left.node
  • 부모의 노드보다 크면 오른쪽에 데이터가 위치
    • right.node
  • 시간 복잡도 = log
    • 부모부터 시작하여 부모보다 데이터가 크면 왼쪽을 탐색, 아니면 오른쪽을 탐색 (재귀함수 사용)