> 자료구조 구현/트리2 트리(tree) 기본 구현 * 객체지향 프로그래밍으로 트리를 구현함 class Node: def __init__(self, value): self.value = value self.left = None self.right = None 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).. 2020. 10. 8. 트리(tree)의 기본 * 트리(Tree): 노드와 간선으로 구성되어 있는 자료 구조 (그래프의 일종으로 Cycle이 일어나지 않는 특징을 가진다) * 이진 트리(Binary Tree): 모든 노드가 최대 2개의 간선을 가지는 트리 * 이진 탐색 트리(Binary Search Tree): 이진 트리 + 규칙 하나 자신보다 왼쪽에 위치한 노드는 자신보다 작은 값을 가지며, 오른쪽 노드는 큰 값을 가진다 * 시간 복잡도: O(log n) (최악의 경우, O(n) - 링크드 리스트와 동일한 성능) - 한번 실행할 때마다, 50%의 실행시간을 단축한다는 것을 의미 - 이미지 출처: www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-inser.. 2020. 10. 6. 이전 1 다음