이진 트리 검색 Binary Tree Search

바이너리 검색

미리 정렬된 데이터를 대상으로 검색 범위를 반으로 감소시켜 가면서 검색 키를 찾는 검색 방법

 

-찾으려는 데이터보다 키가 작으면 왼쪽으로, 반대는 오른쪽으로 이동

-이동 후 다시 반씩 비교하는 바이너리 서치 실행

 

binarysearchrecursive(values, start, end, key)
{
	int ret=-1; //FAIL
   	int middle=0;
    
    if(start<=end){
    	middle=(start+end)/2;
        if(key==values[middle]){
        	ret=middle;
        }
        else if(key<values[middle]){
        	ret= binarysearchrecursive(values, start, midde-1 ,key);
        }
        else{
        	ret= binarysearchrecursive(values, middle+1 , end, key);
        }
   }
   return ret;
  }

 

 

 

내가 최근에 풀었던 문제가 바이너리 트리라 링크 추가함!

 

C++] 프로그래머스 - 입국심사 / 바이너리 트리 (tistory.com)

[C++] 프로그래머스 - 입국심사 / 바이너리 트리

 

바이너리 검색 트리의 제약사항

1) 왼쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 작다.

2) 오른쪽 서브트리에 있는 모든 노드의 키는 루트의 키보다 크다.

3) 왼쪽 서브트리와 오른쪽 서브트리도 모두 바이너리 검색 트리이다.

4) 중복된 키는 바이너리 검색 트리가 될 수 없다.

 

 

 

 

 

바이너리 검색 종류

 

-순차 검색(sequential search)

일렬로 저장된 데이터들을 차례대로 비교하는 검색 방법

 

-색인 순차 검색(index sequential search)

데이터가 미리 정렬된 경우에 색인 테이블(index table)을 이용하여 검색의 효율을 높이는 검색 방법