-
2021.05.16
[C++] 이진 탐색 트리(Binary Search Tree)
이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(Binary Search Tree) 널리 사용되는 형태의 이진 트리(Binary Tree) BST의 속성 왼쪽 노드 ≤ 부모 노드 ≤ 오른쪽 노드 의 관계를 가짐. 부모 노드의 값 ≥ 왼쪽 자식 노드의 값 부모 노드의 값 ≤ 오른쪽 자식 노드의 값 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 이고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있게 됨. 원소 검색을 위해 루트 노드부터 차례대로 값을 비교하는 경우, 각 단계마다 검색 범위가 절반으로 줄어듦. BST가 마지막 레벨을 제외한 모든 노드에 2개의 자식 노드가 있을 경우 트리의 높이 : log₂N N : 원소의 개수 BST의 검색 및 삽입 동작의 시간 복잡도 : O(l..
-
2020.05.15
이진 탐색 트리 프로그램 (Binary Search Tree Program)
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816..
-
2017.06.01
[C] 트리(Tree)
트리(Tree) - 선형 자료 구조(linear data structure) : 자료들이 직선과 같이 나열되어 있는 구조 (리스트, 스택, 큐 등) - 트리는 계층적인 구조(hierarchical structure) 또는 비선형 자료 구조(nonlinear data structure)를 가지고 있으며, 계층적인 자료를 표현하는 데 이용되는 자료 구조. - 인공 지능 문제에서도 트리가 사용되는데 대표적인 것으로 결정 트리(decision tree)가 있음. - 결정 트리는 인간의 의사 결정 구조를 표현하는 한 가지 방법. [트리에서 쓰이는 용어] - 노드(node) : 트리의 구성 요소 - 트리는 한 개 이상의 노드로 이루어진 유한 집합임. - 이들 중 하나의 노드는 루트(root) 노드라고 불리고, 나머..
