자료 구조 - 비선형 자료 구조 (트리)

참고 링크

트리

그래프의 일종

트리에서의 정점을 노드라고하고 간선을 가지라고 한다

관련 용어

• 노드(Node)
  • 그래프의 정점에 해당하는 것
  • 루트 노드
    • 트리의 기준이 되는 노드
    • 나무의 뿌리와 유사
    • 루트 노드 위에 가지가 뻗어있다는 이미지
  • 부모 노드
    • 어떤 노드에서 자신과 인접한 노드들 중 루트 노드로 향하는 노드
  • 자식 노드
    • 어떤 노드에서 자신과 인접한 노드들 중 루트 노드의 반대 방향으로 향하는 노드
  • 단말 노드
    • 자식 노드가 존재하지 않는 노드
    • 가지의 끝
  • 형제 노드
    • 부모 노드가 같은 노드
• 가지(Branch)
  • 그래프의 간선에 해당하는 것
  • 트리에서는 양방향 간선만 사용
• 부트리(Sub Tree)
  • 부분 그래프와 비슷하게 정의
• 차수(Degree)
  • 자식 노드의 개수
• 길이(Length)
  •  임의의 두 노드를 시작, 도착 노드로 하는 경로에 거치게 되는 노드의 수
• 깊이(Depth)
  • 루트 노드에서 해당 노드까지의 길이
• 레벨(Level)
  • 깊이가 같은 노드의 집합
• 높이(Height)
  • 가장 깊이가 깊은 단말 노드까지의 길이

종류

• 이진 트리
  • 모든 노드의 차수가 2이하인 트리
• 전 이진 트리
  • 모든 노드의 차수가 0또는 2인 트리
• 포화 이진 트리
  • 모든 단말 노드의 깊이가 같은 이진 트리
• 완전 이진 트리
  • 모든 단말 노드의 깊이의 최댓값과 최솟값의 차이가 0또는 1인 이진 트리

순회 알고리즘

전위 순회

그래프에서의 깊이 우선 탐색과 같음

중위 순회

후위 순회

레벨 순서 순회

그래프에서의 너비 우선 탐색과 같다

이진 검색 트리

이진 검색이란 일자로 나열된 정렬된 데이터에서 원하는 데이터를 빠르게 찾는 방법

최악의 경우에 O(log n)를 보장하는 매우 유용한 알고리즘

정렬을 필수로한다

이진 검색 트리는 이진 검색에 용이하게 데이터를 다음과 같은 방법으로 이진트리로 구성한 것을 말함

1. 일렬로 나열된 데이터들 중 가장 중앙에 위치한 하나의 데이터를 M이라고 하고 M왼쪽에 위치한 데이터들을 L, 오른쪽에 위치한 데이터를 R이라 하자
2. L과 R이 M을 부모로 가지는 트리를 구성
3. L과 R에 대해서도 각각 같은 방법으로 트리를 구성

이진 검색

이분 탐색과 동일한 알고리즘

오름차순 정렬된 자료를 기준으로함

이진 검색 트리의 루트 노드부터 방문하며, 다음 순서에 따라 노드를 방문한다

• 방문한 노드가 찾는 값이라면 검색 성공
• 방문한 노드가 단말노드이고 찾는 값이 아니라면 검색 실패
• 방문한 노드가 단말노드가 아니고 찾는 값이 아니라면
  • 방문한 노드의 값을 x, 찾는 값을 v라고 할때
    • x<v
      • 방문한 노드의 오른쪽 자식을 방문
    • x>v
      • 방문한 노드의 왼쪽 자식을 방문

여기에서도 위에서와 같이 노드가 저장된 값에 특정한 규칙이 있어야 함에 주의해야함