[자료구조] Binary Search Tree(이진 탐색 트리)

📋 목차

• Binary Search Tree(이진 탐색 트리)란?
• Binary Search Tree(이진 탐색 트리)의 4가지 조건
• Binary Search Tree(이진 탐색 트리) 연산
  • 탐색 연산
  • 삽입 연산
  • 삭제 연산
• Binary Search Tree(이진 탐색 트리) 성능

---

1️⃣ Binary Search Tree(이진 탐색 트리)란?

• 이진탐색트리(BST: Binary Search Tree)는 이진트리 기반의 탐색을 위한 자료구조이다.
• 이진탐색의 효율적인 탐색 능력을 가지며, 삽입과 삭제가 가능한 것이 특징이다.

• 위의 이진 탐색 트리에서, 15의 값을 가진 노드의 왼쪽 서브트리에 있는 값들(5,7,10)은 루트 노드인 15보다 모두 작고, 오른쪽 서브트리에 있는 값들(16, 18, 19, 20)은 모두 15보다 큰 값들이다.
• 이진 탐색 트리를 중위 순회 방법으로 순회하면, 5 -> 7 -> 10 -> 15 -> 16 -> 18 -> 19 -> 20 -> 22 -> 36 -> 45 ->60 으로 숫자들의 크기 순이다.

✔️ 이진탐색트리의 목적은?

이진탐색 + 연결리스트

• 이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), but 삽입,삭제가 불가능
• 연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간복잡도가 O(N)
• 이 두가지를 합하여 장점을 모두 얻는 것이 '이진탐색트리'
• 즉, 효율적인 탐색 능력을 가지고, 자료의 삽입 삭제도 가능하게 만든다.

 

2️⃣ Binary Search Tree(이진 탐색 트리)의 4가지 조건

이진 탐색 트리 (BST, Binary Search Tree)

• 모든 노드는 유일한 키를 갖는다. (중복된 값을 가져서는 안된다.)
  • 중복이 없어야 하는 이유는?
  • 검색 목적 자료구조인데, 굳이 중복이 많은 경우에 트리를 사용하여 검색 속도를 느리게 할 필요가 없음. (트리에 삽입하는 것보다, 노드에 count 값을 가지게 하여 처리하는 것이 훨씬 효율적)
• 왼쪽 서브트리에 존재하는 노드들의 값은 그 트리의 루트 값보다 반드시 작다.
• 오른쪽 서브트리에 존재하는 노드들의 값은 그 트리의 루트 값보다 반드시 크다.
• 왼쪽과 오른쪽 서브트리도 이진탐색트리이다.

 

3️⃣ Binary Search Tree(이진 탐색 트리)의 연산

✔️ 노드 클래스 만들기

BST의 개별 노드를 나타내는 것이 바로 Node클래스이다. 이는 다음과 같이 3개의 필드로 구성된다.

• data : 노드가 갖는 실질적 데이터
• left : 노드의 왼쪽 자식
• right : 노드의 오른쪽 자식

Node<K, V>

• 아래 코드는 노드의 생성자와 getter/setter 메서드를 추가한 클래스이다.

public class BinarySearchTree {

    public class Node {

        public Node root;

        private int data;
        private Node left;
        private Node right;

        /* 생성자 */
        public Node(int data){
            this.setData(data);
            setLeft(null);
            setRight(null);
        }

        /* 각종 getter / setter */
        public int getData() {
            return data;
        }
        public void setData(int data) {
            this.data = data;
        }
        public Node getLeft() {
            return left;
        }
        public void setLeft(Node left) {
            this.left = left;
        }
        public Node getRight() {
            return right;
        }
        public void setRight(Node right) {
            this.right = right;
        }
        /*탐색 연산*/
        public boolean find(int key){
            Node currentNode = root;
        }
    }

    public Node root; // bst의 루트 노드

    public BinarySearchTree(){ // bst 생성자
        root = null;
    }

}

🔹 탐색 연산

탐색연산에서 중요한 점은, 바로 BST의 특성(왼쪽 자식 노드의 값은 현재 노드보다 항상 작아야한다)과 (오른쪽 자식 노드의 값은 현재 노드의 값 보다 항상 커야 한다.)라는 특징을 만족한다고 가정하고 연산을 한다는 것이다.

/*탐색 연산*/
    public boolean find(int key){
        Node currentNode = root;
        while(currentNode != null){
            // 현재 노드와 찾는 값이 같으면
            if(currentNode.getData() == key){
                return true;
            }else if(currentNode.getData() > key){ // 찾는 값이 현재 노드보다 작으면
                currentNode = currentNode.left;
            }else {// 찾는 값이 현재 노드보다 크면
                currentNode = currentNode.right;
            }
        }
        return false;
    }

🔹 삽입 연산

삽입 연산에서 가장 먼저 하는 일은 root노드가 존재하는지 확인하는 것이다.

root노드가 존재하지 않는다는 소리는 해당 트리의 노드가 없다는 뜻이므로 새로운 newNode를 root노드로 만들어주고 return을 한다.

그렇지 않다면 노드의 값을 비교해서 클 때와 작을 때 서로 비교한 뒤, 자리에 알맞는 노드에 삽입하면 된다.

/*삽입 연산*/
    public void insert(int data) {
        Node newNode = new Node(data); // 왼쪽, 오른쪽 자식 노드가 null 이며 data 의 값이 저장된 새 노드 생성
        if(root == null){// 루트 노드가 없을때, 즉 트리가 비어있는 상태일 때,
            root = newNode;
            return;
        }
        Node currentNode = root;
        Node parentNode = null;

        while(true) {

            parentNode = currentNode;

            if(data < currentNode.getData()) { // 해당 노드보다 클 떄.
                currentNode = currentNode.getLeft();
                if(currentNode == null) { // 더 이상 자식 노드가 없을 때, 즉 삽입 할 수 있는 때
                    parentNode.setLeft(newNode);
                    return ;
                }
            }else { // 해당 노드보다 작을 때.
                currentNode = currentNode.getRight();
                if(currentNode == null){ // 더 이상 자식 노드가 없을 때, 즉 삽입 할 수 있는 때
                    parentNode.setRight(newNode);
                    return ;
                }
            }
        }
    }

