컴퓨터공학3 [자료구조] BST(Binary Search Tree) 이진 탐색 트리 - CS면접 대비 이번 글에서는 탐색, 삽입, 삭제 연산에서 탁월한 성능을 보이는 BST(Binary Search Tree)에 관한 내용을 정리해보고자 한다. 1부터 100까지의 수 중 임의의 수 하나를 맞히는 게임을 한다고 가정해보자. 직관적으로 생각했을 때 가운데 값인 50을 가장 먼저 말하고 맞히려는 수가 그보다 큰 경우 75를 작은 경우 25를 외치는 식으로 답을 찾는 게 가장 효율적인 방법일 것이다. 이진 탐색 트리는 이와 유사한 방식으로 자료 탐색이 가능한 이진 트리 자료구조라고 할 수 있다. 이진 탐색 트리(BST, Binary Search Tree) [1] 이진 탐색 트리(BST)의 정의 이진 탐색 트리(BST)는 이진 트리로서 공백일 수 있으며, 만약 공백이 아니라면 다음 성질을 만족한다. 모든 원소는 키.. 2021. 12. 2. [자료구조] Binary Heap(히프)와 Priority Queue(우선순위 큐) - CS면접 대비 이번 글에서는 우선순위 큐(Priority Queue) 구현을 위해 사용되는 이진 히프(Binary Heap)에 관한 내용을 정리해보고자 한다. 일반적인 배열로 우선순위 큐를 구현하는 경우 삽입에 O(N) 정렬에 O(log N) 시간이 소요되는 반면, 히프로 구현하는 경우 enqueue와 dequeue 연산을 O(log N) 시간에 가능하게 해준다. 이진 히프(Binary Heap) [1] 최대/최소 히프의 정의 최대 히프(max heap)는 최대 트리(max tree)*이면서 완전 이진 트리(complete binary tree)이다. 최소 히프(min heap)는 최소 트리(min tree)*이면서 완전 이진 트리(complete binary tree)이다. * 최대(최소) 트리 : 각 노드의 키 값.. 2021. 11. 30. [자료구조] Binary Tree(이진 트리) - CS면접 대비 이번 글에서는 컴퓨터 프로그래밍에서 자주 사용되는 자료구조 중 하나인 이진 트리에 관한 내용을 정리해보고자 한다. 1. 이진 트리의 정의 및 성질 먼저, 이진 트리(binary tree)는 공백이거나 루트(root)와 왼쪽 서브 트리, 오른쪽 서브 트리라고 하는 2개의 분리된 이진 트리로 구성된 노드의 유한 집합이다. 이진 트리와 일반적인 트리의 주요한 차이점은 다음과 같다. 일반 트리의 경우 0개의 노드를 가질 수 없으나, 공백 이진 트리는 존재함 일반 트리는 자식의 순서를 구분하지 않으나, 이진 트리는 왼쪽 자식과 오른쪽 자식을 구별함 또한, 이진 트리는 노드의 수와 관련하여 다음과 같은 성질을 갖는다. 레벨 i 에서의 최대 노드 수는 2^(i -1) → 예) 레벨 3에서 최대 노드의 수는 4개 깊이.. 2021. 11. 16. 이전 1 다음 반응형
