Stack, Queue 등과는 다르게 계층적 구조를 표현할 수 있는 비선형적인 자료구조이다. (가계도와 같은 표현)
기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개가 된다.
부모 밑의 자식 노드 개수를 2개로 제한하는 가장 간단한 형태의 트리이다.
루트 노드를 중심으로 두개의 서브트리로 나뉘고 나뉘어진 두 서브트리도 각각 이진 트리이어야 한다.
트리의 각 층별로 숫자를 매기고 Level(레벨)이라고 한다.
레벨은 0부터 시작하고 루트노드의 레벨은 0이다.
(루트를 1부터 시작하는 경우도 있으나 일반적으로는 0부터 시작한다.)
배열로 구성된 Binary Tree는 노드의 개수가 n 개이고 root가 0이 아닌 1에서 시작할 때, i 번째 노드에 대해서 parent(i) = i/2 , left_child(i) = 2i , right_child(i) = 2i + 1 의 index 값을 갖는다.
트리 자료구조에 포함된 노드를 특정 방법으로 한번씩 방문하는 방법
-> 트리의 정보를 시각적으로 확인할 수 있다.
위의 트리를 순회 결과
In-order: 1 3 4 6 7 8 10 13 14
Pre-order: 8 3 1 6 4 7 10 14 13
Post-order: 1 4 7 6 3 13 14 10 8
Level-order: 8 3 10 1 6 14 4 7 13
이진 탐색이 동작할 수 있도록 고안된 자료구조로 이진 트리의 일종이다.
이진 트리의 탐색은 O(log n)의 시간 복잡도를 갖는다. 하지만 이진 탐색트리는 한쪽에만 노드가 추가되는 편향트리(Skewed Tree)가 될 가능성이 있다. 이 경우에는 성능에 영향을 미치게 되고 worst case에서 시간 복잡도는 O(n)이 된다.
효율적인 이진 탐색을 하기 위해서는 트리구조의 좌우 균형이 잡혀있어야 한다.
배열보다 많은 메모리를 사용하며 데이터를 저장했지만 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황이 발생한다. 이를 해결하기 위해 Rebalancing
기법이 등장한다. (균형을 잡기 위한 트리 구조의 재조정) 이 기법을 구현한 트리에는 여러 종류가 존재하는데 그 중에서 하나가 Red-Black Tree이다.
Zed0202 블로그
...
class Node:
def __init__(self,key):
self.key = key
self.parent = None
self.left = None
self.right = None
def __str__(self): # print문의 출력값
return str(self.key)
'''
a = Node(6)
b = Node(9)
c = Node(1)
d = Node(5)
a.left = b
a.right = c
b.parent = a
b.right = d
a.parent = a
'''
class Node:
def __init__(self,key):
self.key = key
self.parent = None
self.left = None
self.right = None
# 각 함수를 재귀적으로 호출한다.
def preorder(self):
if self != None:
print(self.key) ### MLR
if self.left:
self.left.preorder()
if self.right:
self.right.preorder()
def inorder(self):
if self != None:
if self.left:
self.left.inorder()
print(self.key) ### LMR
if self.right:
self.right.inorder()
def postorder(self):
if self != None:
if self.left:
self.left.postorder()
if self.right:
self.right.postorder()
print(self.key) ### LRM