비선형 데이터구조, 트리(Tree) #1 이진 트리의 소개

1. 트리(Tree)란 무엇인가?

트리(Tree)란 배열과 연결리스트, 스택, 큐와 같은 선형 데이터 구조와는 다르게 계층적인 구조를 가지는 데이터 구조입니다. 트리 노드란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조입니다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나분인 그래프를 트리라고 부릅니다.

 

2. 이진 트리(Tree)란 무엇인가?

이진 트리(Binary Tree)란 각각의 노드가 최대 2개의 자식 노드를 가지는 트리 자료 구조입니다. 자식 노드를 각각 왼쪽 자식 노드, 오른쪽 자식 노드라고 합니다. 

 

3. 이진 트리(Binary Tree)의 용어

• 루트 노드(Root Node) : 트리의 가장 꼭대기에 존재하는 노드
• 부모 노드(Parent Node) : 자식 노드를 가지고 있는 노드
• 왼쪽 자식 노드(Left Children Node) : 왼쪽 부트리의 노드
• 오른쪽 자식 노드(Right Children Node) : 오른쪽 부트리의 노드
• 리프 노드(Leaf Node) : 차수가 0개인 노드, 즉 자식 노드가 없는 노드
• 형제 노드(Sibling Node) : 같은 부모를 가지고 있는 노드
• 노드의 차수(Degree) : 자식의 개수
• 내부 노드(Internal Node) : 차수가 0이 아닌 노드, 즉 자식이 있는 노드
• 서브 트리(Sub Tree) : 트리 속에 또 다른 작은 트리
• 간선(Edge) : 노드와 노드를 잇는 선
• 노드의 깊이(dpeth) : 자신을 제외한 조상 노드들의 개수
• 레벨(Level) : 특정 깊이(depth)를 가지는 노드들의 집합, 루트 노드는 레벨 0
• 트리의 높이(height) : 루트 노드에서 말단 노드에 이르기까지의 노드의 개수 (height= depth+1)
• 노드의 크기(size) : 자기 자신 및 모든 자손 노드의 개수

4. 이진 트리(Binary Tree)의 용어 연습

위의 그림을 기준으로 아래 문제를 연습

1. 루트 노드는 무엇인가?
2. 노드 B의 부모 노드는 어떤 노드인가?
3. 노드 B의 자식 노드는 무엇인가?
4. 위 이진 트리에서 리프 노드는 무엇인가?
5. 노드 D의 형제 노드는 무엇인가?
6. 노드 C의 차수는 몇인가?
7. 위 이진 트리의 내부 노드는 몇개인가?
8. 노드 F의 깊이는 몇인가?
9. 노드 H의 레벨은 몇인가?
10. 노드 D의 높이는 몇인가?
11. 위 이진 트리의 높이는 몇인가?
12. 노드 B의 크기는 몇인가?

1. A

2. A

3. D E

4. H E F G

5. E

6. 2

7. 4

8. 2

9. 3

10. 3

11. 4

12. 4

5. 이진 트리(Binary Tree)의 특징

1. 데이터 정보들을 계층적으로 저장할 수 있다. 예를 들어 컴퓨터에서 파일 시스템을 예를 들수 있다.
2. 이진 트리들(이진 탐색 트리와 같은 순서가 있는 트리)은 적절한 성능의 접근 및 탐색을 제공합니다. (배열 기반 보다 연결리스트 기반이 더 빠름)
3. 이진 트리는 삽입과 삭제에서도 적절한 성능을 보장합니다.(비 순서화된 연결리스트와 배열보다 빠름)
4. 연결리스트와 비슷하게 이진 트리는 크기의 상한선이 없다.

6. 이진 트리로 활용된 주요 애플리케이션

1. 파일 시스템과 같은 계층적인 데이터 조작
2. 정보를 쉽게 검색
3. 정렬된 데이터 리스트 조작
4. 시각효과를 위해 디지털 이미지를 합성하는 워크플로우
5. 라우터 알고리즘
6. 다단계 의사 결정(multi-stage decision-making)의 형태

 

7. 이진 트리의 예제

// 노드의 구성
// key : data값
// left, right : 왼쪽 자식노드, 오른쪽 자식노드
class Node
{
    int key;
    Node left, right;
 
    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}

class Node
{
    int key;
    Node left, right;
 
    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}
 
// 이진트리를 소개하기 위한 예제
class BinaryTree
{
    Node root;	// 루트 노드
 
    // 생성자
    BinaryTree(int key)
    {
        root = new Node(key);
    }
 
 	// 비어있는 트리
    BinaryTree()
    {
        root = null;
    }
 
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
 
        // 루트 노드 생성
        tree.root = new Node(1);
 
        /* 위의 명령문 이후 아래와 같이 트리 생성
 
              1
            /   \
          null  null     */
 
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
 
        /* 1의 자식노드로 2, 3 노드 생성
               1
            /     \
          2        3
        /   \     /  \
      null null null null  */
 
 
        tree.root.left.left = new Node(4);
        /* 4는 2의 왼쪽 자식 노드가 된다.
                    1
                /       \
               2          3
             /   \       /  \
            4    null  null  null
           /   \
          null null
         */
    }
}

 

8. 요약

• 이진 트리는 계층적인 데이터 구조를 가지고 있습니다.
• 이진 트리의 주요 용도는 계층적인 데이터 구조를 조작하는 일입니다.
• 이진 트리는 노드가 최대 자식 노드를 2개까지밖에 가지는 트리입니다.

References

source code : https://github.com/yonghwankim-dev/DataStruct
https://www.geeksforgeeks.org/binary-tree-set-1-introduction/
https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC#%EC%9A%A9%EC%96%B4