본문 바로가기

이진탐색트리2

[알고리즘] ep3+) 이진탐색트리(BST) 구현 BST(이진탐색트리) 구현종료(q) 명령 때까지 삽입(i), 탐색(s), 삭제(d), 인쇄(p), 명령을 반복 입력받아 수행i : 입력 에 대한 노드 생성 및 트리에 삽입d : 입력 가 트리에 존재하면 해당 노드 삭제 후 삭제된 키를 출력, 없으면 ‘X’를 출력s : 입력 가 트리에 존재하면 해당 키를 출력, 없으면 ‘X’를 출력 p: 현재 트리를 전위순회로 인쇄q: 프로그램 종료  주의: 중복 키가 없는 것으로 전제한다. 문제를 단순화하기 위해, 키만 존재하고 원소(element)는 없는 것으로 구현한다. main 함수는 반복적으로 명령을 입력받기 전에 빈(empty) 이진탐색트리를 초기화해야 한다 – 즉, 외부노드 1개로만 구성된 이진트리를 말한다. 힌트: 트리 노드 삭제 시, 삭제할 노드 w의 자식.. 2024. 7. 17.
[알고리즘] ep3) 탐색트리 ㅇ이진탐색트리(BST, Binary Search Tree): 노드의 왼쪽 가지에는 노드보다 작은 값들만 있고, 노드의 오른쪽 가지에는 노드보다 큰 값들만 있도록 구성 내부노드에 (key, value)쌍을 저장하며 그림으로는 간단히 노드에 key만 표시한다(왼쪽 및 오른쪽 부트리 또한 각각 이진탐색트리이다) // 재귀버전int binarySearch(int* arr, int lowIdx, int highIdx, int key) { if (lowIdx > highIdx) { if (highIdx key) { // 중간값이 키값보다 큰 경우, 왼쪽 절반을 탐색 return binarySearch(arr, lowIdx, midIdx - 1, key); } else if (a.. 2024. 7. 11.

티스토리툴바