Session - Tree

Tree

Tree 자료구조는 데이터를 나무(거꾸로된) 형태로 저장하는 자료 구조이다. 데이터 요소들이 부모-자식 관계의 계층적 구조로 표현이 된다. 윈도우와 리눅스의 파일스스템 구조도 트리로 표혀노딘다. 대용량의 데이터를 저장할때도 많이 쓰인다. 데이터의 저장의 의미 보다는 저장된 데이터를 더 효과적으로 탐색 하기 위해서 사용된다.

주요 용어

• Node : Tree 구조를 구성하는 기본 요소로써 Tree 구조의 교점이다. Node는 데이터를 가지고 있고 자식노드 또한 가지고 있다.

• Root Node : Tree의 가장 위 노드, 즉 시작점이 되는 노드이다.

• Edge(간선) : Tree를 구송하기 위해 노드와 노드를 연결하는 선이다.

• level : Tree의 특정 깊이를 가지는 노드의 집합이다.

• degree(차수): 특정 노드가 지닌 자식의 수를 말한다

• Leaf Node : 하위에 자식 노드가 연결되어 있지 않은 노드이다. 그러므로 degree(차수)는 0이다.

이진 트리 (Binary Tree)

Tree 자료구조의 가장 기본적인 형태인 binary tree(이진 트리) 자료구조는 두 개의 자식 노드를 가진 트리 형태이다. 이진 트리에는 다음과 같은 유형이 존재한다

• 편향 이진 트리 (Skewed Binary Tree) : 하나의 차수로만 이루어진 선형 구조의 이진 트리이다. 한쪽으로 기울어진 형태를 가지고 있고 사향 이진트리라고 부르기도 한다.
  

• 포화 이진 트리 (Full Binary Tree) : Leaf 노드를 제외한 모든 노드의 degree(차수)가 두 개로 이루어진 Tree이다. 그러므로 노드의 개수 파악이 용이하다.
  

• 완전 이진 트리 (Complete Binary Tree) : 포화 이진트리와 같은 개념으로 생성하지만 노드를 삽입할때 왼쪽부터 차례대로 삽입한다.

이진 트리 탐색 (Binary Search Tree)

이진 탐색 Tree에서는 항상 부모 노드가 왼쪽 자식 노드보다는 크고, 오른쪽 자식노드보다는 작다. 따라서 한번 확일할때 마다 보아야 하는 원소의 개수가 절반씩 줄어든다는 점에서 O(logN)의 시간복잡도를 가진다.

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

실행결과

 -- /home/sungjunjin/바탕화면/tree.py 
7 Not Found
14 is found
None