[자료구조] 트리(Tree)

노드(Node)와 브랜치(Branch)를 이용해 사이클을 이루지 않도록 구성한 자료구조

선형 구조(순차적 구성)인 큐, 스택 등과 달리 트리는 비선형 구조이다.(계층적으로 구성)

 

주로 이진 트리(Binary Tree) 형태로 탐색(검색) 알고리즘 구현에 많이 사용된다.

이진 트리: 노드의 최대 브랜치가 2인 트리. 즉, 자식 노드가 최대 2개인 트리

 

• 노드(Node): 트리에서 데이터를 저장하는 기본 요소(데이터 + 연결된 노드에 대한 브랜치 정보)
• 루트 노드(Root Node): 트리에서 가장 위에 있는 노드
• 레벨(Level): 루트 노드를 기준으로, 하위에 연결된 노드의 깊이
• 부모 노드(Parent Node): 어떤 노드의 상위 레벨에 연결된 노드
• 자식 노드(Child Node): 어떤 노드의 다음 레벨에 연결된 노드
• 형제 노드(Sibling, Brother Node): 동일한 부모를 가진 노드
• 깊이(Depth): 트리에서 노드가 가질 수 있는 최대 레벨
• 터미널 노드 / 리프 노드(Terminal Node / Leaf Node): 하위 레벨에 노드가 연결되어 있지 않은 노드. 즉, 자식 노드가 없는 노드

 

• 이진 탐색 트리(Binary Search Tree, BST): 이진 트리이면서, 왼쪽 노드가 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값인 조건을 만족하는 트리. 탐색 시 시간 복잡도는 O(log n)
• 포화 이진 트리(Full Binary Tree): 모든 노드가 2개의 자식 노드를 가지면서 모든 리프 노드가 동일한 레벨을 갖는 트리
• 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 모든 리프 노드가 왼쪽에 있는 이진 트리. 노드를 삽입할 때 최하단 왼쪽 노드부터 차례로 삽입하는 트리