데이터 분석 기술 블로그

트리 (비선형)노드와 간선으로 구성된 계층적 자료 구조이진트리: 각 노드가 최대 두 개의 자식을 가짐이진 탐색 트리: 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼힙: 최소값 / 최댓값을 빠르게 찾기 위한 완전 이진트리 (게임 리더보드)삽입 / 삭제 → O(log n)탐색 → BST는 O(log n) 일반 트리는 O(n)

1. 힙(heap)완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조입니다.최대 힙(max heap)키 값이 가장 큰 노드를 찾기 위한 완전 이진트리부모 노드의 키 값 > 자식 노드의 키 값루트 노드 : 키 값이 가장 큰 노드최소 힙(min heap)키 값이 가장 작은 노드를 찾기 위한 완전 이진트리부모 노드의 키 값 루트 노드 : 키 값이 가장 작은 노드2. 힙 연산 - 삽입3. 힙 연산 - 삭제힙에서는 루트 노드의 원소만을 삭제할 수 있습니다.루트 노드의 원소를 삭제하여 반환합니다.힙의 종류에 따라 최댓값 또는 최솟값을 구할 수 있습니다.우선순위 큐와 비교4. 힙의 활용

1. 이진 탐색 트리2. 이진 탐색 트리의 연산3. 이진 탐색 트리 - 성능

1. 이진트리(Binary Tree)2. 이진 트리 - 특성3. 이진 트리 - 종류4. 이진 트리 - 순회(traversal)5. 트리의 표현6. 트리의 표현 - 연결리스트7. 연습 문제

1. 문제 제시 : 계산기2. 트리(Tree)트리는 사이클이 없는 무향 연결 그래프입니다.두 노드(or 정점) 사이에는 유일한 경로가 존재합니다.각 노드는 최대 하나의 부모 노드가 존재할 수 있습니다.각 노드는 자식 노드가 없거나 하나 이상이 존재할 수 있습니다.3. 트리 용어

1. 힙(heap)완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조입니다.최대 힙(max heap)키값이 가장 큰 노드를 찾기 위한 완전 이진트리입니다.{ 부모노드의 키값 >  자식노드의 키값 }루트 노드 : 키값이 가장 큰 노드최소 힙(min heap)키값이 가장 작은 노드를 찾기 위한 완전 이진트리입니다.{ 부모노드의 키값  루트 노드 : 키값이 가장 작은 노드2. 힙을 이용한 우선순위 큐

1. 이진 탐색 트리2. 이진 탐색 트리 - 연산3. 이진 탐색 트리 - 성능4. 이진 탐색 트리 - 연산 연습

1. 이진트리의 저장2. 이진 트리의 표현 - 배열배열을 이용한 이진 트리의 표현의 단점편향 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비가 발생합니다.트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 경우 배열의 크기 변경이 어려워 비효율적입니다.배열을 이용한 이진 트리의 표현의 단점을 보완하기 위해 연결리스트를 이요하여 트리를 표현할 수 있습니다.3. 연습문제4. 수식 트리