[자료 구조] 비선형 구조(Non Linear) - 트리(Tree)

비선형 구조(Non Linear)

• 데이터를 저장하기 위한 방법으로 데이터 간의 관계를 이루면서 계층적인 구조를 가지며 일렬로 나열되지 않은 자료구조 형태
  * 계층적인 구조 : 데이터 요소들이 상위와 하위 간의 관계를 가지며, 부모와 자식으로 구성되는 구조
• Ex) 트리(Tree), 그래프(Graph)

트리(Tree)

---

일반 트리

• 데이터를 계층적으로 구조화하여 저장하는 자료구조
• 데이터는 노드(Node)라는 구성요소로 구성되며, 하나의 루트 노드에서 시작하여 여러 개의 자식 노드로 분기되는 구조를 가진다.

• 노드(Node) : 트리를 구성하는 기본 구성 요소. 데이터를 저장하는 단위
• 루트 노드(Root Node) : 트리의 가장 상위에 위치한 노드. 부모 노드가 없는 최상위 상태
• 부모 노드(Parent Node) : 자식 노드를 가지는 노드
• 자식 노드(Child Node) : 부모 노드를 가지는 노드
• 형제 노드(Sibling Node) : 같은 부모를 가지는 노드
• 리프 노드(Leaf Node) : 자식 노드가 없는 노드
• 부분 트리(Sub-tree) : 트리에서 부모 노드와 그 자식 노드를 포함하는 트리
• 간선(Edge) : 노드(정점)와 노드를 연결하는 선으로 트리에서의 edge(간선)는 부모 노드와 자식 노드를 연결하는 선
• 외부 노드, 단말 노드(External Node) : 자식 노드가 없는 노드
• 내부 노드, 비단말 노드, 가지 노드(Internal Node) : 자식 노드가 있는 노드
• 노드의 깊이(Depth) : 루트 노드(Root Node)에서 해당 노드까지 경로 상에 있는 간선(Edge)의 개수
• 노드의 높이(Height) : 해당 노드에서 leaf 노드(끝 노드)까지 가장 긴 경로 상에 있는 간선의 개수

import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

public class TreeEx {

    public static void main(String[] args) {

        Set<String> treeSet = new TreeSet<>();

        treeSet.add("A");
        treeSet.add("B");
        treeSet.add("C");
        treeSet.add("D");
        treeSet.add("E");

        for (String element : treeSet) {
            System.out.println(element);
        }

        Map<String, Integer> treeMap = new TreeMap<>();

        treeMap.put("A", 1);
        treeMap.put("B", 2);
        treeMap.put("C", 3);
        treeMap.put("D", 4);
        treeMap.put("E", 5);

        for (String key : treeMap.keySet()) {
            System.out.println("key : " + key + ", value : " + treeMap.get(key));
        }


    }

}

이진트리(Binary Tree)

• 트리의 각 노드가 최대 두 개의 자식 노드를 갖는 트리 구조
• 각 노드는 키(key)와 값(value), 왼쪽 자식 노드(left child node), 오른쪽 자식 노드(right child node)를 가지고 있다.

 

특징

 

• 왼쪽 자식노드는 부모 노드보다 작은 값을 가지며 오른쪽 자식노드는 부모 노드보다 큰 값을 가진다.
• 균형 잡힌 트리이거나 불균형한 트리일 수도 있다.
• 이진트리를 이용하여 효율적인 검색이 가능하다
• 높이에 따라 결정되며 높이가 낮을수록 빠른 검색이 가능하다
• 검색과 정렬에서 효율적으로 사용되며 그 중에서도 이진탐색트리(Binary Search Tree)는 특히 검색과 삽입, 삭제 연산이 빠른 구조로, 데이터베이스 쿼리나 검색 엔진에서 사용된다.

활용 예시

 

