[Algorithm] Binary Search Tree - Search

Binary Search Tree 의 Search 구현

앞에서 Binary Search Tree의 정의와 insert를 구현을 해봤다.

이번에는 Search를 알아보고 구현해보자.

 

 

 

Search 구현

search 구현은 참 간단하다 그래도 설명을 하면 

더 쉽게 이해 되니 그림으로 먼저 알아보자.

 

일단 글로 설명하자면

• root 부터 비교를 한다
• root 값보다 작으면 왼쪽으로 이동
• root 값보다 크면 오른쪽으로 이동
• 이동하면서 탐색을 반복한다.

 

 

 

 

Search 코드 구현

    // rootNode 는 멤버면수이다.
    public Node searchNode(int data) {
        // rootNode 가 null 이면 리턴
        if (rootNode == null) {
            System.out.println("Can not find node");
            return null;
        }

        Node head = rootNode;
        Node parent = null;
        
       // 탐색시작
       // 값이 같을때 까지 탐색
       while(head.getData() != data) {
       
       	    // 현재 노드 보다 값이 크면 오른쪽으로 이동하여 탐색
            // 값이 작으면 왼쪽으로 이동하여 탐색
            if (head.getData() < data) {
                head = head.right;
            } else {
                head = head.left;
            }

            // 만약 head 가 null 이면 찾는 값이 없기 때문에 
            // 탐색을 종료한다.
            if (head == null) {
                System.out.println("Can not find node");
                break;
            }
        }

        return head;
    }

 

 

 

 

선행학습

https://vprog1215.tistory.com/72

Binary Search Tree - Insert

 

 

 

 

전체코드

구현코드:

https://github.com/rnrl1215/algorithm-base/tree/master/src/main/java/algorithm/binarysearchtree

 

테스트코드:

https://github.com/rnrl1215/algorithm-base/blob/master/src/test/java/BinarySearchNodeTest.java