Binary Search Tree(이진 탐색 트리)

Binary Search Tree는 특정한 규칙을 따르는 이진 트리이다.

이진 트리는 부모 노드가 자식 노드를 최대 2개까지 갖는 트리이다.

특정한 규칙이란

1. 왼쪽 자식 노드는 부모 노드보다 작거나 같다.
2. 오른쪽 자식 노드는 부모 노드보다 크다.

이진 탐색은 주어진 목표를 향해 전체 크기의 반씩 나누고 비교하여 접근하는 탐색 방법이다.

원래는 정렬된 배열에서만 가능했다. 하지만 이진 탐색 트리는 위의 규칙 덕분에 root 노드로부터 찾고자 하는 값을 비교해감으로써 원하는 값에 접근이 쉽다.

 

---

✅ 장점

1. 탐색, 삽입, 삭제의 연산이 평균적으로 빠르다.

• 트리의 노드 개수가 n 일때, 탐색, 삽입, 삭제의 평균적인 시간 복잡도는 O(log n) 이다.
• 트리의 높이가 h 일때, 연산을 최대 h번 한다.
• 균형이 잘 갖춰진 트리일 수록 높이가 log n 에 가깝다.

2. 동적 데이터 관리가 용이하다.

• 배열과 다르게 크기가 고정되어 있지 않다.
• 삽입, 삭제가 평균적으로 빠르기 때문에 데이터가 변동이 큰 환경에서 유리하다.

3. 중위 순회로 정렬된 결과를 얻을 수 있다.

• 이진 탐색 트리의 규칙으로, 값들이 정렬되어 있기 때문에 중위 순회로 (배열처럼) 정렬된 결과를 얻을 수 있다.

---

❌ 단점

1. 편향 된 트리에서는 일반 배열과 연산 속도가 비슷하다.

• 트리가 한쪽으로 편향 된 상황에서는 일반 배열과 연산 속도에서 큰 차이가 없다. (오히려 더 느릴수도 있다.)
• 예를 들어, 정렬된 데이터를 순서대로 삽입하면 다음과 같은 트리가 된다.

  1
   \
    2
     \
      3
       \
        4
         \
          5

• 이런 최악의 경우에는 시간 복잡도가 O(log n)이 아니라 O(n)이 될 수 있다.

2. 캐시 효율성이 낮음

• 배열은 메모리의 연속된 공간을 사용한다.
• 하지만 BST의 노드들은 포인터를 통해 연결되어 있고, 메모리의 이곳저곳에 흩어져 있다.
• 프리패칭(prefetching)의 특징까지 더해져 배열은 캐시에 적재되면 연속된 데이터들에 쉽게 접근이 가능하다.
• 하지만 BST는 캐시가 한 번에 여러 노드를 불러오는 것이 어렵고, 캐시 미스(Cache Miss)가 자주 발생함.
• 그래서 실제 성능이 기대보다 낮을 수도 있다.

3. 추가적인 포인터 저장 공간이 필요함.

• 배열과 달리, 각 노드가 왼쪽/오른쪽 자식 노드를 가리키는 포인터를 저장해야 함.
• 노드 개수가 많아질수록 메모리 오버헤드가 발생함.

 

---

Insert

삽입을 할 때의 경우를 떠올려보았다.

case 1 : 빈 트리

case 2 : 비어있지 않은 트리

---

case1 : 빈 트리

갓 생성한 BST에는 아무런 노드가 없다.

새로 insert 하면, 해당 노드를 root로 설정하고 retrun 한다.

