이진탐색트리 Binary Search Tree 탐색, 삽입, 삭제, 순회 search, insert, delete, traverse 구현하기

이진탐색트리 Binary Search Tree

---

• 이진탐색트리의 개념

• 각 노드의 왼쪽 서브트리에는 현재 노드보다 작은 값을 가진 노드만 있다.
• 각 노드의 오른쪽 서브트리에는 현재 노드보다 큰 값을 가진 노드만 있다.
• 중복 노드가 없다.
• inorder traverse를 한다 (왼쪽 - 루트 - 오른쪽) → 오름차순 정렬 가능

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

class BinarySearchTree:
		def __init__(self):
				self.root = None
		def setRoot(self,value):
				self.root = Node(value)

• 탐색 Search

class BinarySearchTree:
		...
		def search(self, value):
				if (self._search(self.root, value) is False):
						return False
				else:
						return True
		def _search(self, currentNode, value):
				# 재귀 함수의 base condition (더 이상 노드가 없으면 False 반환 후 종료)
				if (currentNode is None):
						return False 
				# 일치하는 값을 발견하면 해당 노드 반환 
				elif (value == currentNode.value):
						return currentNode
				# 값이 현재 노드보다 작으면 왼쪽으로 순회 시작 (재귀)
				# 중복이 없으므로 <,>
				elif (value < currentNode.value):
						return self._search(currentNode.left, value)
				# 값이 현재 노드보다 크면 오른쪽으로 순회 시작
				elif (value > currentNode.value):
						return self._search(currentNode.right, value)
				

시간복잡도 : O(h)

최악의 경우 리프 노드까지 탐색하기 때문에 루트 - 리프 길이인 h만큼 소요될 수 있다. 

• 삽입 Insert

class BinarySearchTree:
		...
		def insert(self, value):
				# BST의 root이 null인 경우 
				if(self.root is None):
						self.setRoot(value)
				else:
						self._insert(self.root, value)
		
		def _insert(self, currentNode, value):
				if (value <= currentNode.value):
						# 현재 노드에 왼쪽 자식이 있다면
						if (currentNode.left):
								self._insert(currentNode.left, value)
						# 더이상 왼쪽 자식이 없다는 것 = 현재 노드가 리프 노드임을 의미
						else:
								currentNode.left = Node(value)
				elif (value > currentNode.value):
						if (currentNode.right):
								self._insert(currentNode.right, value)
						else:
								currentNode.right = Node(value)

• 삭제 Delete

case 1) 삭제할 노드에 자식 노드가 없는 경우

→ 그냥 없애면 된다.

 

case 2) 삭제할 노드에 자식 노드가 하나 있는 경우

→ 해당 노드를 지우고 해당 노드의 자식노드와 부모 노드를 연결한다.

(삭제할 노드의 자식을 부모노드 자식으로 만든다.)

 

case 3) 삭제할 노드에 자식 노드가 두개 있는 경우

• predecessor : 삭제할 노드의 왼쪽 서브트리 중 최대값
• successor : 삭제할 노드의 오른쪽 서브트리 중 최소값

→ successor을 삭제할 노드 자리에 복사해놓고 기존 successor 위치의 노드를 삭제 (predecessor로도 가능)

case 3-1) successor의 자식 노드가 하나인 경우

case 3-2) successor의 자식 노드가 없는 경우

case 3-3) successor의 자식 노드가 둘인 경우

 

• 과정
  1. 삭제할 노드의 오른쪽 서브트리에서 successor을 찾는다.
  2. successor을 삭제할 노드 위치에 복사한다.
  3. successor을 삭제한다.

class BinarySearchTree:
		...
		def delete(self, value):
				if (currentNode is None):
						return False
				elif value < currentNode.value:
						currentNode.left = self._delete(currentNode.left, value)
				elif value > currentNode.value:
						currentNode.right = self._delete(currentNode.right, value)
				# 삭제할 노드를 찾으면 _delete 호출
		
		def _delete(self, currentNode, value):
				# currentNode = 삭제할 노드가 자식 노드가 없는 경우 그냥 지움
				if (not currentNode.left and not currentNode.right):
						currentNode = None
				# 삭제할 노드가 자식 노드 하나를 가지고 있는 경우 
				# -> 자식 노드를 삭제할 노드 위치로 복사하고 자식 노드 삭제 
				elif (not currentNode.left):
						currentNode = currentNode.right
				elif (not currentNode.right):
						currentNode = currentNode.left
				# 삭제할 노드가 자식 노드 두개를 가지고 있는 경우 
				else:
						# 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 수를 대체자로 선정
						successor = currentNode.right
						while successor:
								successor = successor.left
								currentNode.value, successor.value = successor.value, currentNode.value
						currentNode.left = self._delete(currentNode.left, successor.value)
				return currentNode

				
						

• 순회 Traverse

class BinarySearchTree:
		...
		def traverse(self):
				return self._traverse(self.root)
		def _traverse(self, currentNode):
				result = []
				if (currentNode.left is not None):
						result.extend(self._traverse(currentNode.left))
				if (currentNode.right is not None):
						result.extend(currentNode.value)
				if (currentNode.right is not None):
						result.extend(self._traverse(currentNode.right))
				return result

---

References

• ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/