[자료구조] 트리(Tree)

👨🏻‍🏫 fastcampus 알고리즘/기술면접 완전 정복 올인원패키지 - 이준희 강사님

1. 트리 구조

• 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 (Brother Node) : 트리에서 Node가 가질 수 있는 최대 Level

출처: https://hanamon.kr/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-tree-%ED%8A%B8%EB%A6%AC/

 

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

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

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

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

5. 트리 파이썬 전체 코드 구현

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

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

	def delete(self, value):
			# 삭제할 노드 탐색
			searched = False
			self.current_node = self.head
			self.parent = self.head
			while self.current_node:
				if self.current_node.value == value:
					searched = True
					break
				elif value < self.current_node.value:
					self.parent = self.current_node
					self.current_node = self.current_node.left
				else:
					self.parent = self.current_node
					self.current_node = self.current_node.right

			if searched == False
				return False

		# case 1
		if self.current_node.left == None and self.current_node.right == None :
			if value < self.parent.value:
				self.parent.left = None
			else:
				self.parent.right = None
		
		# case 2
		elif self.current_node.left != None and self.current_node.right == None:
			if value < self.parent.value:
					self.parent.left = self.current_node.left
			else:
					self.parent.right = self.current_node.left
		elif self.current_node.left == None and self.current_node.right != None:
			if value < self.parent.value:
				self.parent.left = self.current_node.right
			else:
				self.parent.right = self.current_node.right

		# case 3
		elif self.current_node.left != None and self.current_node.right != None:
			# case 3-1
			if value < self.parent.value:
				self.change_node = self.current_node.right
				self.change_node_parent = self.current_node.right
				while self.change_node.left != None:
					self.change_node_parent = self.change_node
					self.change_node = self.change_node.left
				if self.change_node.right != None:
					self.change_node_parent.left = self.change_node.right
				else:
					self.change_node_parent.left = None
				self.parent.left = self.change_node
				self.change_node.right = self.current_node.right
				self.change_node.left = self.current_node.left

			# case 3-2
			else:
				self.change_node = self.change_node.right
				self.change_node_parent = self.current_node.right
				while self.change_node.left != None:
					self.change_node_parent = self.change_node
					self.change_node = self.change_node.left
				if self.change_node.right != None:
					self.change_node_parent.left = self.change_node.right
				else:
					self.change_node_parent.right = self.change_node.right
				self.parent.right = self.change_node
				self.change_node.right = self.current_node.right
				self.change_node.left = self.current_node.left
			
		return True

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

7-1. 시간 복잡도(탐색시)

• depth (트리의 높이)를 h라고 표기한다면, $$O(h)$$
• n개의 노드를 가진다면, $$h = lon_2n$$에 가까우므로, 시간 복잡도는 $$O(logn)$$
  • 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축 시킬 수 있다는 것을 의미

7-2. 이진 탐색 트리 단점

• 평균 시간 복잡도는 $$O(log n)$$이지만,
  • 이는 트리가 균형잡혀 있을 때의 평균 시간복잡도이며,
  • 다음 예와 같이 구성되어 있을 경우, 최악의 경우는 링크드리스트들과 동일한 성능을 보임 $$O(n)$$