(TIL) Tree

Tree

• 트리는 일반적으로 정보의 각 항목을 계층적으로 연관되도록 구조화할 때 사용되는 비선형 자료구조
• 따라서, 데이터 요소들이 단순 나열이 아닌 부모-자식 처럼 계측정 구조로 표현
• 트리는 사이클이 없는 그래프의 한 종류로, 가장 기본적인 트리 구조는 binary tree임
• 트리 자료구조는 데이터를 거꾸로된 나무 형태로 저장하는 모양

용어

• Node : 트리 구조의 교점으로 데이터를 가지고 있으며, 자식 노드룰 가지고 있음
• Root Node : 트리 구조의 가장 위 노드로 시작점을 나타냄
• Edge : 노드와 노드를 연결하는 선
• level : 트리의 깊이를 가지는 노드의 집합
• degree : 하위 트리 개수 / 각 노드가 지닌 가지의 수를 말함
• Internal Node : Leaf 노드를 제외한 중간에 위치한 노드
• Leaf Node : 하위에 다른 노드가 연결되어 있지 않느 노드

트리의 탐색

• 전위순회

  • 루트노드 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 순회하며, '깊이우선순회'라고 칭함

• 중위순회

  • 루트노드를 시작으로 왼쪽서브트리 - 노드 - 오른쪽 서브트리 순으로 순회하는 방식으로 '대칭 순회'라고 칭함

• 후위순회

  • 루트노드에서 시작해서 왼쪽 서브트리 - 오른쪽 서브트리 - 노드 순으로 순회하는 방식

이진트리와 이진 탐색트리

이진 트리

• 이진트리는 최대 차수가 2인 트리를 말하며, 하나의 노드에 left or right만 존재

  편향 이진 트리

  

• 편향 이진트리는 하나의 차수로만 이루어진 경우로, 이런 구조는 가장 끝 노드 탐색 시 결국 모두 읽어 들여야하는 단점이 있어 효율이 떨어짐

  포화 이진 트리

  

• 포화이진트리는 가장 끝 노드를 제외한 모든 노드의 차수가 두개로 이루어진 경우로 해당 차수에 몇개의 노드가 존재하는 지 바로 알 수 있어 갯수 파악에 용이함

  완전 이진 트리

• 포화 이진트리와 같은 개념으로 생성하지만 모든 노드가 왼쪽부터 차근차근 생성되는 이진 트리