public Node insert(Node node) {
        if (this.root == null) {
            this.root = node;
            return this.root;
        }
   .
   .
   .

---

case 2 : 비어있지 않은 트리

트리에 원소가 최소 하나 이상이란 이야기.

root 노드부터 차근차근 비교해주면서 좌우로 이동한다. 비교한 노드의 자식 노드가 없다면 그 자리에 삽입하는 노드와 연결해준다.

public void insert(Node node) {
		. . .
       Node cur = this.root;
        while (cur != null) {
            if (node.getData() <= cur.getData()) {
                if (cur.getLeft() == null) {
                    cur.setLeft(node);
                    node.setParent(cur);
                    return cur.getLeft();
                }
                cur = cur.getLeft();
            } else if (cur.getData() < node.getData()) {
                if (cur.getRight() == null) {
                    cur.setRight(node);
                    node.setParent(cur);
                    return node;
                }
                cur = cur.getRight();
            }   
        }
        return node;
    }

---

Delete

삭제할 때의 경우는 크게 3가지이다.

• case 1 : 자식노드가 0개인 경우
• case 2 : 자식노드가 1개인 경우
• case 3 : 자식노드가 2개인 경우

• case 3-1 : 자식노드가 2개인데, 제일 작은 노드가 자식노드일 때
• case 3-2 : 자식노드가 2개인데, 제일 작은 노드가 자식노드가 아닐 때

---

case 1 : 자식노드가 0개

    // 자식 노드가 0개인 경우
    private Node case1(Node targetNode){
        if (targetNode.getData() == this.root.getData()) {setRoot(null);;}

        Node parent = targetNode.getParent();

        if (parent.getLeft().getData() == targetNode.getData()) {parent.setLeft(null);}
        else {parent.setRight(null);}

        targetNode.setParent(null);

        return targetNode;
    }

---

case 2 : 자식노드가 1개

// 자식 노드가 1개인 경우
    private Node case2(Node targetNode){
        Node parent = targetNode.getParent();

        Node targetNodeChild = null;
        if (targetNode.getLeft() != null) {targetNodeChild = targetNode.getLeft();}
        else {targetNodeChild = targetNode.getRight();}

        // targetNode가 root인 경우
        if (parent == null) {
            targetNodeChild.setParent(null);
            setRoot(targetNodeChild);

            targetNode.setLeft(null);
            targetNode.setRight(null);
            return targetNode;
        }

        // 부모노드의 왼쪽 자식이면
        if (parent.getLeft().getData() == targetNode.getData()) {parent.setLeft(targetNodeChild);}
        // 오른쪽 자식이면
        else {parent.setRight(targetNodeChild);}

        targetNodeChild.setParent(parent);

        targetNode.setParent(null);
        targetNode.setLeft(null);
        targetNode.setRight(null);

        return targetNode;
    }

---

case 3-1 : 자식노드가 2개인데, 제일 작은 노드가 자식노드일 때

 

//자식 노드가 2개인데, 제일 작은 노드가 자식 노드가 아닐 때
    private Node case31(Node targetNode){
        Node parent = targetNode.getParent();

        Node rightSubTreeNodeParent = targetNode.getRight();
        Node rightSubTreeNode = targetNode.getRight().getLeft();
        while (rightSubTreeNode.getLeft() != null) {
            rightSubTreeNodeParent = rightSubTreeNode;
            rightSubTreeNode = rightSubTreeNode.getLeft();
        }
        // 노드와 부모 노드의 연결을 끊는다.
        rightSubTreeNodeParent.setLeft(rightSubTreeNode.getRight());
        if (rightSubTreeNode.getRight() != null) {rightSubTreeNode.setParent(rightSubTreeNodeParent);}
        
        // targetNode의 자식노드들의 부모노드를 rightSubTreeNode로 설정한다.
        targetNode.getRight().setParent(rightSubTreeNode);
        targetNode.getLeft().setParent(rightSubTreeNode);

        //rightSubTreeNode의 왼쪽 자식을 targetNode의 왼쪽 자식으로, 오른쪽 자식은 오른쪽 자식으로 설정한다.
        rightSubTreeNode.setLeft(targetNode.getLeft());
        rightSubTreeNode.setRight(targetNode.getRight());

        //targetNode의 양쪽자식을 null로 설정한다.
        targetNode.setLeft(null);
        targetNode.setRight(null);

        // 지우려는 노드가 root 노드라면
        if (parent == null) {setRoot(rightSubTreeNode);}
        else {
            // 아니라면 부모노드와 이어줘야 됨.
            rightSubTreeNode.setParent(parent);

            //parent의 왼쪽 자식이면
            if (parent.getLeft().getData() == targetNode.getData()) {parent.setLeft(rightSubTreeNode);}
            else {parent.setRight(rightSubTreeNode);}
        }

        return targetNode;
    }

---

case 3-2 : 자식노드가 2개인데, 제일 작은 노드가 자식노드가 아닐 때

//자식 노드가 2개인데, 제일 작은 노드가 자식 노드일 때
    private Node case32(Node targetNode){
        Node parent = targetNode.getParent();
        Node rightNode = targetNode.getRight();
        
        // targetNode가 root가 아니면
        if (parent != null) {
            if (parent.getLeft().getData() == targetNode.getData()) {parent.setLeft(rightNode);}
            else {parent.setRight(rightNode);}

            rightNode.setParent(parent);
        }
        // root 가 맞다면
        else {
            setRoot(rightNode);
            rightNode.setParent(null);
        }

        rightNode.setLeft(targetNode.getLeft());
        targetNode.getLeft().setParent(rightNode);
        
        targetNode.setParent(null);
        targetNode.setRight(null);
        targetNode.setLeft(null);
    

        return targetNode;
    }

 

 

---

완성된 이진 탐색 트리

아래 더 보기를 누르면 확인할 수 있음.

package Trees;

public class BST {
    protected Node root;

    protected void setRoot(Node node) {this.root = node;}
    public Node getRoot() {return this.root;}
    
    // 삽입
    public Node insert(int data) {
        return insert(new Node(data));
    }

    public Node insert(Node node) {
        if (this.root == null) {
            this.root = node;
            return this.root;
        }
        
        Node cur = this.root;
        while (cur != null) {
            if (node.getData() <= cur.getData()) {
                if (cur.getLeft() == null) {
                    cur.setLeft(node);
                    node.setParent(cur);
                    return cur.getLeft();
                }
                cur = cur.getLeft();
            } else if (cur.getData() < node.getData()) {
                if (cur.getRight() == null) {
                    cur.setRight(node);
                    node.setParent(cur);
                    return node;
                }
                cur = cur.getRight();
            }   
        }
        return node;
    }

    // 삭제
    public Node delete(int data) {
        return delete(new Node(data));
    }

    // 자식 노드가 0개인 경우
    private Node case1(Node targetNode){
        if (targetNode.getData() == this.root.getData()) {setRoot(null);;}

        Node parent = targetNode.getParent();

        if (parent.getLeft().getData() == targetNode.getData()) {parent.setLeft(null);}
        else {parent.setRight(null);}

        targetNode.setParent(null);

        return targetNode;
    }
    
    // 자식 노드가 1개인 경우
    private Node case2(Node targetNode){
        Node parent = targetNode.getParent();

        Node targetNodeChild = null;
        if (targetNode.getLeft() != null) {targetNodeChild = targetNode.getLeft();}
        else {targetNodeChild = targetNode.getRight();}

        // targetNode가 root인 경우
        if (parent == null) {
            targetNodeChild.setParent(null);
            setRoot(targetNodeChild);

            targetNode.setLeft(null);
            targetNode.setRight(null);
            return targetNode;
        }

        // 부모노드의 왼쪽 자식이면
        if (parent.getLeft().getData() == targetNode.getData()) {parent.setLeft(targetNodeChild);}
        // 오른쪽 자식이면
        else {parent.setRight(targetNodeChild);}

        targetNodeChild.setParent(parent);

        targetNode.setParent(null);
        targetNode.setLeft(null);
        targetNode.setRight(null);

        return targetNode;
    }

    //자식 노드가 2개인데, 제일 작은 노드가 자식 노드가 아닐 때
    private Node case31(Node targetNode){
        Node parent = targetNode.getParent();

        Node rightSubTreeNodeParent = targetNode.getRight();
        Node rightSubTreeNode = targetNode.getRight().getLeft();
        while (rightSubTreeNode.getLeft() != null) {
            rightSubTreeNodeParent = rightSubTreeNode;
            rightSubTreeNode = rightSubTreeNode.getLeft();
        }
        // 노드와 부모 노드의 연결을 끊는다.
        rightSubTreeNodeParent.setLeft(rightSubTreeNode.getRight());
        if (rightSubTreeNode.getRight() != null) {rightSubTreeNode.setParent(rightSubTreeNodeParent);}
        
        // targetNode의 자식노드들의 부모노드를 rightSubTreeNode로 설정한다.
        targetNode.getRight().setParent(rightSubTreeNode);
        targetNode.getLeft().setParent(rightSubTreeNode);

        //rightSubTreeNode의 왼쪽 자식을 targetNode의 왼쪽 자식으로, 오른쪽 자식은 오른쪽 자식으로 설정한다.
        rightSubTreeNode.setLeft(targetNode.getLeft());
        rightSubTreeNode.setRight(targetNode.getRight());

        //targetNode의 양쪽자식을 null로 설정한다.
        targetNode.setLeft(null);
        targetNode.setRight(null);

        // 지우려는 노드가 root 노드라면
        if (parent == null) {setRoot(rightSubTreeNode);}
        else {
            // 아니라면 부모노드와 이어줘야 됨.
            rightSubTreeNode.setParent(parent);

            //parent의 왼쪽 자식이면
            if (parent.getLeft().getData() == targetNode.getData()) {parent.setLeft(rightSubTreeNode);}
            else {parent.setRight(rightSubTreeNode);}
        }

        return targetNode;
    }
   
    //자식 노드가 2개인데, 제일 작은 노드가 자식 노드일 때
    private Node case32(Node targetNode){
        Node parent = targetNode.getParent();
        Node rightNode = targetNode.getRight();
        
        // targetNode가 root가 아니면
        if (parent != null) {
            if (parent.getLeft().getData() == targetNode.getData()) {parent.setLeft(rightNode);}
            else {parent.setRight(rightNode);}

            rightNode.setParent(parent);
        }
        // root 가 맞다면
        else {
            setRoot(rightNode);
            rightNode.setParent(null);
        }

        rightNode.setLeft(targetNode.getLeft());
        targetNode.getLeft().setParent(rightNode);
        
        targetNode.setParent(null);
        targetNode.setRight(null);
        targetNode.setLeft(null);
    

        return targetNode;
    }


    public Node delete(Node target) {
        if (this.root == null) {return null;}

        Node curNode = this.root;
        // 목표노드를 찾는다.
        while (curNode != null) { 
            if (target.getData() == curNode.getData()) {break;}
            else if (target.getData() <= curNode.getData()) {curNode = curNode.getLeft();}
            else if (target.getData() > curNode.getData()) {curNode = curNode.getRight();}
        }

        //Not Found
        if (curNode == null) {return null;}

        // 목표노드가 자식노드를 가지고 있는지 파악한다.
        if (curNode.getLeft() == null && curNode.getRight() == null){
            return case1(curNode);
        } else if (curNode.getLeft() != null && curNode.getRight() != null) {
            if (curNode.getRight().getLeft() != null) {return case31(curNode);}
            return case32(curNode);
        } else if (curNode.getLeft() == null || curNode.getRight() == null) {
            return case2(curNode);
        }

        return null;
    }

    // 탐색
    public boolean search(int data) {
        return search(new Node(data));
    }

    public boolean search(Node target) {
        /* 노드가 있다면 true, 없다면 false를 반환 */
        // cur 노드와 target 노드의 데이터를 비교해나가면서 target을 탐색한다.
        Node cur = root;
        while (cur != null) {
            // target이 존재하는 경우!
            if (cur.getData() == target.getData()) {
                return true;
            }

            // cur보다 작은 경우  : cur의 왼쪽 자식과 비교해야 한다.
            else if (target.getData() < cur.getData()) {
                // 아니면 왼쪽 노드로.
                cur = cur.getLeft();
            }
            // cur보다 큰 경우
            else {
                cur = cur.getRight();
            }
        }

        return false;
    }

    public void preOrder() {
        /* 전위 순회 : 노드 - 왼쪽자식 - 오른쪽자식 순으로 순회한다. */
        System.out.println("***** 전위 순회 *****");
        preOrder(root);
        System.out.println("\n= = = = = = = = = = = = = = = = = =");
    }

    private void preOrder(Node node) {
        if (node != null) {
            Systehttp://m.out.printf("%d ", node.getData());
            preOrder(node.getLeft());
            preOrder(node.getRight());
        }
    }

    public void inOrder() {
        /* 중위 순회 : 왼쪽자식 - 노드 - 오른쪽자식 순으로 순회한다. */
        System.out.println("***** 중위 순회 *****");
        inOrder(root);
        System.out.println("\n= = = = = = = = = = = = = = = = = =");
    }

    private void inOrder(Node node) {
        if (node != null) {
            inOrder(node.getLeft());
            Systehttp://m.out.printf("%d ", node.getData());
            inOrder(node.getRight());
        }
    }

    public void postOrder() {
        /* 후위 순회 : 왼쪽자식 - 오른쪽자식 - 노드 순으로 순회한다. */
        System.out.println("***** 후위 순회 *****");
        postOrder(root);
        System.out.println("\n= = = = = = = = = = = = = = = = = =");
    }

    private void postOrder(Node node) {
        if (node != null) {
            postOrder(node.getLeft());
            postOrder(node.getRight());
            Systehttp://m.out.printf("%d ", node.getData());
        }
    }
}