CS/자료구조
-
BST - Binary Search TreeCS/자료구조 2023. 12. 29. 01:09
요즘 프로그래밍을 공부하는 사람들을 만나면, 다들 '자료구조 = 코딩테스트 준비' 라는 생각을 하고 있는 것 같습니다. 저는 수학에 사칙연산이 기본이라면, 코드를 작성할 때는 자료구조가 그 역할을 한다고 생각하는데요. 이번에는 다양한 트리 중에 이진 검색 트리를 살펴보겠습니다. 1. BST 란? Binary Search Tree라는 이름에서 알 수 있듯이, BST는 일종의 Binary Tree 입니다. (부모가 2개 이하의 자식을 갖는 트리) 그리고 Binary Tree 중에 특정 조건을 만족하는 경우에 검색에 이점이 생기기 때문에, 이들을 따로 BST로 분류를 합니다. 2. 성립조건 성립 조건은 생각보다 간단합니다. '부모를 기준으로 부모 보다 작은 값은 왼편에, 부모 보다 큰 값은 오른편에 위치한다...
-
Tree 란?CS/자료구조 2023. 10. 28. 20:13
요즘 프로그래밍을 공부하는 사람들을 만나면, 다들 '자료구조 = 코딩테스트 준비' 라는 생각을 하고 있는 것 같습니다. 저는 수학에 사칙연산이 기본이라면, 코드를 작성할 때는 자료구조가 그 역할을 한다고 생각하는데요. 일하면서 트리에 익숙하지 않아서 고생했던 적들이 있어서, 트리에 관한 글을 써보려고 합니다. 1. Tree 란? 트리는 노드(Node)와 간선(Edge)로 이루어져있고, 순환이 존재하지 않는 계층적 자료 구조입니다. 간단하게 생각해보면, 트리는 이름에서 알 수 있듯이 나무를 뒤집어 놓은 모양입니다. 하나씩 살펴보면, 노드(Node)를 가지가 뻗어져 나오는 마디라고 생각하고 간선(Edge)을 마디라고 생각하면 좋을 것 같네요. 그리고 순환이 존재하지 않는다는 것은 노드가 자기 자신을 다시 방..