[알고리즘] 2. 기초적인 자료형 (트리)

1. 트리(Tree)

아직까지도 많이 사용되고, 앞에서 다룬 자료형들보다 더욱 다양한 형태로 개발된 자료형입니다.

트리는 그래프와 유사한 형태이지만, A에서 B라는 노드로 갈 수 있는 한개의 길만 존재하는 자료구조입니다.

이진트리(출처 : 위키)

트리(Tree)는 아래와 같은 요소를 갖고있습니다.

 - Root(루트노드) : 최상의 노드 (위 그림에서 2)

 - parent(부모노드) : 특정 노드의 바로 상위에 연결된 노드 (2는 루트노드이며, 7과 5의 부모노드입니다.)

 - child(자식노드) : 특정노드의 바로 아래에 연결된 노드 (7과 5는 2의 자식노드입니다.)

 - sibling(형제노드) : 같은 부모노드를 갖고있는 노드입니다. (7과 5는 형제노드입니다)

 - leaf(단말노드) : 자식이 없는 최하단의 노드입니다. (2"중복", 5, 11, 4는 단말노드입니다.)

 - Level(레벨) : Root를 Level 1로 두고, 아래로 자식노드로 내려갈 수록 1씩 증가합니다. (6의 경우 Level3)

 - depth(깊이) : 트리의 최대 Level을 의미합니다. 위 트리의 depth는 4입니다.

 - degree(차수) : 특정 노드의 하위 트리의 개수를 의미합니다.

 

 

 

1.1. 이진트리 (Binary Tree)

가장 대표적인 트리의 형태로, 위 그림에서 다루었던 형태입니다.

하나의 노드는 최대 두 개의 자식노드만을 갖을 수 있는 형태입니다. 이진트리를 사용하는 이유는, 자식노드이 수가 최대 2개로 정해져있기 때문에 구현하기 쉽고, 이를 이용하여 다양한 알고리즘을 구현하는것이 가능하다는 장점이 있습니다.

 

 1) BST(Binary Search Tree)

가장 대표적인 탐색알고리즘입니다. BST를 이용하기 위해서는 아래와같은 전재가 필요합니다.

 - 이진트리로 구현되어있을 것

 - 특정 노드를 기준으로 좌측에는 항상 작은 값이, 우측에는 항상 큰 값이 존재해야합니다.

 - 모든 노드는 서로다른 값(키)을 갖고있어야 합니다.

 

class Node():
    def __init__(self, data, left=None, right=None, parent=None):
    	self.value = data
        self.left = left
        self.right = right
        self.parent = parent
    def __str__(self):
    	return str(self.value)
        
class BST:
    def __init__(self):
        self.root = None
    def search(self, target, tree):
        if tree == None: return None
        if tree.value == target: 
            return tree
        if tree.value < target:
            return self.search(target, tree.right)
        else:
            return self.search(target, tree.left)

 

위는 BST의 가장 기본적인 탐색 코드입니다. 각 노드는 부모와, 두 자식 노드를 객체로 갖고있으며, 탐색하기를 원하는 값을 현재의 값과 비교하며 탐색하게 됩니다.

 

BST의 경우, 찾고싶은 값이 최악의 경우에도 Leaf 이하에는 존재할 수 없기 때문에 평균 O(logn)으로 탐색이 가능하다는 장점이 있습니다.

 

BST에서 값을 추가하고, 제거하는 것 역시도 추가 역시도 O(depth)로 가능하다는 장점이 있습니다.

 

 

 

물론 BST도 정말 큰 단점이 있습니다.

 

바로 "Skewed" 라는 현생이 발생할 수 있다는 것입니다.

 

즉, 아래 그림과 같이 한쪽으로만 일방적으로 자식노드가 생길 경우 n개의 노드에 대해서 탐색에 n만큼의 탐색이 필요할 수 있습니다.

 

이러한 문제를 방지하기위해 Bad-Black Tree라는 개념이 등장했습니다.

 

 

 

만........ 정말 많은 이미지를 통한 설명이 필요한 부분이기에... 차후에 뒤에서 다루도록하겠습니다.(꾸벅)