2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net ** 문제 유형 트리, 구현 ** 풀이 중위 순회를 이용하면 x축을 기준으로 왼쪽부터 방문한다는 특징이 있음 중위 순회 알고리즘을 이용하고, 추가적으로 level 값을 저장하도록 하여 문제 해결 가능 class Node: def __init__(self, number, left_node, right_node): self.parent = -1 # 부모가 존재하는지 확인, 없으면 루트 self.number = number self.left_node..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net ** 문제 유형 트리, 구현 ** 풀이 전위 순회: 루트 -> 왼쪽 자식 -> 오른쪽 자식 중위 순회: 왼쪽 자식 -> 루트 -> 오른쪽 자식 후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 루트 class Node: def __init__(self, data, left_node, right_node): self.data = data self.left_node = left_node self.right_node = right_node def pre_order(..

** 이진 탐색 트리의 시간복잡도 트리의 높이(Depth)를 h라고 하면, 이진 탐색 트리의 시간복잡도는 O(h) n개의 노드를 가진다면, h = log(n) 에 가깝기 때문에, 시간복잡도는 O(log(n)) 동작을 한번 실행 할 때마다 가능한 선택지가 반으로 줄여지기 때문에, 실행시간 역시 반으로 단축시킬 수 있다는 것을 의미한다. ** 이진 탐색 트리의 단점 트리가 균형 잡혀 있을 경우, 평균 시간복잡도 O(log(n)) 최악의 경우, 링크드 리스트와 동일한 성능을 갖게 되고 시간복잡도는 O(n)

** 트리 노드 삭제 3가지 경우의 수를 나눠서 생각 1) Leaf 노드 삭제 시 - 삭제할 노드의 Parent 노드가 삭제할 노드를 가리키지 않도록 한다 2) Child 노드가 1개인 노드 삭제 시 - 삭제할 노드의 Parent 노드가 삭제할 노드의 Child 노드를 가리키도록 한다 3) Child 노드가 2개인 노드 삭제 시 - 삭제할 노드의 오른쪽 자식 중, 가장 작은 값을 삭제할 노드의 Parent 노드가 가리키도록 한다. or - 삭제할 노드의 왼쪽 자식 중, 가장 큰 값을 삭제할 노드의 Parent 노드가 가리키도록 한다. **파이썬 객체지향 프로그래밍으로 트리 구현 ---> (삽입), (탐색), 삭제 class BinarySearchTree: def __init__(self, head): s..

** 파이썬 객체지향 프로그래밍으로 트리 구현 ---> 삽입, 탐색, (삭제) 1) 노드 클래스 구현 class Node: def __init__(self, value): self.value = value self.left = None self.right = None 2) 이진 탐색 트리 구현 class BinarySearchTree: def __init__(self, head): self.head = head # 삽입 def insert(self, value): self.current_node = self.head # 비교대상으로, 헤드부터 시작 while True: if value value: self.current_node = self.current_node.left # 이동 else: self.c..

트리 구현시 로직이 많이 들어가서 알고리즘 같은 느낌을 준다. 구현하기 복잡하기 때문에 자료구조 중에서 면접에서 자주 질문이 나오는 편이다. ** 트리(Tree) 구조 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실사용 예: 이진 트리의 형태로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 ** 용어 정리 Node: 트리에서 데이터를 저장하는 기본 요소. (데이터 + 연결 노드의 Branch 정보) 루트 노드: 트리 맨 위에 있는 노드 레벨: 어떤 노드가 위치한 트리의 층 Parent Node: 어떤 노드의 상위 레벨에 있는 노드 Child Node: 어떤 노드의 하위 레벨에 있는 노드 Leaf Node: Child 노드를 가지지 않는 노드 Sibling (Brothe..