🔹 삭제 연산

삭제 연산은 조금 까다로운 부분이 있다.

우리가 만약 자식이 모두 있는 트리의 노드를 삭제했다고 한다면, 삭제한 노드의 자식들은 어떤 순서에 의해 배치될까?

이것이 모호하기 때문에 우리는 삭제 연산에서 케이스를 나눠서 연산을 한다. 케이스는 크게 3가지가 있다.

1. 자식 노드가 없는 경우
2. 하나의 자식 노드를 갖는 경우
3. 두개의 자식 노드를 갖는 경우

삭제 연산 기본 세팅

/*삭제 연산*/
    public boolean delete(int data){
        Node parentNode = root;
        Node currentNode = root;
        boolean isLeftChild = false;

        while(currentNode.getData() != data) {
            parentNode = currentNode;
            if(currentNode.getData() > data) {
                isLeftChild = true;
                currentNode = currentNode.getLeft();
            }else {
                isLeftChild = false;
                currentNode = currentNode.getRight();
            }
            if(currentNode == null){
                return false;
            }
        }

        if(currentNode.getLeft() == null && currentNode.getRight() == null) { // 1. 자식 노드가 없는 경우
            if(currentNode == root) {
                root = null; // 해당 노드가 root node일 경우
            }
            if(isLeftChild) {
                parentNode.setLeft(null); // 삭제할 노드가 부모 노드의 왼쪽 자식일 경우
            }
            else {
                parentNode.setRight(null); // 삭제할 노드가 부모 노드의 오른쪽 자식일 경우
            }
        } else if(currentNode.getRight() == null){      // 2-1. 자식 노드가 하나인 경우(오른쪽 자식이 없을 때)
            parentNode.setLeft(currentNode.getLeft());
        } else if(currentNode.getLeft() == null) {      // 2-2. 자식 노드가 하나인 경우(왼쪽 자식이 없을 떄)
            parentNode.setRight(currentNode.getRight());
        } else {                                        // 3. 자식이 둘인 경우
                Node minimum = getMinumun(currentNode);
                if(currentNode == root) {
                    root = minimum;
                }else if (isLeftChild){
                    parentNode.setLeft(minimum);
                }else {
                    parentNode.setLeft(currentNode.getLeft());
                }
                minimum.setLeft(currentNode.getLeft());
        }
        return false;
    }

    Node getMinumun(Node deleteNode) {
        Node minimum = null;
        Node minimumParent = null;
        Node currentNode = deleteNode.getRight();
        while(currentNode != null) {
            minimumParent = minimum;
            minimum = minimumParent;
            currentNode = currentNode.getLeft();
        }
        if(minimum != deleteNode.getRight()){
            minimumParent.setLeft(minimum.getRight());
            minimum.setRight(deleteNode.getRight());
        }
        return minimum;
    }

 

4️⃣ Binary Search Tree(이진 탐색 트리) 성능

이진탐색트리는 이진 탐색을 위한 트리다. 루트노드를 포함해서, 부모 노드가 왼쪽에 작은 값의 자식을, 오른쪽에는 큰 값의 자식을 가지는 구조다. 검색할 때 부모 노드를 보고 부모보다 작은 값을 찾고 있다면 왼쪽 서브트리를 탐색하고 큰 값을 찾고 있다면 오른쪽 서브트리를 탐색하면 된다. 각 단계마다 해야되는 작업이 반절로 줄어드니 O(log n)의 시간복잡도를 가진다.

 

이진 트리는 왼쪽 서브트리와 오른쪽 서브트리의 균형이 맞아야 성능이 보장된다. 한쪽으로 너무 치우쳐져 있으면 O(n) 의 성능을 보인다. 이런 이슈로 이진트리를 균형잡히게 하도록 만든 트리가 있는데, 바로 👉 AVL tree 와 Red-Black tree 이다. (AVL tree 와 Red-Black tree에 관한 내용은 3주 뒤에 공부할 예정입니다..ㅎㅎ)

💡 이진 탐색 트리의 성능을 최대로 끌어내기 위해서는 이진 탐색 트리가 완전 이진 트리에 가까워 질 수 있도록 설계해야 한다.

▶︎ 높이가 낮을수록 탐색을 빠르게 할 수 있기 때문에 균형이 잡힌 트리가 될 수 있도록 설계해야 한다.

✔️ 시간 복잡도

• 균형 트리 : 노드 개수가 N개일 때 O(logN)
• 편향 트리 : 노드 개수가 N개일 때 O(N)
• 편향 이진 트리(Skewed Binary Tree)은 탐색할 때 𝑂(𝑁)의 시간 복잡도를 가지기 때문에
• 이진 탐색 트리는 최대한 완전 이진 트리의 형태를 유지할 수 있도록 해야한다.

---

🌐 참고 링크

이진 탐색 트리(Binary Search Tree)개념 및 Java 구현

[자료 구조] - 트리 자료 구조 (4)-이진 탐색 트리 자바로 구현하기 :: Binary Search Tree implementation by java

[자료구조] 이진 탐색 트리(Binary Search Tree)의 정의, 노드 탐색, 삽입, 삭제

20. 이진 탐색 트리(Binary Search Tree)

이진탐색트리 (Binary Search Tree) | 👨🏻‍💻 Tech Interview

이진 탐색 트리 (binary search tree)