[자료구조] Tree

Taeha Kim·2020년 8월 29일

Data Structure&Algorithm

목록 보기

7/9

Tree

트리 자료구조는 이름(Tree)처럼 나무에 나뭇가지가 있고, 이 가지들이 뻗어나가는 모양으로 되어있습니다. 진짜 나무와 비교하면 가지가 위가 아닌 아래로 뻗어나간다는 차이점이 있지만 이점을 제외하면 크리스마스 트리처럼 생겼습니다.😀

Tree 용어

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

Tree의 특징

트리 자료구조는 일반적으로 대상정보의 각 항목들을 계층적으로 구조화 할때 사용하는 비선형 자료구조입니다.
Tree 구조는 데이터의 '저장'의 의미 보다는 저장된 데이터를 더 효과적으로 '탐색' 하기 위해서 사용됩니다.
리스트와 다르게 데이터가 단순히 나열되는 구조가 아니라, 부모(parent)와 자식(child)의 계층적인 관계로 표현 됩니다.
트리는 그래프(Graph)의 한 종류이며, 사이클이 없습니다.
트리에서 Root Node를 제외한 모든 노드는 단 하나의 부모노드를 가집니다.

Tree 순회

트리의 순회란 트리의 각 노드를 체계적인 방법으로 탐색하는 과정을 말합니다.
노드를 탐색하는 순서에 따라 전위 순회, 중위 순회, 후위 순회 세가지로 나뉩니다

1) 전위 순회(Preorder)

루트노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순으로 순회하는 방식입니다.
'깊이 우선 순회'라고도 합니다.

A → B → D → H → I → E → J → K → C → F → L → M → G → N → O

2) 중위 순회(Inorder)

왼쪽 서브트리 → 노드 → 오른쪽 서브트리 순으로 순회하는 방식입니다.
'대칭 순회' 라고도 합니다.

H → D → I → B → J → E → K → A → L → F → M → C → N → G → O

3) 후위 순회(Postorder)

왼쪽 서브트리 → 오른쪽 서브트리 → 노드 순으로 순회하는 방식입니다.

H → I → D → J → K → E → B → L → M → F → N → O → G → C → A

이진 트리(Binary tree)

트리 자료구조는 여러 유형이 있지만 가장 기본이 되는 트리는 이진트리(Binary tree)구조 입니다.

이진트리는 두개 이하의 자식노드를 가집니다.(하나의 자식노드만 가지는것도 가능)
두개의 자식노드 중에서 왼쪽에 있는 노드를 left node , 오른쪽에 있는 노드를 right node 라고 합니다.

이진 트리의 종류

1. 편향 이진 트리(Skewed binary tree)
편향 이진 트리는 하나의 차수로만 이뤄져 있는 경우를 말합니다. 이런 구조는 배열과 같은 선형 구조이기 때문에 Leaf Node 탐색시 결국 모두 읽어 들여야 한다는 단점이 있어서 효율이 떨어집니다. (이같은 점을 보완하기 위해 '높이 균형 트리'라는 것이 있습니다.)

2. 포화 이진 트리(Full Binary Tree)
포화이진 트리는 Leaf Node를 제외한 모든 노드의 차수가 두개로 이뤄진 경우를 말합니다.
이 경우 해당 차수에 몇개의 노드가 존재하는지 바로 알수 있어서 개수 파악이 용이하다는 장점이 있습니다.

3. 완전 이진 트리(Complete Binary Tree)
포화 이진트리와 같은 개념으로 생성하지만 모든 노드가 왼쪽부터 차근차근 생성되는 이진 트리를 말합니다.

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(binary search tree)는 탐색을 위한 이진 트리 기반의 자료 구조입니다.
이진 탐색 트리는 다음과 같은 특징을 갖습니다.

left node 에는 부모노드보다 작은 값이 저장됩니다.
right node 에는 부모노드와 값이 같거나 큰 값이 저장됩니다.
모든 노드는 중복된 값을 가지지 않습니다.

예를 들어, [21, 28, 14, 32, 25, 18, 11, 30, 19, 15]를 이진 트리로 저장하면 다음과 같습니다.

이진 탐색 트리를 사용함으로 데이터를 효율적으로 검색 할 수 있습니다.

원하는 값을 찾을 때까지 현재의 node값보다 찾고자하는 값이 크면 왼쪽으로 움직이고, 작으면 오른쪽으로 움직입니다.

일반적으로 리스트는 검색이 O(N)이고, 이진 탐색 트리는 O(log N)입니다.
따라서 리스트 보다 이진 탐색 트리의 검색이 훨씬 효율적입니다.

Binary search tree in python

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def findval(self, lkpval):
        if lkpval < self.data:
            if self.left is None:
                return str(lkpval)+" Not Found"
            return self.left.findval(lkpval)
        elif lkpval > self.data:
            if self.right is None:
                return str(lkpval)+" Not Found"
            return self.right.findval(lkpval)
        else:
            print(str(self.data) + ' is found')

    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print(self.data)
        if self.right:
            self.right.PrintTree()


root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
print(root.findval(7))
print(root.findval(14))