Tree

1. Tree의 정의

• 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮음

• 데이터가 바로 아래에 있는 하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결된 계층적 자료구조

• 데이터를 순차적으로 나열시킨 선형구조가 아닌, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조

• 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없음

• 즉, 사이클이 없는 하나의 연결 그래프라고 할 수 있음

2. Tree의 구조

• 루트(Root)라는 하나의 꼭짓점 데이터로 시작해 여러 개의 데이터를 **간선(Edge)**로 연결

• 각 데이터를 **노드(Node)**라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 맺음

• 자식이 없는 노드는 나무의 잎과 같다고 하여 **리프 노드(leaf node)**라고 함

• 깊이

  • 루트로부터 하위 계층의 특정 노드까지의 깊이

  • 루트 깊이는 0

• 레벨

  • 같은 깊이를 가진 노드를 묶어 레벨로 표현 가능

  • 깊이가 0인 루트의 레벨은 1

  • 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 함

• 높이

  • 트리 구조에서 리프 노드를 기준으로 루트까지의 높이를 표현 가능

  • 각 리프 노드의 높이를 0으로 놓고, 부모 노드는 자식 노드의 가장 높은 높이값에 +1한 값을 가짐

• 서브 트리

  • 트리 구조의 루트에서 뻗어나오는 큰 트리의 내부에 트리구조를 갖춘 작은 트리

• Tree의 실사용 예제

• 컴퓨터의 디렉토리 구조, 조직도 등

2. Binary Tree

• 이진 트리의 특징

  • 자식 노드가 최대 두 개인 노드로 구성된 트리

• 자료의 삽입/삭제 방법에 따른 분류

  • 정 이진트리(Full binary tree)

    • 각 노드가 0개 혹은 2개의 자식 노드를 가짐

  • 포화 이진트리(Perfect binary tree)

    • 정 이진트리이면서도 완전 이진트리인 경우. 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있음

  • 완전 이진트리(Complete binary tree)

    • 마지막 레벨을 제외한 모든 노드가 가득차 있어야 하며, 마지막 레벨의 노드는 전부 차있지 않아도 되나 왼쪽이 채워져 있어야 함

3. Binary Search Tree

• 이진 탐색 이란?

  • 정렬된 데이터 중에서 특정한 값을 찾기 위한 알고리즘 중 하나

  • 오름차순으로 정렬된 정수의 배열을 같은 크기의 두 부분 배열로 나눈 후, 두 부분 중 탐색이 필요한 부분에서만 탐색하도록 탐색 범위를 제한하여 원하는 값을 찾는 알고리즘

• 이진 탐색 트리

  • 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가짐

  • 기존 이진트리보다 탐색이 빠름

  • 트리 안에 찾고자 하는 값이 없더라도 최대 h번(트리 높이)만큼의 연산 및 탐색이 진행됨

4. Tree Traversal

• 트리 순회 방법의 공통점

  • 모두 노드를 순회할 때 왼쪽부터 오른쪽으로 조회

• 트리 순회 방법

  • 전위 순회 (preorder traverse)

    • 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색

    • 전위 순회는 주로 트리를 복사할 때 사용

  • 중위 순회 (inorder traverse)

    • 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색

    • 중위 순회는 이진 탐색 트리의 오름차순으로 값을 가져올 때 사용

  • 후위 순회 (postorder traverse)

    • 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문

    • 후위 순회는 트리를 삭제할 때 사용. 자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문

  • 레벨 순회 (levelorder traverse)

    • 루트를 방문하는 기준으로 순회를 하는 것이 아닌 트리의 레벨 기준으로 노드들을 방문

    • 루트 노드의 레벨이 1이라고 했을 때 아래로 내려갈수록 레벨은 증가하는 특징

    • 동일한 레벨에 여러 노드가 존재할 경우 왼쪽에서 오른쪽 순서로 노드를 방문