이진 탐색 트리 (Binary search tree) BST - 자료구조

👩‍💻 Binary search ree란?

이진 탐색 트리는 아래의 규칙으로 구성된 이진 트리이다.

1. 왼쫀 자식 노드의 키는 부모 노드의 키 보다 작음
2. 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼
3. 각각의 서브 트리도 이진 탐색 트리를 유지
4. 중복된 키를 허용하지 않음

✏️ 이진 탐색 트리의 특징

• 이진 탐색 트리 규칙에 의해 데이터가 정렬됨
• 이진 트리에 비해 탐색이 빠름 (균형 유지 필요)
  • 균형 상태 : O(logN)
  • 불균형 상태 : O(N)

✏️ 탐색

1. 찾고자 하는 데이터를 루트 노드부터 비교 시작
2. 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동
3. 찾는 데이터가 없으면 null 반환
4. 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어짐

 

✏️ 삽입

1. Root 부터 비교 시작 (중복 키 발견 시 노드를 추가하지 않고 종료)
2. 삽입할 키가 현재 노드의 키보다 작으면 왼쪽으로 이동
3. 삽입할 키가 현재 노드의 키보다 크면 오른쪽으로 이동
4. Leaf 노드에 도달 후 키 비교하여 작으면 왼쪽, 크면 오른쪽에 삽입

 

✏️ 삭제

• 삭제 대상 노드가 Leaf 노드인 경우
  1. 삭제 대상 노드 삭제
  2. 부모 노드의 해당 자식 링크 null로 변경

 

• 삭제 대상 노드에 자식 노드가 하나 있는 경우
  1. 자식 노드를 삭제 대상 노드의 부모 노드에 연결
  2. 삭제 대상 노드 삭제

 

• 삭제 대상 노드에 자식 노드가 둘인 경우
  1. 노드 선택
     • 방법1) 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드 선택
     • 방법2) 삭제 대상 노드의 오른쪽 서브트리에서 가장 작은 노드 선택
  2. 두 가지 방법 중 선택한 노드를 삭제 대상 노드 위치로 올림 (**이진 탐색 트리의 특성 유지를 위해)
  3. 위로 올리는 과정에서 다른 자식 노드들의 링크 연결 작업 진행
  4. 삭제 대상 노드 삭제

 

✏️ 이진 탐색 트리 코드 구현

1) 기본 구현

package algorithmBasic.tree;

class Node{
    int key;
    Node left;
    Node right;

    Node(int key, Node left, Node right){
        this.key = key;
        this.left = left;
        this.right = right;
    }

}
public class BinarySearchTree {
    Node head;

    BinarySearchTree(int key){
        this.head = new Node(key, null, null);
    }

    public void addNode(int key){
        if(this.head == null){
            this.head = new Node(key, null, null);
        }else{
            Node cur = this.head;

            while(true){
                Node pre = cur;

                if(key < cur.key) {
                    cur = cur.left;

                    if (cur == null) {
                        pre.left = new Node(key, null, null);
                        break;
                    }
                }
                else{
                    cur = cur.right;

                    if(cur == null){
                        pre.right = new Node(key, null, null);
                        break;
                    }
                }
            }
        }
    }

    public void removeNoe(int key){
        Node parent = null;
        Node successor = null;
        Node predecessor = null;
        Node child = null;

        Node cur = this.head;
        while(cur != null){
            if(key == cur.key){
                break;
            }
            parent = cur; //cur위치 변환 위에 있으므로 종료시 cur의 부모노드를 가진다.

            if(key < cur.key){
                cur = cur.left;
            }else{
                cur = cur.right;
            }
        }
        if(cur == null){
            System.out.println("key에 해당하는 노드가 없습니다.");
            return;
        }

        // Leaf 노드 인 경우
        if(cur.left == null && cur.right == null){
            if(parent == null){ // 사실상 트리에 노드가 한 개인 케이스
                this.head = null;
            }else{
                if(parent.left == cur){
                    parent.left = null;
                }else{
                    parent.right = null;
                }
            }
        }
        // 자식 노드가 한 개인 경우
        else if((cur.left != null && cur.right == null)
            || (cur.left == null && cur.right != null)){
            if(cur.left != null){
                child = cur.left;
            }else{
                child = cur.right;
            }
            if(parent == null){ // cur이 루트노드이고, 루트노드에 자식이 하나 있는 경우
                this.head = child;
            }else{
                if(parent.left == cur){
                    parent.left = child;
                }else{
                    parent.right = child;
                }
            }
        }
        // 자식 노드가 둘 인 경우 (제일 복잡한)
        else{
            predecessor = cur;
            successor = cur.left; // 삭제 대상 노드기준 왼쪽에서 제일 오른쪽에 있는 것 빼오기

            while(successor.right != null){
                predecessor = successor;
                successor = successor.right;
            }
            predecessor.right = successor.left;
            successor.left = cur.left;
            successor.right = cur.right;

            if(parent == null){
                this.head = successor;
            }else{
                if(parent.left == cur){
                    parent.left = successor;
                }else{
                    parent.right = successor;
                }
            }
        }
    }

}

 

2) 재귀 함수를 사용한 코드 구현

package algorithmBasic.tree;

public class BinarySearchTree2 {
    Node head;

    BinarySearchTree2(int key){
        this.head = new Node(key, null, null);
    }

    public Node addNodeRecursive(Node cur, int key){
        if(cur == null){
            return new Node(key, null, null);
        }
        if(key < cur.key){
            cur.left = addNodeRecursive(cur.left, key);
        }else{
            cur.right = addNodeRecursive(cur.right, key);
        }

        return cur;
    }

    public Node removeNodeRecursive(Node cur, int key){
        if(cur == null){
            return null;
        }
        if(key < cur.key){
            cur.left = removeNodeRecursive(cur.left, key);
        }else if(key > cur.key){
            cur.right = removeNodeRecursive(cur.right, key);
        }else{
            if(cur.left == null){ // 자식노드가 하나 있거나, 없는 경우
                return cur.right;
            }else if(cur.right == null){
                return cur.left;
            }else{
                Node predecessor = cur;
                Node successor = cur.left;

                while(successor.right != null){
                    predecessor = successor;
                    successor = successor.right;
                }
                predecessor.right = successor.left;
                cur.key = successor.key;
            }
        }
        return cur;
    }

    // levelOrder : Queue 이용해서 출력
}