ITPE * JackerLab

개요이진 탐색 트리(BST, Binary Search Tree)는 이진 트리의 일종으로, 왼쪽 서브트리에는 루트보다 작은 값이, 오른쪽 서브트리에는 루트보다 큰 값이 저장되는 자료구조이다. 중복 없는 정렬된 데이터를 저장하면서 빠르게 탐색, 삽입, 삭제가 가능하며, 평균적으로 O(log n)의 성능을 보인다. 알고리즘 문제풀이와 데이터베이스, 메모리 관리 등 다양한 분야에 활용된다.1. BST의 구조와 특징 구성 요소 설명 루트(Root)트리의 최상위 노드노드(Node)데이터와 자식 포인터를 포함한 단위왼쪽 자식루트보다 작은 값오른쪽 자식루트보다 큰 값BST는 모든 노드에 대해 왼쪽 이 성립한다.2. BST의 연산 동작 원리연산동작 방식시간 복잡도 (평균/최악)탐색(Search)루트부터 값 비교, 작으..

개요이진 트리(Binary Tree)는 트리(Tree) 자료구조의 한 종류로, 각 노드가 최대 두 개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 가지는 계층적 구조이다. 트리의 기본이자 다양한 트리 기반 알고리즘의 뼈대 역할을 하며, 이진 탐색 트리(BST), 힙(Heap), 트라이(Trie), 표현식 트리 등으로 확장된다. 노드의 위치와 순서가 중요한 구조로, 다양한 순회 알고리즘이 적용된다.1. 이진 트리의 구조와 용어 용어 설명 노드(Node)데이터를 저장하는 기본 단위루트(Root)트리의 시작 노드 (부모 없음)왼쪽 자식(Left Child)루트 기준 왼쪽 하위 노드오른쪽 자식(Right Child)루트 기준 오른쪽 하위 노드리프(Leaf)자식이 없는 노드서브트리(Subtree)특정 노드를 루트로..

개요트리(Tree)는 노드(Node)와 간선(Edge)로 구성된 계층적 비선형 자료구조로, 하나의 루트 노드(Root)에서 시작하여 자식 노드로 분기되는 구조를 가진다. 트리는 컴퓨터 과학에서 데이터 분류, 탐색, 계층 구조 표현 등 매우 널리 사용되며, 이진 트리, 이진 탐색 트리, 힙, 트라이, AVL 트리, B트리 등 다양한 종류가 있다.1. 트리의 개념과 구성 요소 구성 요소 설명 노드(Node)데이터를 담는 기본 단위루트(Root)트리의 시작 노드 (부모가 없음)부모(Parent), 자식(Child)노드 간 관계 정의리프(Leaf)자식이 없는 마지막 노드서브트리(Subtree)특정 노드를 루트로 하는 부분 트리간선(Edge)노드 간 연결 관계2. 트리의 특성특성설명비선형 구조노드 간 관계가 계..

개요트리 탐색(Tree Traversal)은 트리 구조를 가진 자료구조의 노드를 특정 순서에 따라 방문하는 알고리즘이다. 이진 트리(Binary Tree), 이진 탐색 트리(BST), 힙(Heap) 등 다양한 트리 구조에서 데이터를 순차적으로 접근하거나 연산을 수행할 때 사용된다. DFS 기반의 전위/중위/후위 순회와 BFS 기반의 레벨 순회로 나뉘며, 문제에 따라 적절한 탐색 방법을 선택해야 한다.1. 개념 및 정의트리 탐색은 다음과 같은 두 가지 유형으로 나뉜다:DFS(Depth-First Search): 깊이 우선 순회 (전위, 중위, 후위 순회)BFS(Breadth-First Search): 너비 우선 순회 (레벨 순회)2. DFS 기반 트리 순회 순회 방식 방문 순서 주요 특징 전위 순회 (..