[알고리즘] 이진트리 (B-Tree)

function findNumber(list, value){
    var searchCnt = 0;
    
    var bTree = function(list, value){
        // Step. 탐색 횟수 체크
        console.log("탐색 중");
    
        // Step. 목록 이 0개 또는 지정되지 않은 경우 -1 리턴
        if(list == null || list.length == 0)    return -1;
    
        // Step. 중간값 조회
        var nIdx   = Math.floor(list.length / 2);    // 현재 검색할 Index
        var nValue = list[nIdx];                     // 현재 값
    
        // console.log(nIdx);
        // console.log(nValue);
        // console.log(list);
        
        if(nValue == value)        return nIdx;
        else if(nValue < value)    return bTree(list.slice(nIdx, list.length), value);
        else                           return bTree(list.slice(0, nIdx), value);
    }

    // Step. 목록 정렬
    list.sort(function(a, b){ return a - b });

    console.log("정렬된 값 : " + JSON.stringify(list));
    
    return bTree(list, value);
}

// Step. 변수 지정
var list  = [1, 6, 10, 15, 3, 7, 20];
var value = 10;

if(findNumber(list, value) < 0)    console.log("해당값은 없습니다.");
else                               console.log("해당값이 존재합니다.");

 이번에 코딩을 하다가 갑자기 이진트리에 대해 생각해 보게 되어 지식도 정리할 겸 글을 쓰기 시작했습니다. 평소 개발 때는 굳이 알고리즘이 많이 필요하지 않습니다. 이유는 개발 초기에는 알고리즘이 필요할 정도의 개발이 이루어지지 않기 때문입니다. (이는 대용량 데이터를 처리할 일이 개발 초기에 없다는 것과 같습니다.) 또한, 이후부터는 알고리즘보다 데이터베이스 튜닝이 많다 보니 점점 코딩의 알고리즘보다는 데이터베이스 튜닝에 손이 많이 가기 시작합니다. (이 글을 쓰기 시작한 변명은 여기까지,,,)

---

 대학교에서 알고리즘 수업을 듣는다면 한 번씩 거쳐가는게 B-Tree입니다. 그렇다면 B-Tree는 무엇일까요? B-Tree는 주로 "이진트리", "바이너리 트리" 등등으로 읽히는데, 여기서 의미하는 "이진"과 "바이너리"가 바로 해답입니다.

 

 우선 이진 트리의 기본 조건은 목록이 정렬되어있어야 한다는 점입니다.

때문에, 목록인지와 정렬되어 있는지를 반드시 체크하고 진행하여야 합니다.

이후 탐색 방법은 아래와 같습니다.

 

 1/ 목록의 중간 값이 찾으려는 값과 같으면 완료

 2/ 목록의 중간 값이 찾으려는 값 보다 작으면 중간 이후 값에서 재 검색

 3/ 목록의 중간 값이 찾으려는 값 보다 크면 중간 이전 값에서 재 검색

 

만약 10을 찾기 위해서 해당 값을 검색하였다면 아래의 순서대로 3번의 조건 검색이 이루어졌고 탐색을 완료할 겁니다.

 

 반대로 3을 찾기 위해서 해당 값을 검색하였다면 아래의 순서대로 3번의 조건 검색이 이루어졌고 탐색을 완료할 겁니다.

 이 처럼 크면 1, 작으면 0이라는 두 가지 조건 만으로 나뭇가지처럼 뻣어나가기 때문에 이진트리가 됩니다.

 

 위에서 사전에 정의한 function을 사용하여 위의 내용을 수행해보면 아래와 같은 결과가 반환됩니다.
(※ 현재 함수는 해당 값이 있는지 없는지만 반환하도록 설계되었습니다.)

10을 찾는 경우 탐색 중이 3번 되었음을 확인 가능합니다.

3을 찾는 경우 탐색 중이 2번 되었음을 확인 가능합니다.