[Algorithm][Python] 데이터구조: 트리(Tree)

데이터구조: 트리(Tree)

1. 트리 (Tree) 구조

• 트리: Node 와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
• 실제로 어디에 많이 사용되나?
  • 트리 중 이진 트리(Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨.

2. 트리 용어

• Node : 트리에서 데이터를 저장하는 기본요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
• Root Node : 트리 맨 위에 있는 노드
• Level : 최상위 노드를 Level 0으로 했을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
• Child Node : 어떤 노드의 상위 레벨에 연결된 노드
• Leaf Node(Terminal Node) : Child Node 가 하나도 없는 노드
• Sibling(Brother Node) : 동일한 Parent Node를 가진 노드
• Depth : 트리에서 Node가 가질 수 있는 최대 Level

3. 이진 트리와 이진탐색 트리( Binary Search Tree)

• 이진 트리 : 노드의 최대 Branch 가 2인 트리
• 이진 탐색 트리 (Binary Search Tree, BST) : 이진 트리에 다음과 같은 추가적인 조건이 있는 트리 - 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가진다.

4. 자료 구조 이진 탐색 트리의 장점과 주요 용도

• 주요 용도: 데이터 검색(탐색)
• 장점 : 탐색속도를 개선할 수 있음

  단점은 이진 탐색 트리 알고리즘 이해 후에 살펴보기로 함

이진트리와 정렬된 배열간의 탐색 비교

5. 파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기

5.1. 노드 클래스 만들기

class Node:
	def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None

5.2. 이진 탐색 트리에 데이터 넣기

• 이진 탐색 트리 조건에 부합하게 데이터를 넣어야 함

class NodeMgmt:
	def __init__(self, head):
		self.head = head

	def insert(self, value):
		self.current_node = self.head
		while True:
			if value < self.current_node.value:
				if self.current_node.left !== None:
					self.current_node = self.current_node.left
				else:
					self.current_node.left = Node(value)
			else:
				if self.current_node.right !== None:
					self.current_node = self.current_node.right
				else:
					self.current_node.right = Node(value)
					break

head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)

5.3. 이진 탐색 트리 탐색

class NodeMgmt:
	def __init__(self, head):
		self.head = head

	def insert(self, value):
		self.current_node = self.head
		while True:
			if value < self.current_node.value:
				if self.current_node.left != None:
					self.current_node = self.current_node.left
				else:
					self.current_node.left = Node(value)
					break
			else:
				if self.current_node.right != None:
					self.current_node = self.current_node.right
				else:
					self.current_node.right = Node(value)
					break

	def search(self, value):
		self.current_node = self.head
		while self.current_node:
			if self.current_node.value == value:
				return True
			elif value < self.current_node.value:
				self.current_node = self.current_node.left
			else:
				self.current_node = self.current_node.right
		return False

head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)
BST.insert(3)
BST.insert(0)
BST.insert(4)
BST.insert(8)

BST.search(-1)

# False

5.4. 이진 탐색 트리 삭제

• 매우 복잡함. 경우를 나누어서 이해하는 것이 좋다
• Leaf Node 삭제
• Child Node가 하나인 Node 삭제
• Child Node 가 두개인 Node 삭제

5.4.1. Leaf Node 삭제

• Leaf Node: Child Node 가 없는 Node
• 삭제할 Node의 Parent Node 가 삭제할 Node를 가리키지 않도록 한다.

5.4.2. Child Node 가 하나인 Node 삭제

• 삭제할 Node 의 Parent Node 가 삭제할 Node 의 Child Node 를 가리키도록 한다.

5.4.3. Child Node 가 두개인 Node 삭제

1. 삭제할 Node 의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node 의 Parent Node가 가리키도록 한다.
2. 삭제할 Node 의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node 의 Parent Node 가 가리키도록 한다.

5.4.3.1. 삭제할 Node 의 오른쪽 자식 중 , 가장 작은 값을 삭제할 Node 의 Parent Node 가 가리키게 할 경우

• 삭제할 Node 의 오른쪽 자식 선택
• 오른쪽 자식의 가장 왼쪽에 있는 Node 를 선택
• 해당 Node를 삭제할 Node의 Parent Node 의 왼쪽 Branch가 가리키게 함
• 해당 Node 의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함
• 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node 를 가리키게 함
• 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 함

6. 이진 탐색 트리의 시간복잡도와 단점

6.1. 시간 복잡도 (탐색시)

• depth (트리의 높이) 를 h 라고 표기한다면, O(h)
• n개의 노드를 가진다면, ℎ=𝑙𝑜𝑔2𝑛 에 가까우므로, 시간복잡도는 O(logn)
  • 참고: 빅오 표기법에서 logn에서의 log 의 밑은 10이 아니라 2다.
    • 한번 실행시마다 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있음.

6.2. 이진탐색 트리 단점

• 평균 시간 복잡도는 O(logn) 이지만, 트리가 균형잡혀 있을 때의 평균 시간복잡도이며,
• 다음 예와 같이 구성되어 있을 경우, 최악의 경우는 Linked List 와 동일한 성능을 보여줌(O(n))