트리 자료구조: 이진, 이진탐색, Balanced Tree

목차
트리 자료구조
    1. 이진 트리(Binary Tree)
    2. 이진 탐색 트리(Binary Search Tree)
        2-1. 이진 탐색트리의 Basic operations
    3. Balanced Tree

 

오늘 소개할 트리 자료구조를 이해하기 위해서는 탐색 알고리즘(Search Algorithm)에 대한 이해가 있어야하기 때문에 아래 글을 먼저 보고 오시는 걸 추천드립니다. 그럼 트리 자료구조와 그래프 자료구조를 알아보겠습니다. 

정렬 알고리즘(버블, 퀵)과 탐색 알고리즘(선형, 이진)

---

트리(Tree) 자료구조

트리(Tree)는 계층 구조를 갖는 자료구조로, 여러 개의 노드가 나무의 가지처럼 연결된 구조를 가지고 있습니다.  각 노드는 하나의 부모 노드와 여러 개의 자식 노드를 가지며, 최상위 노드인 루트 노드는 부모 노드가 없는 특별한 노드입니다. 트리 자료구조는 많은 분야에서 사용되며, 컴퓨터 공학에서도 많은 응용 분야가 있습니다. 대표적인 예로 우리가 대부분 사용하고 있는 폴더, 파일 구조도 트리 구조로 되어있죠.

 

 

• Tree와 관련된 용어 설명
  • Node : 트리 구조의 교점으로 Node는 데이터(value)를 가지고 있고, 자식노드를 가지고 있습니다.
  • Root Node: 트리구조에서 가장 위에 있는 노드. 즉 시작점이 되는 노드입니다.
  • Edge: 트리를 구성하기 위해 노드와 노드를 연결하는 선 입니다.
  • level: 트리의 특정 깊이를 가지는 노드의 집합 입니다.
  • degree: 각 노드가 지닌 가지의 수를 말하며 '차수'라고도 합니다.(밑에 Child 몇개 가지고 있는지)
  • Leaf Node(Terminal Node): 하위에 다른 노드가 연결되어 있지 않은 노드
  • Internal Node : Leaf노드를 제외한 중간에 위치한 노드들을 말합니다.
  • Height(=depth): 트리에 가장 큰 Level의 숫자

 

1. 이진 트리(Binary Tree)

이진 트리(Binary Tree)는 각 노드가 최대 2개의 자식 노드를 갖는 트리 자료구조입니다. 모든 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드 중 하나만 가질 수 있습니다. 이진 트는 데이터를 탐색하거나 정렬하는 데 유용하게 사용됩니다. 비슷한 트리로는 자식 노드가 3개인 Ternary Tree가 있습니다.

 

2. 이진탐색 트리(Binary Search Tree)

이진탐색 트리(Binary Search Tree)는 이진 트리의 일종으로, 각 노드가 특정한 순서로 정렬된 데이터를 갖는 트리 자료구조입니다. 왼쪽 자식(left child) 노드는 부모 노드보다 작은 값, 오른쪽 자식(right child) 노드는 부모 노드보다 큰 값이 저장됩니다. 이렇게 순서대로 정렬되어 있어 데이터를 효율적으로 검색할 수 있습니다.

 

 

이진탐색 트리는 이진 탐색(Binary Search) 알고리즘에서 사용하는 구조입니다. 이진 탐색 알고리즘은 이미 정렬되어있는 데이터에서 원하는 항목을 찾는 알고리즘이라고 설명드렸습니다. 술게임을 할 때 소주병에 있는 번호를 맞추는 게임인 업다운 게임과 비슷한 프로세스를 가지고 있죠. 번호를 맞추려면 숫자가 1, 2, 3, 4... 이렇게 이미 숫자가 오름차순으로 정렬이 되어있어야 맞출 수 있습니다. 그래서 이진 탐색 알고리즘은 정렬되어있는 리스트에서만 사용이 가능하다고 했었죠.

 

위 그림의 오른쪽 이진 탐색 트리의 구조를 보면, 숫자가 특정한 규칙에 의해 정렬되어있는 걸 볼 수 있습니다. [4, 6, 7, 8, 10, 11] 중, 가운데 숫자인 8을 Root Node로 설정하고, 그 왼쪽의 트리에는 8보다 작은 숫자만 있고, 그 오른쪽에는 8보다 큰 숫자만 있죠. 다시 4,6,7 중에 가운데 숫자인 6을 중심으로 왼쪽에는 4를 오른쪽엔 7을 채워넣는 식입니다. 

 

이 구조에서 이진 탐색 알고리즘을 사용한다면, 어떻게 될까요? '4'라는 숫자를 찾는다고 가정하고, Root Node부터 시작해보겠습니다. Root Node가 '8'이니까 그보다 큰 숫자는 아예 볼 필요가 없겠죠? 오른쪽 노드에 있는 숫자들을 전부 8보다 큰 숫자 이니 더이상 탐색할 필요가 없습니다. 그리고 '6'으로 내려옵니다. 다시 4는 6보다 작은 숫자이니, 오른쪽 노드는 마찬가지 볼 필요가 없겠죠. 그렇게 6의 자식 노드인 4을 O(logN)이라는 시간복잡도로 효율적으로 찾을 수 있게 됩니다.

 

2-1. 이진탐색 트리의 Basic operations

트리에서는 노드의 추가, 삭제, 탐색 등 다양한 작업이 필요합니다. 이러한 작업을 수행하기 위해 다음과 같은 기본적인 트리 연산이 제공됩니다.

• 삽입(insert) : 새로운 노드를 원래의 트리에 추가합니다. 부모노드보다 크면 오른쪽, 작으면 왼쪽에 추가합니다.
• 삭제(delete) : 트리에서 노드를 삭제합니다. 삭제하려는 노드를 찾아야 삭제가 사능해서, 우선 탐색부터 해야합니다.
• 탐색(search: Tree travel) : Root Node부터 차례로 Left child > Right child 순서로 탐색합니다. 노드보다 작은값이면 왼쪽, 높은 값이면 오른쪽 순으로 찾습니다. 

 

3. Balanced Tree

Balanced Tree는 트리의 균형을 유지하기 위한 방법입니다. 중복된 데이터가 들어오는 경우에 이진트리나 이진탐색트리의 경우 한쪽으로 편향된 구조를 가질 수 있다는 단점이 있습니다. 이러한 구조는 배열과 같은 선형구조이기 때문에 Leaf Node 탐색시 효율이 떨어집니다. 이를 보안하기 위해 Balanced Tree구조를 사용하며, 종류에는 B-tree, B+tree 등이 있습니다. 

 

 

 

여기까지 트리 자료구조에 대해서 알아보았습니다. 트리 자료구조 종류에는 이외에도 완전 이진 트리, Full Binary Tree, Perfect binary Tree 등이 있습니다