[Python] 이진 탐색 트리(BST)와 트리 순회

■

 

이진 탐색 트리 (Binary Search Tree)

노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이뤄져 있는 반면, 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있는 트리

이진 탐색 트리 (BST)

위 그림을 보면 이진 탐색 트리가 어떻게 생겨먹은 것인지 이해할 수 있을 것이다.

 

대충 어떤 것인지 알았다면 이제 이 그림에서 원하는 값을 찾는 과정을 살펴볼 것이다.

 

 

 

■■

 

위 이진 탐색 트리에서 우리는 '7'을 찾아 볼 것이다.

당연하지만 루트인 '15'부터 시작한다.

1. '7'은 '15'보다 작기 때문에 왼쪽 자식 노드로 탐색이 진행된다.

2. '10' 또한 마찬가지로 '7'이 더 작기 때문에 왼쪽 자식 노드로 탐색이 진행된다.

3. 여기서부터 '7'은 '5'보다 크기 때문에 오른쪽 자식 노드로 탐색한다.

4. '6'도 마찬가지로 '7'이 더 크기 때문에 오른쪽 자식 노드로 탐색한다.

5. 드디어 원하는 값인 '7'을 찾아냈다.

 

이 탐색의 시간복잡도는 O(logn) 이다.

 

균형이 깨진 이진 탐색 트리

만약 위 그림처럼 균형이 깨진 이진 탐색 트리가 된다면 시간 복잡도가 O(n)에 근접한 시간이 될 것이다.

여기서 '7'을 찾는다고 했을때 루트에서부터 하나씩 차례대로 탐색해야되기 때문에 굉장히 비효율적이다.

 

그렇다면 이렇게 균형이 깨진 이진 탐색 트리를 다시 균형을 맞추면 되지 않을까?

 

 

 

■■■

 

자, 이제 균형이 깨진 이진 탐색 트리를 다시 균형을 맞추는 방법을 알아 볼 것이다.

바로 삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진 탐색트리인 '자가 균형 이진 탐색 트리'

 

자가 균형 이진 탐색 트리는 최악의 경우에도 이진 트리의 균형이 잘 맞도록 유지한다. 그리고 불균형과 균형의 차이는 크게 높이로 구분할 수 있다. 대표적으로 AVL트리와 레드-블랙 트리 등이 있으며 레드-블랙 트리가 높은 효율성으로 자주 쓰인다.

 

이후 자가 균형 이진 탐색 트리에 대한 설명은 길기 때문에 따로 글을 올려야할 것 같다.

 

 

 

 

■■■■

 

트리 순회

그래프 순회의 한 형태로 트리 자료 구조에서 각 노드를 정확히 한 번 방문하는 과정

 

트리 순회는 보통 DFS 또는 DFS로 탐색하는데, DFS로 탐색할시 노드의 방문 순서에 따라 크게 3가지로 구분된다.

 

1. 전위(Pre-Order) 순회 (NLR)

2. 중위(In-Order) 순회 (LNR)

3. 후위(Post-Order) 순회 (LRN)

 

뒤에 적힌 L, R, N의 의미는 다음과 같다.

 

L : 현재 노드의 왼쪽 서브트리

R : 현재 노드의 오른쪽 서브트리

N : 현재 노드 자신

 

NLR	현재 노드 순회 후 왼쪽, 오른쪽 순서로 서브트리 순회
LNR	왼쪽 서브트리 순회 후 현재 노드, 오른쪽 서브트리 순서로 순회
LRN	왼쪽, 오른쪽 서브트리 순서로 순회 후 현재 노드 순회

 

 

■■■■■

 

이제 마지막으로 NLR(전위 순회), LNR(중위 순회), LRN(후위 순회)를 구현해보자.

위 트리를 예시로 코드를 구현해 볼 것이다.

 

#트리를 구현하기 전 Node 클래스를 정의하겠다.
class Node:
	def __init__(self, val, left = None, right = None):
		self.val = val #현재 노드
		self.left = left #왼쪽 자식
		self.right = right #오른쪽 자식

자, 이제 진짜 구현해보자.

#트리 구현
tree = Node('F',
            Node('B',
            	Node('A'),
                Node('D',
                	Node('C'), Node('E'))
                ),
            Node('G',
            	None,
                Node('I', Node('H'))
                )
            )

 

 

전위 순회 (Pre-Order)(NLR)

 

#전위 순회
def preorder(node):
    if node is None:
    	return #다음 노드가 없으면 종료(리턴)
    print(node.val) #현재 노드 출력
    preorder(node.left) #왼쪽 자식 순회
    preorder(node.right) #오른쪽 자식 순회

 

 

중위 순회 (In-Order)(LNR)

 

def inorder(node):
    if node is None:
    	return #다음 노드가 없으면 종료(리턴)
    inorder(node.left) #왼쪽 자식 순회
    print(node.val) #현재 노드 출력
    inorder(node.right) #오른쪽 자식 순회

 

 

후위 순회 (Post-Order)(LRN)

 

def postorder(node):
    if node is None:
    	return #다음 노드가 없으면 종료(리턴)
    postorder(node.left) #왼쪽 자식 순회
    postorder(node.right) #오른쪽 자식 순회
    print(node.val) #현재 노드 출력

 

위 코드들을 보면 매우 직관적이므로 어렵지 않게 이해할 수 있을거라 생각한다.