-
[OOP] Binary Search Tree 자료구조 만들기Python 2023. 3. 20. 19:28
Binary Search Tree란?
- 이진 탐색 트리
- Binary Tree : 오직 두 개의 자식을 가지는 tree구조
- Binary Search Tree : 부모의 왼쪽 자식은 부모의 데이터값보다 작은 값을 가짐, 오른쪽 자식은 크거나 같은 값을 가짐
Binary Search Tree의 장점
1. 이진 탐색의 장점 -> 탐색 시간복잡도 O(logN), 삽입 삭제 불가능
2. 연결리스트의 장점 -> 데이터의 삽입 삭제 가능
Binary Search Tree의 시간복잡도
데이터 삽입, 삭제, 탐색 -> O(logN)
Binary Search Tree의 기본 구성 요소
- Attribution ( 속성 )
- Node
1. 데이터 값
2. left child, right child
class Node: def __init__(self, data=None): self.data = data self.left = None self.right = None
- BST ( Binary Search Tree )
1. Root ( Head )
class BinarySearchtree: def __init__(self): self.root = Node(None)
Binary Search Tree의 주 기능 ( Method )
class BinarySearchtree: def __init__(self): self.root = Node(None) def insert(self, value): new_node = Node(value) if self.root.data is None: self.root = new_node return else: current_node = self.root while True: if value >= current_node.data: if current_node.right is None: current_node.right = new_node return else : current_node = current_node.right else : if current_node.left is None: current_node.left = new_node return else : current_node = current_node.left def print_tree(self): # bfs method need_visited = deque() need_visited.append(self.root) while need_visited: current_node = need_visited.popleft() if current_node.data is not None: print(current_node.data, end=" ") if current_node.left is not None: need_visited.append(current_node.left) if current_node.right is not None: need_visited.append(current_node.right) print() def find(self, value): current_node = self.root if current_node.data is None: return False while True: if value > current_node.data: if current_node.right is None: return False else: current_node = current_node.right elif value < current_node.data: if current_node.left is None: return False else: current_node = current_node.left else: return True BST = BinarySearchtree() BST.insert(10) BST.insert(5) BST.insert(15) BST.insert(3) BST.insert(12) BST.insert(7) BST.print_tree() # 출력 # 10 5 15 3 7 12 print(BST.find(7)) # 출력 # True print(BST.find(8)) # 출력 # False
'Python' 카테고리의 다른 글
[OOP] Linked List 자료구조 만들기 (0) 2023.03.19 [프로그래밍 언어] Python Class 객체 지향(Object Oriented) (0) 2023.03.19 [프로그래밍 언어] Python 기초 (0) 2023.03.16 [Python] Heapq 모듈로 힙(Heap) 구현하기 (0) 2022.10.20