Algorithm/Data Structure 썸네일형 리스트형 [트리] Binary Search Tree 개념 트리(Tree)는 노드(Node)와 간선(Edge)의 집합으로 이루어진다. 간선은 노드들의 부모-자식 관계를 정의하며 트리의 첫 번째 노드를 루트(Root) 노드, 자식 노드가 없는 노드를 단말(Leaf) 노드라고 한다.다음은 트리를 기술하는데 사용하는 기본적인 용어들이다.레벨(Level) : 루트 노드로부터의 거리(루트노드의 레벨은 1)높이(Height) : 노드가 가질 수 있는 최대 레벨 = 깊이(Depth)차수(Degree) : 한 노드가 가지는 자식 노드의 개수서브트리(Subtree) : 트리에 속한 노드들의 부분집합포레스트(Forest) : 트리의 집합이진트리 : 자식 노드의 개수가 최대 2개인 트리이진탐색트리(Binary Search Tree)이진 탐색 트리는 기존의 이진 트리에서 몇 가.. 더보기 [정렬] 선택 vs 버블 vs 삽입 정렬의 종류 - 교환(Exchange) : 버블(Bubble), 퀵(Quick) 정렬 - 삽입(Insertion) : 삽입(Intsertion), 셀(Shell) 정렬 - 병합(Merging) : 2-way 병합, n-way 병합 - 분배(Distribution) : 기수(Radix) 정렬 - 선택(Selection) : 선택(Selection), 힙(Heap) 정렬 선택정렬(Selection Sort) 전체 자료 중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환(Exchange)하는 정렬 방식이다. - STEP.1 - STEP.2 - STEP.3 - STEP.4 특성 : 평균 시간복잡도 O(n^2)으로 느린 알고리즘이다. 하지만 최악의 경우도 O(n^2)으로 평균(최선)과 동일하다.정렬의 안정성을 .. 더보기 이전 1 다음