• 균형 트리
  - 모든 노드의 서브 트리의 높이 차이가 한정된 트리 
  - 트리의 균형을 유지하며, 검색 및 삽입 연산의 시간 복잡도를 일정하게 유지할 수 있게한다.
• 불균형 트리
  - 한쪽으로 치우쳐진 트리 구조
  - 서브 트리의 높이 차이가 크게 나는 경우를 말하며, 검색 및 삽입 연산의 시간 복잡도가 불규칙하게 증가할 수 있다.
• 검색 알고리즘
  - 이진트리는 데이터를 정렬된 상태로 저장하기 때문에 데이터 검색 시간을 줄일 수 있다.
  - 주어진 값을 찾을 때까지 반복적으로 노드를 탐색하는 방법을 사용하여 매우 빠르며, 데이터 검색에 아주 적합하다.
• 정렬 알고리즘
  - 이진탐색트리(BST)를 이용하면 데이터를 삽입하면서 자동으로 정렬이 된다.
  - 힙(Heap)은 특정 우선순위 큐를 구현할 때 사용되며, 우선순위 큐를 이용한 다익스트라 알고리즘 등에 활용된다.
• 이진 검색 트리
  - 이진트리를 사용하여 데이터를 압축하면 중복되는 데이터를 제거할 수 있다.
  - Ex) 문자열 "ABBCCCDDDDEEEEE"를 이진트리로 압축하면 "A(1)B(2)C(3)D(4)E(5)"와 같이 표현할 수 있다.
• 파일 시스템
  - 파일 시스템에서는 이진트리를 사용하여 파일을 저장하며 파일을 빠르게 검색/삽입/삭제할 수 있습니다.
• 게임 개발
  - 게임에서는 이진트리를 사용하여 다양한 기능을 구현할 수 있습니다.
  - Ex) 적을 탐색하거나, 아이템을 검색하거나, 스킬 트리를 구현하는 등의 기능에 이진트리를 사용할 수 있습니다.
• 데이터베이스
  - 인덱싱을 위해 이진트리를 사용합니다. 이진탐색트리(BST)를 이용하면 데이터를 빠르게 검색할 수 있습니다.
  - B+트리(B+Tree)는 대용량 데이터베이스에서 많이 사용되는 인덱스 알고리즘입니다.

종류

 

• 전 이진 트리 (Full Binary Tree)
  - 트리의 모든 노드가 0개 또는 2개의 자식 노드를 가지는 이진 트리
  - 암호화 알고리즘에서 사용한다.
  

  

• 포화 이진 트리 (Perfect Binary Tree)
  - 트리의 모든 내부 노드가 2개의 자식을 가지며 모든 리프 노드가 같은 레벨에 있는 이진 트리
  - 데이터 정렬, 우선순위 큐 및 트리기반 알고리즘에서 사용한다.
  

  

• 완전 이진 트리 (Complete Binary Tree)
  - 트리의 모든 레벨이 완전히 채워져 있지는 않지만 마지막 레벨을 제외한 모든 레벨에서 왼쪽으로 차례대로 채워진 이진 트리
  - 힙 구조에서 사용한다.
  

  

• 편향 이진 트리 (Skewed Binary Tree)
  - 트리의 모든 노드가 한 쪽(왼쪽이나 오른쪽)으로만 자식을 가지는 이진 트리
  

  

• 균형 트리 (Balanced Tree)
  - 트리의 모든 내부 노드의 두 자식 서브 트리의 높이 차이가 1이하 인 이진 트리
  - 검색이나 삽입 작업에서 사용한다.
  

  

• 이진 힙(Binary Heap)
  - 트리의 각 노드가 자식 노드보다 작은 값을 가지는 최소 힙이거나 각 노드가 자식 노드보다 큰 값을 가지는 최대 힙 형태를 가지는 이진트리
  - 우선순위 큐에서 사용한다.

▷ 출처

https://adjh54.tistory.com/320

https://www.javatpoint.com/