10. 이진 검색 트리 구현 - 패스트캠퍼스 백엔드 부트캠프 3기

1. 이진 검색 트리(BST)

• 검색을 위한 자료구조
• Key(유일한 값)이 트리의 자리가 됨 → 중복을 허용하지 않음
• 왼쪽 서브트리에 있는 모든 키 값은 부모의 키 값보다 작다.
• 오른쪽 서브트리에 있는 모든 키 값은 부모의 키 값보다 크다.
• 키 값을 비교하는 기준은 자료의 종류에 따라 다를 수 있음
• 키를 검색할 때 하나의 노드와 비교 후 크거나 작음에 따라 왼쪽 혹은 오른쪽 서브트리로 이동을 결정할 수 있음
• 트리가 비교적 균형을 이루었다면 n개의 요소에서 어떤 키 값을 찾거나 찾는 데 실패하는 데 걸리는 시간은 평균적으로 O(log n)

public interface SearchInterface<T> {
    public T search(Comparable x);
    public void insert(Comparable x);
    public void delete(Comparable x);
    public boolean isEmpty();
    public void clear();
}

 

public class TreeNode<E> {
    E data;
    Comparable key;
    TreeNode left;
    TreeNode right;

    TreeNode(Comparable key, TreeNode left, TreeNode right) {
        this.key = key;
        this.left = left;
        this.right = right;
    }
}

public class BinarySearchTree implements SearchInterface<TreeNode>{
    private TreeNode root;
    public BinarySearchTree() {
        root = null;
    }

    @Override
    public TreeNode search(Comparable searchKey) {
        return searchItem(root, searchKey);
    }

    private TreeNode searchItem(TreeNode tNode, Comparable searchKey) {
        if(tNode == null)
            return null;
        else if(searchKey.compareTo(tNode.key) == 0)
            return tNode;
        else if(searchKey.compareTo(tNode.key) < 0)
            return searchItem(tNode.left, searchKey);
        else
            return searchItem(tNode.right, searchKey);
    }

    @Override
    public void insert(Comparable newKey) { root = insertItem(root, newKey);}

    private TreeNode insertItem(TreeNode tNode, Comparable newItem) {
        if(tNode == null)
            tNode = new TreeNode(newItem, null, null);
        else if(newItem.compareTo(tNode.key)<0)
            tNode.left = insertItem(tNode.left, newItem);
        else
            tNode.right = insertItem(tNode.right, newItem);
        return tNode;
    }

    @Override
    public void delete(Comparable searchKey) {
        root = deleteItem(root, searchKey);
    }

    private TreeNode deleteItem(TreeNode tNode, Comparable searchKey) {
        if (tNode == null)
            return null;
        else {
            if(searchKey == tNode.key)
                tNode = deleteNode(tNode);
            else if(searchKey.compareTo(tNode.key) <0)
                tNode.left = deleteItem(tNode.left, searchKey);
            else
                tNode.right = deleteItem(tNode.right, searchKey);
            return tNode;
        }
    }

    private TreeNode deleteNode(TreeNode tNode) {
        if((tNode.left == null) && (tNode.right == null))
            return null;
        else if(tNode.left == null)
            return tNode.right;
        else if(tNode.right == null)
            return tNode.left;
        else {
            returnPair rPair = deleteMinItem(tNode.right);
            tNode.key = rPair.key;
            tNode.right = rPair.node;
            return tNode;
        }
    }

    private returnPair deleteMinItem(TreeNode tNode) {
        if (tNode.left == null) {
            return new returnPair(tNode.key, tNode.right);
        } else {
            returnPair rPair = deleteMinItem(tNode.left);
            tNode.left = rPair.node;
            rPair.node = tNode;
            return rPair;
        }
    }

    private class returnPair{
        private Comparable key;
        private TreeNode node;
        private returnPair(Comparable it, TreeNode nd) {
            key = it;
            node = nd;
        }
    }

    @Override
    public boolean isEmpty() {return root == null;}

    @Override
    public void clear() { root = null;}

    public void printPreOrder(){ prPreOrder(root);}
    public void prPreOrder(TreeNode tNode) {
        if (tNode != null) {
            System.out.println(tNode.key);
            prPreOrder(tNode.left);
            prPreOrder(tNode.right);
        }
    }
}

public class BinarySearchTreeTest {
    public static void main(String[] args) {
        System.out.println("Binary Search Tree!");
        BinarySearchTree bst1 = new BinarySearchTree();

// 여러 값을 차례대로 삽입
        bst1.insert(10);
        bst1.insert(20);
        bst1.insert(5);
        bst1.insert(80);
        bst1.insert(90);
        bst1.insert(75);
        bst1.insert(301);
        bst1.insert(77);
        bst1.insert(15);
        bst1.insert(40);

// 현재 트리의 Pre-Order(전위 순회) 결과 출력
        bst1.printPreOrder();

// 첫 번째 삭제 연산: del1 = 20
        Integer del1 = 20;
        bst1.delete(del1);
        System.out.println(del1 + " Deleted!");
// 삭제 후 Pre-Order 결과 확인
        bst1.printPreOrder();

// 두 번째 삭제 연산: del2 = 10
        Integer del2 = 10;
        bst1.delete(del2);
        System.out.println(del2 + " Deleted!");
// 다시 Pre-Order 결과 확인
        bst1.printPreOrder();

// 검색(search) 예시
        Integer tmp = 755;
        TreeNode res = bst1.search(tmp);

// 검색 결과에 따라 출력문을 달리 함
        if (res == null) {
            System.out.println("Search for " + tmp + " failed");
        } else {
            System.out.println("Search for " + tmp + " returned the node of " + res.key);
        }

// 다시 다른 값으로 검색 예시
        tmp = 5;
        res = bst1.search(tmp);
        if (res == null) {
            System.out.println("Search for " + tmp + " failed");
        } else {
            System.out.println("Search for " + tmp + " returned the node of " + res.key);
        }
    }
}