단방향으로 연결된 계층적인 자료구조입니다.
그래프의 한 종류 입니다.
단방향이고 계층적이기 때문에 사이클이 존재하지 않습니다.
순차적으로 나열시킨 선형 구조가 아니라, 비선형 구조입니다.
대표적인 종류로는 이진 트리, 이진 탐색 트리가 있습니다.
실생활의 예로는 컴퓨터 파일 시스템 구조, 단체의 조직도가 있습니다. (하나의 폴더 아래에 폴더나 파일이 존재)
이진 트리란?
자식 노드가 최대 두 개인 트리입니다. 정 이진 트리, 포화 이진 트리, 완전 이진 트리가 있습니다.
이진 탐색 트리란?
부모 노드를 기준으로 왼쪽의 자식 노드는 항상 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 항상 부모 노드의 값보다 큰 특징을 가지고 있는 이진 트리입니다.
이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있습니다. 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 해결해야 할 문제입니다. 이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있습니다.
트리를 왜 사용할까?
효율적인 탐색이 가능합니다.
트리 구조는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결합니다. 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가집니다. 위 그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node)입니다. 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Node)라고 부릅니다
