Tree

Tree

• 사이클(회로)이 없고 서로 다른 노드를 잇는 경로가 유일한 그래프이다

• 트리 속 간선 하나를 자르면 트리가 두 개로 분리된다

• 간선의 수(E) = 노드의 수(V)- 1

• 트리가 아닌 경우

  • 사이클이 존재하는 경우

  • 서로 다른 노드를 잇는 경로가 유일하지 않는 경우

  • 연결되지 않는 노드가 존재하는 경우 (하나의 트리가 아닌 n개의 트리로 봄)

• 용어

  • 루트노드(root node) : 부모가 없는 최상단위 노드

  • 단말노드(leaf node, terminal node) : 자식이 없는 말단 노드

  • 내부노드(internal node) : 단말노드를 제외한 모든 노드(루트노드 포함)

  • 깊이(depth) : 루트노드에서 어떤 노드까지 도달하기 위해 거쳐야하는 간선의 수

    • 깊이에 따라 트리 탐색 시간복잡도가 변함

    • 트리의 높이 : 루트 노드에서 가장 깊숙히 있는 노드의 깊이

  • 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합

    • 루트노드의 레벨은 0, 자식노드로 내려가면서 1씩 증가함

  • 차수 : 각 노드가 지닌 자식 노드의 수

    • 트리의 차수 : 트리의 최대 차수

Binary Tree

• 자식 노드가 최대 2개인 트리

• 종류

  • 전(Full) 이진트리 : 단말노드를 제외한 모든 노드가 0또는 2개의 자식노드를 가짐

  • 완전(Complete) 이진트리 : 마지막 레벨을 제외한 모든 레벨에서 노드들이 모두 2개의 자식 노드를 가짐

    • 왼쪽(→) 그리고 아래쪽(↓) 순서로 채워진다

    • 완전 이진트리는 1차원 배열로 표현가능하다 (heap)

  • 균형 이진트리 : 모든 단말노드의 깊이 차이가 최대 1

• 트리 순회

  • 전위 순회 : root → 왼쪽→ 오른쪽

  • 중위 순회 : 왼쪽 → root → 오른쪽

  • 후위 순회 : 왼쪽 → 오른쪽 → root

Binary Search Tree(BST, 이진탐색트리)

Untitled

• 왼쪽 자식 < 부모 < 오른쪽 자식 인 이진탐색

• 균형 잡힌 이진탐색트리의 탐색,삽입,삭제 → O(logN)

• 편향된 이진탐색트리의 탐색,삽입,삭제 → O(N)

  • 이를 해결하기위해 Rebalancing 기법 등장.

  • Rebalancing 기법을 구현한 트리 : AVL트리, Red-Black Tree

• 배열로 표현한 이진 탐색 트리

  • 현재 방문 노드의 index = i

  • 왼쪽 자식의 index = 2i +1

  • 오른쪽 자식의 index = 2i + 2

  • 부모의 index = (i - 1) / 2