[자료구조] 트리(Tree)

트리(Tree)

---

트리는 값(노드)들이 나무 가지와 같은 모양을 가지고 있는 자료 구조이다.

트리 내에 있는 각 공간을 "노드"라고하며, 가장 위쪽에 있는 노드를 "루트 노드"라고 한다.

또한 트리는 트리 안에 하위 트리를 가지고, 그 트리가 또 다시 하위 트리를 가지는 재귀적 구조이다.

 

위 그림에 있는 트리를 보면, 전체 트리에서 다시 왼쪽, 오른쪽으로 나뉘어서 하위 트리를 가지는걸 볼 수 있다.

컴퓨터에서 폴더(Directory)구조가 트리 구조의 예가 될 수 있다.

 

이제 트리에 대한 용어에 대해서 알아보도록 하자.

노드(Node)

• 트리를 구성하는 요소(데이터)
• 각 노드는 키 또는 값과 하위 노드에 대한 포인터를 가지고있다.
• A, B, C, D, E, F, G, H, I

간선(Edge)

• 노드와 노드를 연결하는 선
• A와 B사이의 선, C와 F사이의 선 등

루트 노드(Root Node)

• 트리의 최상위 노드
• A

부모 노드(Parent Node)

• 하위 노드(자식 노드)를 가진 노드
• A, B, C, D
• B는 D의 부모 노드

자식 노드(Child Node)

• 상위 노드(부모 노드)를 가진 노드
• A를 제외한 모든 노드
• B는 A의 자식 노드

형제 노드(Siblings)

• 같은 부모 노드를 가지는 자식 노드들
• F와 G는 C를 공통 부모로 가지는 형제

리프 노드(Leaf Node)

• 트리의 가장 하위에 있는 자식이 없는 노드
• F, G, H, I

깊이(Depth)

• 루트 노드와 자신(노드)까지의 간선 수
• H의 깊이는 3

레벨(Level)

• 루트 노드와 자신(노드)까지 거치는 노드 수
• H의 레벨은 4

높이(Height)

• 트리에서 가장 높은 레벨
• 위 그림의 트리의 높이는 4

차수(Degree)

• 해당 노드의 하위 트리(SubTree), 자식 노드의 수
• B노드의 Degree는 2

경로(Path)

• 특정 노드로부터 다른 노드 사이에 있는 노드들의 순서
• A, H의 Path는 A, B, D, H

크기(Size)

• 해당 트리의 노드의 개수
• 위 트리의 크기는 9

넓이(Width)

• 가장 많은 노드를 가지고 있는 레벨
• 위 트리의 넓이는 4

 

트리의 종류

---

1. 이진 트리(Binary Tree)

자식 노드를 최대 2개까지 가지는 트리

 

1-1) 완전 이진 트리(Complete Binary Tree)

왼쪽 자식부터 채워지며 가장 아래(마지막 레벨)을 제외한 모든 레벨이 채워져있는 트리

 

1-2) 포화 이진 트리(Perfect Binary Tree)

트리의 모든 노드가 0개 혹은 2개의 자식노드를 가지며 모든 리프 노드가 같은 레벨을 가지는 경우

 

1-3) 정 이진 트리(Full Binary Tree)

트리의 모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리, 포화 이진 트리의 하위 종류

 

1-4) 편향 이진 트리(Skewed Binary Tree)

트리의 노드들이 모두 한 방향으로 편향된 트리

 

1-5) 균형 이진 트리(Banaced Binary Tree)

트리의 모든 노드의 왼쪽과 오른쪽 서브 트리의 높이가 1이상 차이나지 않는 트리

위쪽은 균형 이진 트리이고, 아래는 균형 이진 트리가 아니다.

2. 삼항 트리(Ternary Tree)

자식 노드를 세개까지 가지는 트리

 

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

1. 각 노드의 왼쪽 서브트리는 해당 노드보다 작은 값들이 들어간다.
2. 각 노드의 오른쪽 서브트리는 해당 노드보다 큰 값들이 들어간다.
3. 각 노드들은 중복된 값을 가질 수 없다.
4. 왼쪽, 오른쪽의 서브트리 또한 이진 탐색 트리이다.

이진 트리 구현(Kotlin)

---

fun main() {
    var mTree = MyBinaryTree()
    mTree.add(1)
    mTree.add(10)
    mTree.add(13)
    mTree.add(32)
    mTree.add(50)

    println(mTree.search(32))
    println(mTree.search(90))
}

class MyBinaryTree{
    var root: MyNode? = null

    fun add(data: Int){
        if(root == null) root = MyNode(data)
        else{
            var node: MyNode? = root

            while(true) {
                if (node!!.left == null) {
                    node.left = MyNode(data)
                    break
                } else if (node.right == null) {
                    node.right = MyNode(data)
                    break
                } else node = root!!.left
            }
        }
        println("데이터 추가 ${data}")
    }

    fun search(data: Int): Boolean{
        var node = root
        while(true){
            if(node!!.data == data) return true
            else if(node.left != null) node = node.left
            else if(node.right != null) node = node.right
            else return false
        }
    }
}

class MyNode(var data: Int){
    var left: MyNode? = null
    var right: MyNode? = null
}

이진 트리를 Kotlin코드로 구현해보았다.

위 트리에선 데이터 추가와 검색만 가능하도록 했고, 중복을 허용하는 트리이다.