터칭 데이터

힙 (Heaps) 트리, 그 중에서도 이진트리의 한 종류 1. 루트 노드가 언제나 최대값 또는 최소값을 가지는데 대개 파이썬의 경우는 최소힙 heapq에 마이너스 - 를 붙여 최대힙으로 구현한다. 2. 완전 이진 트리여야 한다. 완전 이진 트리 (Complete Binary Tree) 높이가 k인 완전 이진 트리는 레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리면서 레벨 k-1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리를 말한다. 조건을 지키며 정상적으로 구현된 힙이라면 어떤 노드를 루트로 하는 서브트리라도 모두 최대힙이 보장된다. 이진 탐색 트리와의 비교 이진 탐색 트리는 왼쪽 자식은 루트 노드보다 작고 오른쪽 자식은 루트 노드보다 크기 때문에 왼쪽과 오른쪽의 관계가 정의..

트리 (Tree) 정점(node)과 간선(edge)을 이용하여 데이터의 배치를 나타내는 자료 구조 노드의 개념 루트(root)노드: 맨 위에서 시작되는 최초의 노드 리프(leaf)노드: 맨 아래에 위치하고 자식이 없는 말단 노드 부모(parent)노드: 루트 노드에 더 가까우며 자식을 가진 노드 자식(child)노드: 루트 노드로부터 더 멀고 부모를 가진 노드 형제(sibling)노드: 같은 부모를 둔 같은 레벨(level)의 노드들 조상(ancestor)노드: 부모를 비롯한 간선으로 이어진 루트 노드까지의 모든 부모 노드들 후손(descendant)노드: 자식을 비롯한 간선으로 이어진 리프 노드까지의 모든 자식 노드들 노드의 수준(level): 보통은 루트 노드의 레벨을 0으로 둔다. 루트 노드의 레벨..