이진 탐색 트리
이진 탐색을 위한 이진 트리
•
이진 탐색은 데이터 집합이 배열인 경우에만 사용할 수 있기에 이진 탐색을 하기 위해서 데이터 집합의 처음과 끝을 알아야하고, 데이터 집합의 중앙 인덱스를 즉각 계산할 수 있어야 하며, 계산된 중앙 요소에 인덱스로 즉시 접근이 가능해야한다.
•
링크드 리스트는 처음과 끝의 위치는 알고 있어도 중앙 요소는 알 수 없다. 따라서 이진 트리로 이 문제를 해결한다.
from dataclasses import dataclass
@dataclass
class Node:
def __init__(self, data: int):
self.data = data
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, data: int):
self.root = self._insert_data(self.root, data)
return self.root is not None
def _insert_data(self, node, data):
if node is None:
node = Node(data)
else:
if data <= node.data:
node.left = self._insert_data(node.left, data)
else:
node.right = self._insert_data(node.right, data)
return node
def delete(self, data):
self.root, deleted = self._delete_data(self.root, data)
return deleted
def _delete_data(self, node, data):
if node is None:
return node, False
deleted = False
if data == node.data:
deleted = True
if node.left and node.right:
parent, child = node, node.right
while child.left is not None:
parent, child = child, child.left
child.left = node.left
if parent != node:
parent.left = child.right
child.right = node.right
node = child
elif node.left or node.right:
node = node.left or node.right
else:
node = None
elif data < node.data:
node.left, deleted = self._delete_data(node.left, data)
else:
node.right, deleted = self._delete_data(node.right, data)
return node, deleted
def find(self, data: int):
return self._find_data(self.root, data)
def _find_data(self, root, data: int):
if root is None or root.data == data:
return root is not None
elif data < root.data:
return self._insert_data(root.left, data)
else:
return self._insert_data(root.right, data)
def preorder_traversal(self):
def _preorder_traversal(root: Node):
if root is None:
pass
else:
print(root.data, end=" ")
_preorder_traversal(root.left)
_preorder_traversal(root.right)
_preorder_traversal(self.root)
def inorder_traversal(self):
def _inorder_traversal(root: Node):
if root is None:
pass
else:
_inorder_traversal(root.left)
print(root.data, end=" ")
_inorder_traversal(root.right)
_inorder_traversal(self.root)
def levelorder_traversal(self):
def _levelorder_traversal(root: Node):
queue = [root]
while queue:
root = queue.pop(0)
if root is not None:
print(root.data, end=" ")
if root.left:
queue.append(root.left)
if root.right:
queue.append(root.right)
_levelorder_traversal(self.root)
Python
