트리

비선형 구조의 여러 구조 중 단방향의 한 구조, 그래프인데 단방향인 거임, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있음

특징

• 비선형 구조
  • 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조
• 사이클이 없음
  • 사이클: 시작 노드에서 출발해 다른 노드를 거쳐 시작하는 것
  • 트리는 사이클(cycle)이 없는 하나의 연결 그래프 (Connected Graph)
• 용어 - 노드: 트리 구조를 이루는 모든 개별 데이터
  • 트리는 '루트' 노드부터 시작해 그 자식인 '자식' 노드, 자식이 또 부모가 되는 '부모'노드, 자식끼리는 '형제' 노드, 제일 막내 노드는 '리프' 노드
• 측정데이터:
  • 깊이(depth): 루트 노드 0부터 시작해서 자식 노드로 하나씩 내려갈 때마다 깊이가 1씩 증가
  • 레벨(Level): 같은 깊이들을 묶어 레벨로 표현
  • 높이(Height): 리프 노드 0부터 시작해 부모 노드로 하나씩 올라갈 때마다 높이가 1씩 증가
  • 서브 트리: 트리 구조를 갖춘 작은 트리를 서브 트리

예시

• 컴퓨터의 디렉토리 구조: 모든 폴더는 하나의 폴더(루트 폴더, /)에서 시작되어, 가지를 뻗어나가는 모양새
  
• 가계도
• 회사 직책
• 월드컵 토너먼트 대진표

이진 트리

효율적인 탐색을 위해 고민하여 나온 것이 이진 트리다!

자식 노드가 최대 두 개인 노드들로 구성된 트리, 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눔

특징

자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나눈다!

• 정 이진 트리 : 각 노드가 0개 혹은 2개의 자식 노드를 가짐.
• 포화 이진 트리 : 정 이진 트리이면서 완전 이진 트리인 경우. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리.
• 완전 이진 트리 : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 함.

이진 탐색 트리

Binary Search Tree, 이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 이진트리

• 각 노드에 중복되지 않는 키(Key)가 있음.
• 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있음.
• 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있음.
• 좌우 서브트리도 모두 이진 탐색 트리여야 함.
  단점: 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있음, 해결하고 싶다면 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가해야한다!

즉, 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징을 가진다!

특징

• 효율성: 기존 이진 트리보다 탐색이 빠르다는 장점
  • 트리의 높이가 h(height)라면 o(h)의 복잡도
• 탐색 과정: 원하는 값이 나올 때까지 반복해 진행!
  • 루트 노드의 키와 찾고자 하는 값을 비교. 만약 찾고자 하는 값이라면 탐색을 종료.
  • 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행.
  • 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행.

예시

5라는 값을 찾고자 한다.

1. 제일 처음에는 루트 노드와 값을 비교
2. 루트 노드가 여기서는 10이므로 루트노드보다 작기 때문에, 왼쪽 서브 트리로 탐색 시작
3. 마주친 노드는 7이고, 찾고자 하는 값은 5이므로 다시 7을 기준으로 왼쪽 서브 트리로 탐색 진행
4. 만난 값이 찾고자 하는 값이므로 탐색이 종료

만약 3을 찾는다면 4번의 연산이 진행되었을 것. 즉! 트리 안의 값을 찾는다면 무조건 트리의 높이(h) 이하의 탐색

핵심: 트리 안에 찾고자 하는 값이 없더라도 최대 h번의 연산 및 탐색이 진행

1. 만일 13이라는 숫자를 찾는다고 가정. 마지막으로 도착하는 노드의 값은 14인데, 여기서 13은 14보다 작으므로 왼쪽 서브 트리로 탐색을 진행
2. 오른쪽 서브 트리가 없으므로 14에서 탐색이 종료

즉! 최대 h번의 연산 및 탐색이 진행 - 트리의 높이(h) 이하의 탐색, 시간복잡도는 O(h)!

트리 순회

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것, 모든 노드를 방문하기 위해서 일정한 조건이 필요, 트리 구조를 유지보수하거나 특정 목적을 위해서도 순회 방법에 대한 정의는 필수적으로 필요

종류

1. 전위 순회 (preorder traverse)
   맨위 루트부터 자식으로 순회, 주로 부모 노드가 먼저 생성되어야 하는 트리를 복사할 때 사용
2. 중위 순회 (inorder traverse)
   루트를 중간에 순회, 부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식. 중위 순회는 이진 탐색 트리의 오름차순으로 값을 가져올 때 쓰임
3. 후위 순회 (postorder traverse)
   루트를 가장 마지막에 순회, 후위 순회는 트리를 삭제할 때 사용. 자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문
4. 레벨 순회

구현