[알고리즘] 이진탐색트리(BST) 란 ?

이진탐색트리(BST)란?

• 최대 2개의 자식노드를 가지는 트리
• 그 하위도 이진탐색트리의 구조를 가진다.
• 각 노드에는 값이있으며 값사이에는 전순서가 있다.
• 중복값을 허용하지 않는다.

이진탐색트의 연산

• 삽입
• 삭제
• 검색

이진탐색의 예시

 

이진탐색트리(BST)의 구현

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int size=sc.nextInt();
        BSTMethod bstMethod = new BSTMethod();
        BST root=null;

        for(int i= 0;i<size;i ++){
            int data = sc.nextInt();
            root = bstMethod.insertPreNode(root,data);
        }

        bstMethod.deleteNode(root,4);
        BST findNode = bstMethod.findNode(root,5);

    }
}

/**
 * 바이너리 탐색에 필요한 바이너리 트리
 */
class BST{
    public BST preNode = null;
    public BST nextNode = null;
    public int data;

    public BST(int data){
        this.data = data;
    }
}

/**
 * BST 연산에 필요한기능을 정의해 놓은 CLASS
 */
class BSTMethod{
    /**
     * 알맞은 위치에 값 입력
     * @param node parent NODE
     * @param data insert value
     * @return insertNode
     */
    public BST insertPreNode(BST node, int data) {
        if (node == null) {
            node = new BST(data);
            return node;
        } else {
            BST child;
            if (node.data > data) {
                child = insertPreNode(node.preNode, data);
                node.preNode = child;
            }else {
                child = insertPreNode(node.nextNode, data);
                node.nextNode = child;
            }
            return node;
        }
    }

    /**
     * 값을 찾기 위한 메소드
     * @param root ROOT NODE
     * @param data 찾을 값
     * @return 찾은노드
     */
    public BST findNode(BST root, int data){
        BST findNode = root;
        while(findNode.data != data) {
            if(findNode.data < data){
                findNode = findNode.nextNode;
            }else{
                findNode = findNode.preNode;
            }
            if(findNode ==null){
                return null;
            }
        }

        return findNode;
    }

    /**
     * NODE 삭제를 위한 메소드
     * @param node ROOT NODE
     * @param data 삭제시킬 값
     */
    public void deleteNode(BST node,int data){
        BST parentNode = node;
        BST currentNode = node;
        boolean check = false;

        while(currentNode.data != data){
            parentNode = currentNode;
            if(currentNode.data > data){
                check = true;
                currentNode = currentNode.preNode;
            }else{
                check =false;
                currentNode = currentNode.nextNode;
            }

            if(node ==null){
                return;
            }
        }
        /**
         * 자식노드가 없을경우
         */
        if(currentNode.preNode == null && currentNode.nextNode == null){
            if(currentNode == node){
                currentNode = null;
            }
            if(check == true){
                parentNode.preNode = null;
            }else{
                parentNode.nextNode = null;
            }
        }
        /**
         * 자식노드가 하나일경우
         * 1. 왼쪽이 없을 때
         * 2. 오른쪽이 없을 때
         */
        else if(currentNode.nextNode ==null){
            if(currentNode == node){
                node = currentNode.preNode;
            }else{
                parentNode = currentNode.preNode;
            }
        }else if(currentNode.preNode == null){
            if(currentNode == node){
                node = currentNode.nextNode;
            }else{
                parentNode = currentNode.nextNode;
            }
        }
        /**
         * 자식이 2개일경우
         */
        else{
            BST findNode = findDelNode(currentNode);
            if(currentNode == node){
                node = findNode;
            }else if(check){
                parentNode.preNode = findNode;
            }else{
                parentNode.nextNode = findNode;
            }

            findNode.preNode = currentNode.preNode;
        }
    }

    /**
     *
     * @param deleteNode 삭제시킬 노드
     * @return
     */
    public BST findDelNode(BST deleteNode){
        BST result =null;
        BST resultParent = null;
        BST current = deleteNode.nextNode;

        while(current != null){
            resultParent = result;
            result = current;
            current = current.nextNode;
        }

        if(result != deleteNode.nextNode){
            resultParent.preNode = result.nextNode;
            result.nextNode = deleteNode.nextNode;
        }

        return result;
    }
}