2. 트리(Tree)
📌 트리(Tree)
그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부른다.
자료구조 Tree는 이름 그대로 나무의 형태를 가지고 있다. 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습을 가지고 있다
마치 가계도와 흡사해 보이는 이 트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다. 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다. 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 그래프에서의 사이클은 존재하지 않는다.
✔️ Tree의 구조
트리 구조는 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선으로 연결한다. 각 데이터를 노드(Node) 혹은 접점(Vertax)이라고 한다.
두 개의 노드가 상하 계층으로 연결되면 부모와 자식 관계를 가진다. 위의 그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 자식 노드(Child Node)이다.
같은 부모의 자식 노드들을 서로 형제(Sibling) 관계라고 한다. 위의 그림에서 A의 자식 노드 B, C는 서로에 대해 형제(Sibling) 관계이다.
또한 자식이 없는 노드를 나무의 잎과 같다고 하여 리프 노드(Leaf Node)라고 부른다.
✔️ 트리 구조의 레벨과 서브 트리(Sub Tree)
자료 구조 Tree는 깊이와 높이, 레벨 등을 측정하여 사용한다.
❗️깊이(Depth)
루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있다.
루트 노드는 나무가 지면에 있는 것처럼 깊이가 0이다. 루트로부터 내려갈수록 최대 깊이에 1을 더한 값을 깊이로 가진다.
❗️레벨(Level)
같은 깊이를 가지고 있는 노드들을 묶어서 레벨(level)로 표현할 수 있다.
깊이가 0인 루트의 레벨은 1이다. 또한 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 한다. 특정 레벨까지만을 탐색할 수 있게 하는 등 제약을 줄 수도 있다.
❗️높이(Height)
리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다.
리프 노드와 직・간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 1을 더한 값을 높이로 가진다. 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 기준한다.
❗️서브 트리(Sub Tree)
루트에서 뻗어 나오는 큰 트리의 내부에 트리 구조를 갖은 작은 트리를 서브 트리(Sub Tree)라고 한다.
루트로부터 뻗어나오는 모든 트리들을 서브 트리로 묶을 수 있다. 나무를 생각하면 가지에서 퍼져나가는 모든 잔가지들을 하나의 그룹으로 묶어서 서브 트리라고 표현할 수 있다.
📌 트리 순회(Tree Traversal)
특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다.
1에서 10까지의 정수로 구성된 트리에서 3이라는 숫자를 찾기 위해 모든 노드를 방문하는 경우는 트리 순회의 한 예시이다. 트리 구조는 계층적 구조라는 특별한 특징을 가지며 노드를 순회하는 방법으로 크게 세 가지가 있다. 각각의 순회가 이루어지는 과정을 아래의 움직이는 그림을 통해 확인하자.
✔️ 전위 순회(Preorder Traverse)
✔️ 중위 순회(Inorder Traverse)
✔️ 후위 순회(Postorder Traverse)
📌 이진 탐색 트리(Binary Search Tree)
트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용한다.
이전의 수많은 선배 개발자들은 효율적인 탐색을 위해 고민하고 발전시켜 새로운 트리의 모습을 만드는 등 치열한 노력을 쏟았다. 많은 트리들의 모습 중, 가장 간단하고 많이 사용하는 이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree)에 대해 알아보자.
✔️ 이진 트리(Binary Tree)
이진 트리(Binary Tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리를 말한다. 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다.
이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full Binary Tree), 완전 이진 트리(Complete Binary Tree), 포화 이진 트리(Perfect Binary Tree)로 나뉜다.
| 이진 트리 종류 | 영어 표기 | 설명 |
| 정 이진 트리 | Full Binary tree | 각 노드가 0개 혹은 2개의 자식 노드를 갖는 트리를 말한다. |
| 완전 이진 트리 | Complete Binary Tree | 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져 있어야 한다. |
| 포화 이진 트리 | Perfect Binary Tree | 정 이진 트리이면서 완전 이진 트리인 경우의 트리를 말한다. 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있는 트리이다. |
✔️ 이진 탐색 트리(Binary Search Tree)
이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징을 가지고 있다.
이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한 쪽으로 노드들이 몰리게 될 수 있다. 균형이 잡히지 않은 트리는 탐색하는데 시간이 더 걸리는 경우도 있기 때문에, 이 문제를 해결하기 위해 이진 탐색 트리는 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가하여 보완하는 구조로 되어 있다.
📌 이진 탐색 트리의 과정
✔️ 특정 데이터를 검색하는 과정
정렬된 배열과 이진 탐색 트리를 비교해보자.
정렬된 배열의 경우 맨 앞에서부터 순차적으로 값이 내가 찾고자 하는 값과 동일한지를 비교한다. 따라서 최대 배열의 크기만큼의 시간이 걸린다. 위의 예제에서 27을 찾기 위해 10번의 스텝을 밟는다.
반면에, 이진 탐색 트리에서는 내가 찾으려는 값과 노드의 값을 비교하여 내려간다. 예제를 살펴보면 값보다 큰 브런치는 비교하지 않기에 3번의 스텝으로 원하는 값의 탐색을 마칠 수 있다.
✔️ 데이터가 정렬되는 과정
이진 탐색 트리에서 데이터가 정렬되는 과정을 살펴보자.
- 입력된 데이터는 루트 노드의 값과 비교하여 작다면 왼쪽 노드에, 크다면 오른쪽 노드에 입력된다.
- 만약 왼쪽 노드에 값이 존재할 때 자식 노드는 부모 노드로 변경되고 값에 따라 왼쪽 혹은 오른쪽 노드에 값이 있는지를 비교한다.
- 만약 오른쪽 노드에 값이 존재할 때 자식 노드는 부모 노드로 변경되고 값에 따라 왼쪽 혹은 오른쪽 노드에 값이 있는지를 비교한다.
- 값이 존재하지 않는 왼쪽 노드(데이터가 비교하는 부모 노드보다 값이 작을 경우)를 발견한 경우 해당 노드에 값을 입력해준다.
- 값이 존재하지 않는 오른쪽 노드(데이터가 비교하는 부모 노드보다 값이 클 경우)를 발견한 경우 해당 노드에 값을 입력해준다.
✔️ 다시 선형 구조로 변경되는 과정
📌 트리의 활용
트리를 그림으로 설명해서 그렇지 알고보면 실생활에서 우리 주변에서 흔히 볼 수 있는 구조이다.
✔️ 컴퓨터 디렉토리 구조
가장 대표적인 예제는 컴퓨터의 디렉토리 구조이다. 어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더나 다운로드 폴더 등에서 다른 폴더에 진입하고, 또 그 안에 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾는다. 모든 폴더는 하나의 폴더(루트폴더, / )에서 시작되어, 가지를 뻗어나가는 모양새를 띈다.
✔️ 조직도
회사의 조직 구성도나 가족 구성의 가계도를 표현할 때도 트리 구조로 표현한다. CEO를 루트로 부사장, 이사회, 부문장 등등으로 뻗어 나간다. 그 외에도 나무처럼 생긴 모양새들은 거의 다 트리 형식이라고 보면 된다.