이진탐색트리3 [C언어와 친구들] 이진 탐색 트리 (BST) 이진탐색트리(Binary Search Tree, BST)란? - 모든 원소는 유일한 키 값을 갖는다. (중복 내용을 갖는 항목은 없다.) - 왼쪽 서브트리의 모든 원소들은 루트의 키보다 작은 값을 갖는다. - 오른쪽 서브트리의 모든 원소드른 루트의 키보다 큰 값을 갖는다. - 왼쪽 서브트리와 오른쪽 서브트리도 이진탐색트리이다. (재귀적으로 정의) 이진 탐색 트리에서 3가지 연산: 탐색/삽입/삭제 1) 탐색 루트 노드를 주고서 우리가 찾고 싶은 x라는 key 값을 찾는다. search(root, x) x를 root 값부터 비교해가면서 root 보다 크면 오른쪽 서브 트리를, root 보다 작으면 왼쪽 서브트리를 방문한다. 만약 x가 roo값과 같으면 바로 root를 반환한다. search 함수를 만들어보자.. 2022. 10. 24. [WEEK03] 개발일지 (부제: set💖과 소소한 행복 찾기) ※ 개발일지가 아니라 일기일 수도 있는 점 양해바랍니다. 오전, 오후, 새벽이 모두 담겨있어요.※ ※ WEEK 시작인 매주 목요일에 업데이트 됩니다. 많.관.부 ※ DAY01 22.10.06 (목) from Jungle import Knowledge 벌써(?) 3주차이다. 사실 일주일 됐을 때 2주를 체감했고, 2주가 됐을 때 4주를 체감했는데 돌이켜보니 일단 했다. 이번 시험은 B반이 먼저 시험을 봤고, 문제는 쿼드트리, PPAP, 소수곱이 나왔다. 저번 주에 색종이 만들기를 공부하면서 힌트에 '쿼드트리를 만드는 문제'라고 해서 '쿼드트리가 뭐냐!!' 하면서 혼자 공부를 했었는데 문제에 나와서 반가웠다. 하지만, 공부를 하지 않았다면 과연 풀 수 있었던 문제일까 생각해보면 잘 모르겠다.. 아직 재귀에 .. 2022. 10. 13. [알고리즘] 이진 트리, 이진 검색 트리 & 백준(이진 탐색 트리, 트리의 순회) 이진트리(Binary Tree) : 노드가 왼쪽 자식(left chile)과 오른쪽 자식(right child)만 가진다. 자식이 없을 수도 있다. (최대 두 개의 자식 노드를 가지는 트리 형태의 자료구조로서, 단순히 값을 저장하기 위한 용도로 사용되기 보다는 효율적인 탐색 혹은 정렬을 위해 사용된다.) 완전 이진 트리(Complete Binary Tree) - 마지막 레벨을 제외하고, 모든 레벨에 노드가 가득 찬다. - 마지막 레벨은 왼쪽부터 채우고 끝까지 꽉 차지 않아도 된다. - Heap, 우선순위 큐에서 사용하는 트리 구조이다. * 힙(Heap): 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리(complete binary tree)를 기본으로 한 자료구조이다. 이진 .. 2022. 10. 12. 이전 1 다음
