Tree

Tree(트리)

트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적인 구조를 갖는 비선형 자료구조로, 여러 노드(Node)가 간선(Edge)으로 연결되어 있는 형태를 가지고 있다.

• 무엇인가를 저장하고 꺼내야 한다는 사고에서 벗어나 트리라는 자료구조를 봐야한다고 한다.

트리의 구성요소와 관련된 용어

• Node(노드) : 트리를 구성하고 있는 각각의 요소를 의미
• Edge(간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미
• Root Node(루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미
• Terminal Node( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미
• Internal Node(내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함
• Parent Node(부모 노드) : 특정 노드의 바로 위에 위치한 노드를 의미
  • 자식 노드를 가지는 노드는 해당 자식 노드의 부모 노드이다.
• Child Node(자식 노드) : 특정 노드의 바로 아래에 위치한 노드를 의미
  • 이진 트리에서 각 노드는 최대 두 개의 자식 노드를 가질 수 있다.
• Level(레벨) : 루트 노드부터 특정 노드까지의 경로 길이를 의미
  • 루트 노드의 레벨은 0이며, 각 레벨로 내려갈 때마다 1씩 증가한다.

트리의 종류

1. Binary Tree(이진 트리) :
   • 각 노드가 최대 두 개의 자식 노드를 가지는 트리구조이다.
     • 이진 트리는 자식 노드의 수, 자식 노드의 배치, 데이터의 정렬 방식 등에 따라 다양한 형태를 가질 수 있다.
2. Full Binary Tree(포화 이진 트리) :
   • 모든 레벨에서 노드들이 모두 채워져 있고, 마지막 레벨을 제외한 모든 노드들이 두 개의 자식 노드를 가지는 이진 트리를 의미한다. 모든 내부 노드는 2개의 자식 노드를 가진다.
     • 모든 단말 노드는 동일한 레벨에 존재한다.
3. Complete Binary Tree(완전 이진 트리) :
   • 마지막 레벨을 제외한 모든 레벨에서 노드들이 왼쪽부터 차례로 채워져 있고, 마지막 레벨에서는 노드들이 가능한 한 왼쪽부터 채워진 이진 트리를 의미한다.
     • 완전 이진 트리는 배열을 이용한 효율적인 저장 방법을 제공한다.
4. BST(Binary Search Tree, 이진 탐색 트리) :
   • 이진 탐색 트리는 이진 트리의 일종으로, 데이터를 저장하고 검색하는데 효율적인 구조이다. 각 노드는 왼쪽 자식의 노드의 값보다 작고, 오른쪽 자식 노드의 값보다 큰 값을 가진다.
     • 이진 탐색 트리는 데이터를 효율적으로 정렬된 상태로 유지하고, 탐색, 삽입, 삭제 등의 연산을 빠르게 수행 가능하다.
     • BST의 장점은 O(log n)의 평균 시간 복잡도를 가진다는 것이다.