이진 탐색 트리 (Binary Search Tree, BST) 이진 탐색 트리는 효율적인 탐색을 위해 만들어진 트리로, 다음과 같은 속성이 존재한다. 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다. (중복 X) 2. 부모의 키가 왼쪽 자식 노드의 키보다 크다. 3. 부모의 키가 오른쪽 자식 노드의 키보다 작다. 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다. 특징 기존 이진트리보다 탐색이 빠르다는 장점을 가지고 있다. 이진 탐색 트리의 탐색 연산은 트리의 높이가 h라면 O(h)의 시간 복잡도를 갖게 된다. 탐색 (Search) 이진 탐색 트리의 탐색 과정은 다음과 같다. 1. 루트 노드와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료한다. 2. 찾고자 하는 값이 루트 노드보다 작..
💡 비선형 자료 구조 (Non Linear Data Structure) 비선형 자료 구조란 하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 것을 의미한다. 자료들 간의 앞뒤 관계가 1:n, 또는 n:n의 관계를 말한다. 트리와 그래프가 대표적인 비선형 자료 구조이고, 계층적 구조(Hierarchical Relationship)를 나타내기에 적절하다. 🔎 트리(Tree)의 개념 트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사하다. 트리는 또한 트리 내에 다른 하위 트리가 존재하고, 그 하위 트리 안에는 또다른 하위 트리가 있는 재귀적 자료구조이기도 하다. 대표적인 트리 구조 예시는 ..
🔎 스택 (Stack) 📕 개념 선형 자료구조의 일종으로, 스택은 영어의 의미인 쌓아 올린다는 것을 의미합니다. 따라서 책처럼 위로 하나씩 차곡차곡 쌓아 올린 자료구조를 말합니다. 📒 특징 위의 그림처럼 같은 구조와 크기인 자료들을 정해진 방향으로만 쌓을 수 있고, top으로 정해진 곳을 통해서만 접근이 가능합니다. top은 가장 위에 있는 자료로, 가장 최근에 추가된 자료를 가리키고 있습니다. 또한 삭제할 때도, top을 통해서만 가능합니다. 스택에서 삽입하는 연산을 'push', 삭제하는 연산을 'pop'이라고 합니다. 따라서 스택은 나중에 들어간 원소가 먼저 나오고 (Last In First Out - LIFO), 먼저 들어간 원소는 가장 나오게 됩니다 (First In Last Out - FILO..
0. 선형 자료구조 (Linear Data Structure) 선형 자료구조란 하나의 자료 뒤에 하나의 자료가 존재하는 것을 의미합니다. 자료들 간의 앞뒤 관계가 1:1 선형 관계를 이루며, 배열과 리스트가 대표적인 예이고, 더 나아가 스택, 큐, 데크도 선형 자료구조에 해당됩니다. 해당 선형 자료구조는 연속된 자료구조와 연결된 자료구조 2가지로 나눌 수 있습니다. (Contiguous & Linked) ▪ 연속된 자료구조 (Contiguous) 연속된 자료 구조는 모든 원소를 단일 메모리 덩어리에 넣어 저장하는 것을 말합니다. 대표적인 연속된 자료 구조에는 배열(Array)이 있습니다. ▪ 연결된 자료구조 (Linked) 연결된 자료 구조는 노드(node)라고 하는 여러 개의 메모리 덩어리에 데이터를 ..
