Tree
- 그래프의 여러 구조 중 일방향 그래프의 한 구조로, 그 모습이 나무와 닮아 있다고 해서 트리 구조라는 이름이 붙여졌다. 하나의 뿌리로부터 가지가 사방으로 뻗은 형태를 띄우고 있기 때문
- 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조이다.
- 데이터를 순차적으로 나열시킨 형태인 선형 구조가 아닌, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조로 되어있다.
- 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다.
- 이 데이터들을 노드(Node)라고 하며, 상위 노드와 하위 노드가 연결이 되면 부모/자식 관계를 가지게 됩니다
- A는 B와 C의 부모 노드(Parent Node)가 되는 것이고, B와 C는 A의 자식 노드(Child Node)가 된다.
- 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(leaf Node)라 부른다.
- 트리구조는 높이와 깊이를 잴 수 있다.
- 노드와 노드의 간격(거리)를 레벨(Level)이라고 부르며, 첫 번째 노드인 루트를 Level 1로 설정한다
- 루트부터 가장 안쪽에 있는 노드까지의 레벨을 트리의 높이(Height)라고 하고, 반대로, 특정 노드부터 시작하여 루트까지의 레벨을 노드의 깊이(depth)라고 칭한다.
- 같은 레벨에 나란히 있는 노드들은 형제 노드(sibling Node)라 칭한다.
- root에서 뻗어나오는 큰 트리의 내부에 트리의 모양새를 갖춘 작은 트리를 서브 트리라고 부릅니다 (위 그림 예제에서는 D-H-I, B-D-E, C-F-G)
트리의 실사용 예제
- 가장 대표적으로, 컴퓨터의 디렉토리 구조를 생각할 수 있다.
- 어떠한 프로그램이나 파일을 찾을 때 우리는 우리만의 방식으로 잘 정돈된 폴더에서 타고 들어가 원하는 것을 찾게 됩니다. 혹은, 이미 만들어 놓은 폴더 구조에서 찾고는 한다. 모두 하나의 폴더에서 시작되어, 가지처럼 뻗어나가는 형태를 보이고 있다.
- 하나의 폴더 안에 여러 개의 폴더가 있고, 또 그 여러 개의 폴더 안에 또 다른 폴더가 있을 수도 있고, 없을 수도 있다. 보이는 바와 같이, 제일 첫 번째 폴더에서 찾고자 하는 폴더로 가는 경로는 유일하다. 사용자들이 사용하기 편하게 하기 위한 파일 시스템과 같은 구현은 모두 트리를 이용해서 만든다
- 다른 예시로는 월드컵 토너먼트 대진표, 가계도(족보), 조직도 등이 있다.
BST(Binary Search Tree)\
- 모든 왼쪽 자식들은 루트나 부모보다 작은 값이고, 모든 오른쪽 자식들은 루트나 부모보다 큰 값인 특징을 가지고 있는 이진 트리를 이진 탐색 트리(Brinary search tree)라 부른다.
- 트리는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용하기도 한다.
- 자식 노드가 최대 두 개인 노드들로 구성된 트리를 이진 트리라고 정의
- 이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다.(아래 그림 참조)
정 이진 트리: 각 노드가 0 개 혹은 2 개의 자식 노드를 갖습니다.
포화 이진 트리: 정 이진 트리이면서 완전 이진 트리인 경우(왼쪽은 다채워지고, 오른쪽은 0개 혹은 2개)입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리 - 완전 이진 트리: 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.
- 이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 가능성이 있습니다. 이러한 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 도입할 수 있다.
Tree traversal(트리 순회)
- 어떠한 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
- 트리를 순회할 수 있는 방법은 크게 전위 순회, 중위 순회, 후위 순회 세 가지로 나뉜다. 전, 중, 후의 기준은 루트로, 루트를 어디에 두느냐에 따라서 순회 방식이 달라진다. 이 순회 방식과는 논외로, 순회할 때의 순서는 항상 왼쪽부터 오른쪽으로 가게 된다.
트리 순회 관련 자료.
BFS/DFS
- 아래 자료들을 보면서 더 공부할 예정
BFS/DFS
<참조 자료>
소통하는 개발자를 꿈꾸는