BST(Binary Search Tree)

YJS·2023년 9월 11일

CS 전공지식 늘리기 프로젝트

목록 보기

7/16

🤓오늘의 공부 주제: BST🤓

Q. BST는 어떤 자료구조인가?

A. 이진탐색트리(Binary Search Tree; BST)는 정렬된 tree입니다. 어느 node를 선택하든 해당 node의 left subtree에는 그 node의 값보다 작은 값들을 지닌 node들로만 이루어져 있고, node의 right subtree에는 그 node의 값보다 큰 값들을 지닌 node들로만 이루어져 있는 binary tree입니다.

검색과 저장, 삭제의 시간복잡도는 모두 $O(logn)$ 이고, worst case는 한쪽으로 치우친 tree가 됐을 때 $O(n)$ 이다.

Q. 이진트리(Binary tree)는 어떤 자료구조인가?

A.모든 node의 child nodes의 갯수가 2 이하인 트리를 이진 트리라고 한다.

Q. BST의 worst case 시간복잡도는 $O(n)$ 인데 어떠한 경우에 worst case가 발생하는가?

A.균형이 많이 깨져서 한 쪽으로 치우친 BST의 경우에 worst case가 됩니다. 이렇게 되면 Linked list와 다를게 없어집니다. 따라서 탐색시에 $O(logn)$ 이 아니라 $O(n)$ 이 된다. 이를 해결하기 위해서는 자가 균형 이진 탐색 트리(Self-Balancing BST)는 알고리즘으로 이진 트리의 균형이 잘 맞도록 유지하여 높이를 가능한 낮게 유지하면 된다. 대표적으로 AVL트리와 Red-black tree가 있다. JAVA에서는 hashmap의 seperate chaning으로써 Linked list와 Red-black tree를 병행하여 저장한다.

public class BinarySearchTree {
    Node root = null;

    public void add(int key) {
        Node newNode = new Node();
        newNode.key = key;

        if (root == null) {
            root = newNode;
        } else {
            root = addNode(root, newNode);
        }
    }

    private Node addNode(Node node, Node newNode) {
        if (node == null)
            return newNode;
        else if (node.key > newNode.key)
            node.left = addNode(node.left, newNode);
        else
            node.right = addNode(node.right, newNode);

        return node;
    }

    public void remove(int key) {
        root = removeNode(root, key);
    }

    private Node removeNode(Node node, int key) {
        if (node == null)
            throw new RuntimeException("해당 값을 가진 노드를 찾을 수 없습니다.");

        if (node.key > key)
            node.left = removeNode(node.left, key);
        else if (node.key < key) {
            node.right = removeNode(node.right, key);
        } else {
            //삭제할 노드를 찾은 경우
            if (node.left != null) {
                //왼쪽 서브트리에서 가장 오른쪽에 있는 값 찾아 대체하기
                Node child = findMaxNode(node.left);
                int removedKey = node.key;
                node.key = child.key;
                child.key = removedKey;
                //다시 옮겨진 위치에서 서브트리에 대해 재귀적으로 실행
                node.left = removeNode(node.left, key);
            } else if (node.right != null) {
                //오른족 서브트리에서 가장 왼쪽에 있는 값 찾아 대체하기
                Node child = findMinNode(node.right);
                int removedKey = node.key;
                node.key = child.key;
                child.key = removedKey;
                //다시 옮겨진 위치에서 서브트리에 대해 재귀적으로 실행
                node.right = removeNode(node.right, key);
            } else {
                //삭제할 노드가 단말 노드인 경우 부모 노드와의 연결 종료
                return null;
            }
        }

        return node;
    }

    private Node findMaxNode(Node node) {
        if (node.right == null)
            return node;
        else
            return findMaxNode(node.right);
    }

    private Node findMinNode(Node node) {
        if (node.left == null)
            return node;
        else
            return findMinNode(node.left);
    }

    public void search(int key) {
        searchNode(root, key);
    }

    private Node searchNode(Node node, int key) {
        if (node == null)
            throw new RuntimeException("해당 값을 가진 노드를 찾을 수 없습니다.");

        if (node.key > key)
            node.right = searchNode(node.right, key);
        else if (node.key < key)
            node.left = searchNode(node.left, key);
        else
            System.out.println("해당 값을 가진 노드를 찾았습니다.");

        return node;
    }

    public void descendingTraversal() {
        //내림차순 순회
        System.out.print("내림차순 순회: ");
        rightInorderTraversal(root);
        System.out.println();
    }

    private void rightInorderTraversal(Node node){
        //우측 중위 순회
        if(node == null)
            return;
        rightInorderTraversal(node.right);
        System.out.printf("%d ", node.key);
        rightInorderTraversal(node.left);
    }


    public void ascendingTraversal() {
        //오름차순 순회
        System.out.print("오름차순 순회: ");
        leftInorderTraversal(root);
        System.out.println();
    }

    private void leftInorderTraversal(Node node) {
        //좌측 중위 순회
        if(node == null)
            return;
        leftInorderTraversal(node.left);
        System.out.printf("%d ", node.key);
        leftInorderTraversal(node.right);
    }

}