[Algorithm] Binary Search Tree - Insert

Binary Search Tree 

컴공때 배웠던걸 복습할겸 다시 공부할겸 정리할겸 겸사겸사

 

특징

• 자식을 최대 2개만 가질수 있는 트리이다.
• root 의 왼쪽값은 root 의 값보다 작다.
• root 의 오른쪽 값은 root의 값보다 크다.
• Insert, Search, Delete, Successor, Predecessor 을 구현한다.

 

Binary Search Tree 의 구조

• 다음은 Binary search tree 의 구조이다
• 100 이 처음에 들어와 루트가 되었고
• 50  을 넣을때 100 과 비교한다. 부모보다 작기 때문에 왼쪽에 추가해준다.
• 200 이 들어왔을때 부모의 값보다 크기 때문에 오른쪽 에 추가해준다.
• 이걸 반복하면 다음과 같은 그림이 된다.

 

 

 

Insert 구현

위의 예시대로 구현 하면된다.

하나씩 그림으로 살펴 보자

아래 처럼 반복하다 보면 위의 그림이 만들어진다.

 

 

 

 

 

Insert 코드 구현

	// root 는 멤버 변수
    public void insertNode(int data) {
        // 루트 노드가 비어 있다면 
        // 노드를 생성하고 값을 넣어준다.
        if(rootNode == null) {
            rootNode = new Node(data);
            return;
        }

		// 탐색을 위한 head
        Node head = rootNode;
        
        // 탐색한 값의 부모
        Node parentNode = rootNode;
        boolean isLeftLocation = false;
        
        // head 가 null 이면 값을 넣는 단계 이기 때문에 
        // 탐색을 멈춘다.
        while (head != null) {
            parentNode = head;
            
            // data 값이 비교하는 노드보다 크면 오른쪽
            // 작은면 왼쪽
            if (head.getData() < data) {
                head = head.right;
                isLeftLocation = false;
            } else {
                head = head.left;
                isLeftLocation = true;
            }
        }

        // 최종적으로 노드를 생성하고 값을 넣어준다.
        if (isLeftLocation) {
            parentNode.left = new Node(data);
        } else {
            parentNode.right = new Node(data);
        }
    }

 

 

 

전체코드

구현코드:

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