DataStructure - 트리, 이진 트리란?

트리 자료구조란?

• 상위 노드와 하위 노드로 구성됨.
• 가장 상위에 위치한 노드를 루트(root)라고 함.

이진 트리란?

• 하위 노드를 2개까지 가질 수 있는 트리.
• 이진 탐색 트리: 왼쪽 하위 노드가 더 작은 값을 가지고 오른쪽 하위 노드가 더 큰 값을 가지는 것.
  • 트리가 한쪽으로 치우치면 선형 탐색과 동일한 성능 O(n)이 나옴.

이진 탐색 트리

삽입

• 데이터를 입력한 시점에 정렬해서 보관함.
  • 루트를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브트리에 삽입됨.

검색

• 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬된 상태에서 검색이 진행됨.
  • 이때문에, 매 단계마다 탐색 범위가 절반으로 줄어듦.
  • 빅오 표기법: O(log n)

순회

• 이진 트리 자료 구조는 데이터의 값을 기준으로 정렬해서 보관함.
  • 정렬되어 있기 때문에 정렬된 순서로 데이터를 차례로 조회 가능함.
    • 정렬된 데이터를 차례대로 조회하는 것을 순회한다고 표현함.
  • 데이터를 차례로 순회하기 위해선 중위 순회를 사용하면 됨.
    • 왼쪽 서브트리를 방문한 후 현재 노드를 처리하고 마지막으로 오른쪽 서브트리를 방문함.
      • 이진 탐색 트리의 특성상 노드를 오름차순으로 방문하게 됨.