1. Tree

Tree는 데이터를 거꾸로된 나무 형태로 저장하는 자료 구조다. 여러 유형이 있지만 그 중 가장 기본은 binary tree(이진 트리) 자료구조다. 이진 트리는 두개의 자식 노드를 가진 트리 형태!

Tree 구조는 데이터의 저장의 의미 보다는 저장된 데이터를 더 효과적으로 탐색 하기 위해서 사용된다. 일반 list는 검색이 O(N)인데에 비해 이진 트리는 O(log N) 이므로 리스트 보다 검색이 훨씬 효율 적이다.

• 트리는 일반적으로 대상정보의 각 항목들을 계층적으로 연관되도록 구조화 시키고자 할때 사용하는 비선형 자료구조
• 데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현
• 트리는 그래프(Graph)의 한 종류이며 사이클이 없음
• 계층적인 관계의 표현에 쓰이고, 윈도우와 리눅스의 파일시스템 구조도 트리로 표현. 대용량의 데이터를 저장할때도 많이 쓰임

2. 용어

트리의 속성 중 가장 중요한 것이 '루트 노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다'는 것이다. 기본 개념은 노드와 루트 노드이고, 나머지 개념에 대해서도 정리가 필요하다.

• Node : 트리 구조의 교점. Node가 데이터를 가지고 있고, 또한 자식노드를 가지고 있다. 트리 자료구조는 노드를 기본으로 구성된다.
• Root Node: 트리구조의 가장 위 노드. 즉 시작점이 되는 노드.

---

• Edge: 트리를 구성하기 위해 노드와 노드를 연결하는 선.
• level: 트리의 특정 깊이를 가지는 노드의 집합.
• degree: 하위 트리개수/각 노드가 지닌 가지의 수.
• Internal Node : Leaf노드를 제외한 중간에 위치한 노드.
• Leaf Node: 하위에 다른 노드가 연결되어 있지 않은 노드.

3. 트리의 탐색

트리의 순회란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말한다. 노드를 방문하는 순서에 따라 전위순회, 중위 순회, 후위순회 세가지로 나뉜다. 이미지 및 내용은 위키피디아!

1. 전위순회(preorder, 깊이 우선 순회): 루트에서 시작해 왼쪽 서브트리를 위>아래로 다 돌고 오른 쪽으로!
2. 중위순회(inorder, 대칭 순회): 왼쪽 서브트리를 가운데부터 아래>위 순으로 돌고 노드를 방문한 뒤, 오른쪽 서브트리를 아래>위 순으로 순회한다.
3. 후위 순회(postorder): 왼쪽 서브트리를 리프 노드부터 돌고, 오른쪽을 돈 뒤에 노드를 방문
4. 레벨 순서 순회(level order, 너비 우선 순회): 레벨 순서 순회(level-order)는 모든 노드를 낮은 레벨부터 차례대로 순회한다.

예시

전위 순회: F, B, A, D, C, E, G, I, H (root, left, right)
중위 순회: A, B, C, D, E, F, G, H, I (left, root, right)
후위 순회: A, C, E, D, B, H, I, G, F (left, right, root)
레벨 순서 순회: F, B, G, A, D, I, C, E, H

4. 이진 트리와 이진 탐색 트리

• 이진 트리는 최대 차수가 2인 트리를 말한다. (=각 노드가 최대 2개의 자식 노드를 가질 수 있다)
• 이는 하나의 노드에 LEFT or RIGHT만 존재한다고 표현한다. left node는 부모 node의 값 보다 적은 값이 저장되고 right node는 같거나 큰 값을 저장한다.

4.1 이진 트리

- 편향 이진 트리

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

- 포화 이진 트리

full binary tree. 포화이진 트리는 Leaf Node를 제외한 모든 노드의 차수가 두개로 이뤄진 경우를 말한다. 이 경우에는 해당 차수에 몇개의 노드가 존재하는지 바로 알수 있어 개수 파악이 용이하다는 장점이 있다.

- 완전 이진 트리

complete binary tree. 포화 이진트리와 같은 개념으로 생성하지만 모든 노드가 왼쪽부터 차근차근 생성되는 이진 트리를 말한다.

4.2 이진 탐색 트리

- 이진 탐색 트리

binary search tree. 이진 탐색 트리에서는 항상 부모 노드가 왼쪽 자식보다는 크고, 오른쪽 자식보다는 작다.
이러한 특성 덕분에 이진탐색트리에서는 한번 확인할때 ㅁ마다 보아야 하는 원소의 개수가 절발씩 줄어든다는 점에서 '완전 이진 트리'인 경우 탐색시간에 O(logN)의 시간복잡도를 가진다.

이진 탐색 트리에서 탐색(traverse)을 할 때는 찾고자 하는 값이 부모 노드보다 작을 경우 왼쪽 자식으로, 찾고자 하는 값이 부모 노드보다 클 경우 오른쪽 자식으로 이어 나가면서 방문 한다. 이진 탐색트리는 이진 탐색이 항상 동작하도록 구현하여 탐색 속도를 극대화시킨 자료구조다.

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))