[자료구조] Binary Search Tree

Binary Search Tree란?

---

👉 개념

Binary Search Tree(BST)는 효율적인 탐색을 위한 데이터 저장 방법이다. 

 

👉 규칙

• 노드에 저장되는 키는 유일하다. 
• 부모의 키 값이 왼쪽 자식 노드의 키 값보다 크다. 
• 부모의 키 값이 오른쪽 자식 노드의 키 값보다 작다. 
• 왼쪽과 오른쪽 서브트리도 BST이다. 

 

👉 장단점

장점
탐색 연산 시간복잡도가 O(log N)이다. (명확히 말하면 O(h))

단점 
편향 트리의 경우 저장 순서에 따라서 한 쪽으로만 노드가 추가되는 경우가 발생한다.
최악의 경우는 탐색 시간복잡도가 O(N)이다.
배열보다 많은 메모리를 사용한다.

 

출처: https://yoongrammer.tistory.com/71

 

 

 

Leetcode 문제를 통한 BST 구현

---

BST를 직접 구현하는 것이 도움이 될 것이라 생각하여 아래 문제를 풀어보았다. 

1. 탐색: https://leetcode.com/problems/search-in-a-binary-search-tree/

Search in a Binary Search Tree - LeetCode

 

2. 삽입: https://leetcode.com/problems/insert-into-a-binary-search-tree/

Insert into a Binary Search Tree - LeetCode

 

3. 삭제: https://leetcode.com/problems/delete-node-in-a-bst/

Delete Node in a BST - LeetCode

 

 

👉 풀이

1. 탐색

	class Solution:
	def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
	node = root
	while node:
	if node.val == val:
	return node
	elif val < node.val:
	node = node.left
	else:
	node = node.right
	return None

view raw BST_Search.py hosted with ❤ by GitHub

 

2. 삽입

	class Solution:
	def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
	if not root:
	return TreeNode(val)
	node = root
	while True:
	if val < node.val:
	if not node.left:
	node.left = TreeNode(val)
	return root
	else:
	node = node.left
	else :
	if not node.right:
	node.right = TreeNode(val)
	return root
	else:
	node = node.right

view raw BST_Insert.py hosted with ❤ by GitHub

 

3. 삭제

	class Solution:
	def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
	def delNode(node):
	if node.left == None and node.right == None: # 리프 노드일 경우
	return None
	elif node.left == None: # 오른쪽 노드만 있을 경우
	return node.right
	elif node.right == None: # 왼쪽 노드만 있을 경우
	return node.left
	# 양쪽 노드가 있을 경우 (오른쪽에서 가장 작은 수를 올린다.)
	prev = node
	minNode = node.right
	while minNode.left:
	prev = minNode
	minNode = minNode.left
	node.val = minNode.val
	if prev.left == minNode:
	prev.left = minNode.right
	else:
	prev.right = minNode.right
	return node
	prev = None
	node = root
	while node:
	if node.val == key:
	break
	elif key < node.val:
	prev = node
	node = node.left
	else:
	prev = node
	node = node.right
	if not node: # 찾지 못 함
	return root
	elif prev == None: # 삭제 노드가 root Node
	return delNode(node)
	elif prev.left == node: # 삭제 노드가 왼쪽에 있는 경우
	prev.left = delNode(node)
	else: # 삭제 노드가 오른쪽에 있는 경우
	prev.right = delNode(node)
	return root

view raw BST_Delete.py hosted with ❤ by GitHub