[CS] 지식 - 4 (자료구조-Tree)

Tree

Tree

의미 및 특징

• node와 branch로 구성된 비선형 자료구조
• 원소들 간에 1:n 관계 및 계층관계를 갖는 자료구조
• 하위 트리는 subtree가 될 수 있다.
• 뻗어나간 정점들은 다른 정점과 연결되지 않는다.
• 데이터의 값에 따라 자리가 정해져, 자료의 탐색, 삽입, 삭제가 효율적이다

Binary Tree, 이진 트리

의미 및 특징

• 최대로 가질 수 있는 차수가 2인 트리(자식 노드가 2개)

  종류

• 포화 이진 트리(perfect binary tree)
  • 모든 레벨에 노드가 포화 상태로 차 있는 이진 트리
• 완전 이진 트리(Complete Binary Tree)
  • 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리
  • 마지막 레벨의 모든 노드는 최대한 왼쪽부터 채워져야 한다.
• 편향 이진 트리(Skewed Binary Tree)
  • 왼쪽 편향 이진 트리, 오른쪽 편향 이진 트리
  • 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리
• 이진 검색 트리
  • 근노드와 비교하여 값이 작으면 좌측, 값이 크면 우측으로 연결하여 구성한다.
  • 정렬이 완료된 데이터를 이진 검색 트리로 구성할 경우, 사향 이진 트리가 되고 비교 횟수가 선형 검색과 동일해 진다.