트리 용도 용어 정리 종류 이진 트리 일반 트리 스레드 이진 트리 구현 배열 표현법 연결리스트 표현법 트리 활용 탐색 집합 표현 허프만 코드 트리 트리란 그래프의 한 종류로 무방향 연결 비순환 그래프(Connected Undirected Acyclic Graph)이다. 루트 노드가 존재하고, 루트 노드를 제외한 모든 노드의 in-degree가 1인 방향그래프라고 말할 수도 있다. 계층적인 구조를 가지며 그래프의 한 종류이므로 비선형 자료구조에 속한다. 용도 계층적인 조직을 표현하기 위해 사용되거나, 컴퓨터의 디렉토리 구조 / 인공지능의 decision tree 등에 이용된다. 또한 자료의 탐색 / 정렬 / DB 구성이나 분자구조식 설계 등에서도 다양하게 이용된다. (결정트리)(이진탐색) 용어 정리 노드 ..

서론 자료구조 자료구조는 컴퓨터에서 자료를 정리하고 조직화하는 다양한 구조를 말한다. 프로그램은 자료구조와 알고리즘으로 이루어져있기 때문에, 자료구조는 반드시 공부해야하는 분야이다. 자료구조는 먼저 단순 자료구조와 복합 자료구조로 구분되고, 복합 자료구조에는 선형 구조와 비선형 구조가 있다. 순차적으로 살펴보자. 배열, 문자열 연결 리스트 스택, 큐, 덱 그래프 트리 힙 구조체

세그먼트 트리 https://www.acmicpc.net/blog/view/9 백준님 글 배열 크기 결정 세그먼트 트리를 만들기 위해서 C++의 경우, vector 자료형을 사용하는데 python으로 구현할 것이기 때문에 배열을 사용하려고 한다. 배열의 크기가 얼마나 되어야 할지 가늠하기 위해 크기를 결정해보자. 2의 제곱 수가 리프 노드의 수(n)로 주어진다면 ( 분석해야할 data 갯수가 2의 제곱 수라면 ) 각 단계마다 1/2씩 줄어나가므로 log(n)이 필요한 총 단계(화살표)가 되고 전체 층의 갯수, 즉 높이(h)는 log(n)+1이 된다. 최상위 노드부터 2^(0)개의 노드로 시작하여 층이 증가할 수록 2의 지수 또한 증가하기 때문에 꽉찬 이중 트리(full binary tree)의 총 노드 ..