재민의 IT 공부기록

이진 탐색 트리는 탐색을 효율적으로 하기 위한 자료구조로서, 이진트리이자 모든 원소는 서로 다른 key를 가지는 특성을 가지고 있다. 이진탐색에서의 탐색은 searchBST() 연산을 이용하여 진행된다. 우선 루트에서 시작하여, 탐색할 key값 x를 루트 노드의 key값과 비교한다. key값보다 루트 노드의 key값이 클 경우 왼쪽 서브트리에서, key값이 루트노드의 key값보다 클 경우 오른쪽 서브트리에서 탐색을 진행한다는 기본 메커니즘을 기반으로 탐색을 진행한다. 이진탐색에서 탐색의 구현은 반복/재귀가 있다. 반복적 방법은 while p != NULL을 이용하여 p값을 찾을 때까지 삽입 연산을 계속 수행하는 방법이고, 재귀적 방법은 찾고자하는 key값이 해당 key값보다 클 경우 범위를 제한하여 다시..

BST(Binary Search Tree)란 탐색을 효율적으로 하기 위한 자료구조이다. 이진탐색트리는 다음과 같은 특징을 가진다. 1) 이진트리이며 모든 원소는 서로 다른 유일한 키를 가짐 2) 왼쪽 서브트리의 key값< 루트의 key값< 오른쪽 서브트리의 key값 3) 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리 -이진탐색 트리의 연산 1) 탐색(searchBST()) 연산 루트에서 시작, 탐색할 키값 X를 루트노드의 키값과 비교한다. 키값이 루트노드의 키값과 같으면 탐색 성공, 크거나 작으면 각각 오른쪽, 왼쪽으로 위치시켜 다시 탐색연산 수행 -탐색 방법: 반복적 방법, 순환적 방법(재귀적으로 수행) 2) 삽입(insertBST())연산 탐색연산이 모두 완료된 이후에 진행된다. 탐색이 실패한 위..