😘 트리란?
많은 자료 구조들은 기본적으로 선형 구조를 나타내기 위해 사용됩니다. 하지만 세상은 이것만으로 표현할 수 있을 만큼 만만치 않습니다. 선형으로 표현하기 어려운 형태의 자료 중 흔한 것으로 계층 구조가 있습니다. 자료 간 상하위 관계나 포함 관계가 존재하는 경우 계층 구조가 생깁니다. 이런 계층적 구조를 갖는 자료들을 표현하기 위한 자료 구조가 바로 트리(tree)입니다.
트리는 처음에 현실 세계의 개념을 추상화해 표현하는 자료구조로 고안되었지만, 탐색형 자료구조로도 유용하게 쓰입니다. 특정 조건을 지키도록 구성된 트리들을 이용하면 배열이나 리스트를 사용하는 것보다 같은 작업을 더 빠르게 할 수 있기 때문입니다. 예를 들어 이진트리의 경우 하위 숫자 최대 두개까지 있으며 왼쪽 가지를 따라 내려가면 더 작은 수를 그리고 오른쪽 가지를 따라 내려가면 더 큰 수를 만날 수 있습니다. 따라서 이와 같은 속성을 사용하면 자료들을 좀 더 빠르게 찾을 수 있고 해결할 수 있습니다. 그렇다면 트리가 무엇인지 자세히 알아보자.
트리의 구성 요소
트리는 자료가 저장된 노드들이 간선으로 서로 연결되어 있는 자료구조입니다. 노드 간에는 상/하위 관계가 있으며, 그 중 상위 노드를 부모노드 , 하위 노드를 자식노드라고 부릅니다. 부모 노드가 같은 두 노드는 형제노드라고 합니다. 그리고 모든 노드들의 최종 부모를 루트 노드라고 하고 , 자식 노드가 없는 노드들을 리프 노드라고 부릅니다.
1. 트리와 노드의 속성
루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수를 해당 노드의 깊이라고 합니다. 이때, 트리에서 가장 깊숙히 있는 노드의 깊이를 해당 트리의 높이라고 합니다.
2. 트리의 재귀적 속성
트리에서 한 노드와 그의 자손들을 모두 모으면 그들도 하나의 트리가 된다. 예를 들어 어떤 노드 t와 그 자손들로 구성된 트리를 t를 루트로 하는 서브트리라고 말합니다. 따라서 모든 트리는 루트와 루트 밑에 있는 서브트리들의 집합이라고 말할 수 있습니다.
3. 트리의 구현
트리는 다양한 방법으로 구현할 수 있지만 그중에서 가장 일반적인 형태는 각 노드들을 객체로 표현하고, 이들을 서로의 포인터로 연결하는 것입니다. 이때 각 노드들은 자신의 부모와 모든 자손들에 대한 포인터를 가지고 있습니다. 이렇게 할 경우 메모리를 상당히 절약할 수 있습니다.
간단한 이진 탐색 트리의 구현, 탐색, 삭제 연산 등을 보여주도록 하겠다.
😂 트리 구성
1) 클래스 정의, 초기화
이진 탐색 트리를 구현하려면 먼저 그 재료가 되는 Node 클래스를 정의해야 한다. Node 클래스는 노드값(self.data)과 좌/우 노드(self.left, self,right), 총 세 개의 속성을 가진다. 초기화 할 때는 데이터 값만 주어지고 좌우 노드가 비어 있다.
#클래스 정의
class Node(object):
def __init__(self, data):
self.data = data
self.left = self.right = None
만든 노드 클래스를 가지고 이진 탐색 트리 클래스인 BinarySearchTree를 구현해보자. 처음에는 비어있는 트리이다.
class BinarySearchTree(object):
#클래스 초기화
def __init__(self):
self.root = None
이제 여기에 원소를 추가, 탐색, 삭제할 수 있도록 insert(), delete(), find()메서드를 추가해야 한다.
2) 삽입 메서드
재귀를 사용해 트리에 새 원소를 추가해보자. 새로 추가할 원소의 값을 현재 루트 값과 비교하여 왼쪽/오른쪽 중 알맞은 위치로 노드를 삽입한다.
#삽입 메서드
def insert(self, data):
self.root = self._insert_value(self.root, data)
return self.root is not None
def _insert_value(self, node, data):
if node is None:
node = Node(data)
else:
if data <= node.data:
node.left = self._insert_value(node.left, data)
else:
node.right = self._insert_value(node.right, data)
return node탐색 메서드
이 역시 재귀와 대소관계 비교를 통해 쉽게 구현할 수 있다.
#탐색 메서드
def find(self, key):
return self._find_value(self.root, key)
def _find_value(self, root, key):
if root is None or root.data == key:
return root is not None
elif key < root.data:
return self._find_value(root.left, key)
else:
return self._find_value(root.right, key)이진 트리의 좌우 균형이 맞으면 탐색/ 삽입/ 삭제의 시간 복잡도가 O(log n)이다. 그러나 이진 탐색트리 는 정렬된 데이터에 취약하다. 오름차순이든 내림차순이든 정렬된 데이터가 입력되면 한쪽으로 치우친 트리가 만들어 진다. 이때 최악의 시간복잡도는 O(n)이 된다.
