[자료구조] 6. 트리 (Tree)

Romy·2021년 12월 13일
0

자료구조

목록 보기
7/8
post-thumbnail

✅ 구조

  • Node로 구성된 계층적 자료구조
  • Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조

✅ 용어

  • Node : 트리에서 데이터를 저장하는 기본 요소
    (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
  • Root Node : 트리 맨 위에 있는 노드
  • Level : 최하위 노드를 level0으로 하였을 때 하위 Branch로 연결된 노드의 깊이
  • Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
  • Child Node : 어떤 노드의 상위 레벨에 연결된 노드
  • Leaf Node : Child Node가 하나도 없는 노드
  • Slibing : 동일한 Parent Node를 가진 노드
  • Dept : 트리에서 Node가 가질 수 있는 최대 Level

✅ 이진트리

  • 이진트리 : 노드의 최대 Branch가 2인 트리
  • 이진탐색트리 : 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노트보다 큰 값을 가지고 있는 이진트리

장점

  • 탐색 속도를 개선할 수 있음

단점

- 평균 시간 복잡도는 O(logn)이지만, 위와 같이 한 개의 branch로만 연결되어 있게 구성되어있을 경우 링크드 리스트와 동일한 성능을 보여줌 O(n)

주요 용도

: 데이터 검색 (탐색)

시간복잡도

  • depth를 h라고 표기한다면 O(h)
  • n개의 노드를 가진다면 h = log2n에 가까우므로 시간 복잡도는 O(logn)
profile
👩‍💻 IT Engineering

0개의 댓글