[자료구조] 이진탐색트리 구현 - 최솟값, 최댓값 찾기 / 특정 값 찾기

최솟값/최댓값 찾기 (min(), max())

이진탐색트리에서 최솟값은 맨 왼쪽 노드값이고, 최댓값은 맨 오른쪽 노드값이다.

그러므로 최솟값을 구하는 메소드 min(), 최댓값을 구하는 메소드 max()는 다음과 같이 구현할 수 있다.

 

//최솟값 찾기

    min(){

        return this.minNode(this.root);

    }

    minNode(node){

        if(node){

            while(node && node.left !== null){

                node = node.left;

            }

            return node.key;

        }

        return null;

    }

//최댓값 찾기

    max(){

        return this.maxNode(this.root);

    }

    maxNode(node){

        if(node){

            while(node && node.right !== null){

                node = node.right;

            }

            return node.key;

        }

        return null;

    }

 

사용하는 코드

console.log(`최솟값: ${tree.min()}`); 

console.log(`최댓값: ${tree.max()}`); 

 

특정 값 찾기(search(key))

 //특정값 찾기

    search(key){

        return this.searchNode(this.root, key);

    }

    searchNode(node, key){

        if(node === null){

            return false;

        }else if(key < node.key){

            return this.searchNode(node.left, key);

        }else if(key > node.key){

            return this.searchNode(node.right, key);

        }else{

            return true;

        }

    }

사용하는 코드

console.log(tree.search(1) ? '키 1을 찾았습니다.' : '키 1을 찾지 못했습니다.');

console.log(tree.search(8) ? '키 8을 찾았습니다.' : '키 8을 찾지 못했습니다.');