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

 

학습 전: *트리 학습하러 가기*

---

(1) 이진 탐색 트리(Binary Search Tree)

• 아래 규칙으로 구성된 이진 트리
  
  • 왼쪽 자식 노드의 키 < 부모 노드의 키
  • 오른쪽 자식 노드의 키 > 부모 노드의 키
  • 각각의 서브 트리도 이진 탐색 트리 유지
  • 중복 키 허용 X

이진 탐색 트리

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

균형 상태와 불균형 상태

---

(2) 탐색

• 찾고자 하는 데이터를 루트부터 시작
• 대소 비교를 하여(데이터 작음 → 왼쪽, 데이터 큼 → 오른쪽)으로 이동
• 찾는 데이터가 없음 → null
• 어떤 데이터를 찾더라도 최대 트리 높이 만큼 탐색이 이뤄짐

이진 탐색 트리 - 탐색

---

(3) 삽입

• Root 부터 비교 시작(중복 노드 키 발견: 종료)
• 삽입할 키 < 현재 노드의 키 → 왼쪽
• 삽입할 키 > 현재 노드의 키 → 오른쪽

이진 탐색 트리 - 삽입

---

(4) 삭제

---

(1) 삭제 노드가 Leaf 노드인 경우

• 삭제 대상 노드 삭제
• 부모 노드의 해당 자식 링크 null 변경

 

삭제 노드가 leaf인 경우

---

(2) 삭제 대상 노드에 자식 노드 하나 있는 경우

• 자식 노드를 삭제 대상 노드의 부모 노드에 연결
• 삭제 대상 노드 삭제

 

삭제 노드에 자식 하나 있는 경우

---

(3) 삭제 대상 노드에 자식이 둘인 경우
[i] 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드 선택

[ii] 삭제 대상 노드의 오른쪽 서브 트리에서 가장 작은 노드 선택

• [i] or [ii]에서 선택한 노드를 삭제 대상 노드 위치로 올림
• 위로 올리는 과정에서 다른 자식 노드들의 링크 연결 작업
• 삭제 대상 노드 삭제

삭제 대상 노드에 자식이 둘인 경우

---

(5) JAVA 코드로 학습하기

---

(1) 이진 탐색 트리 구현하기  with 레벨 순회

class Node{  //값을 저장할 노드 객체
    int key;  //값
    Node left;  //노드의 왼쪽
    Node right;  //노드의 오른쪽

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

class BinarySearchTree{  // 이진 탐색 트리
    Node head;  //이진 트리의 head Node

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

    // 값을 매개변수로 받아서 이진 탐색 트리에서 찾는 함수
    public boolean searchNode(int key){
        Queue<Node> queue = new LinkedList<>();  //queue 배열을 생성
        queue.add(this.head);  //위쪽 (head) 부터 탐색 시작
        while(!queue.isEmpty()){  //queue가 비어질 떄까지 반복
            Node cur = queue.poll();  //queue에서 node를 하나 꺼냄
            if(cur.key == key){  //꺼낸 노드가 찾는 값인 경우
                return true;
            }
            if(key < cur.key){  //찾는 값보다 현재 꺼낸 값이 더 큰 경우
                if(cur.left != null){  //왼쪽에 값이 존재하면
                    queue.offer(cur.left);  //왼쪽으로 이동
                }
            }else{  //찾는 값보다 현재 꺼낸 값이 더 작은 경우
                if(cur.right != null){  //오른쪽에 값이 존재하면
                    queue.offer(cur.right);  //오른쪽으로 이동
                }
            }
        }
        return false;
    }

    // 이진 탐색 트리에 노드 추가
    public void addNode(int key){
        if(this.searchNode(key)){  //만약 찾고자하는 데이터가 이미 존재하는 경우
            System.out.println("same key: "+ key);  //키 존재를 알림
            return;
        }

        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 removeNode(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;  //부모노드 변수에 현재 노드 저장
            if(key < cur.key){  //찾고자하는 데이터가 현재보다 작을 때
                cur = cur.left;  //왼쪽으로 이동
            }else {  //찾고자하는 데이터가 현재보다 클 때
                cur = cur.right;  //오른쪽으로 이동
            }
        }
        if(cur == null){  //만약 비어있다면
            System.out.println("Not found key: "+key);  //찾는 데이터가 없는 것
            return;
        }
        if(cur.left == null && cur.right == null){  //case1: leaf node일 때 연결 정리
            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)){  //case2: 자식 노드가 하나인 경우
            if(cur.left != null){  //왼쪽 노드가 존재하는 경우
                child = cur.left;  //자식 노드 변수에 현재의 왼쪽 노드를 저장
            }else{  //오른쪽 노드가 존재하는 경우
                child = cur.right;  //자식 노드 변수에 현재의 왼쪽 노드를 저장
            }

            if(parent == null){  //root이면서 자식 노드 1개일 경우
                this.head = child;  //헤드에 자식이 올라감
            }else{  //root는 아닌 경우
                if(parent.left == cur){  //부모의 왼쪽이 현재 타겟일 때
                    parent.left = child;  //부모의 왼쪽 자식을 연결해줌
                }else{  //부모의 오른쪽이 현재 타겟일 경우
                    parent.right = child;  //부모의 오른쪽 자식을 연결해줌
                }
            }
        } else{  //case3: 자식노드가 둘
            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){  //root, 자식 노드 2개
                this.head = successor;
            }else{
                if(parent.left == cur){
                    parent.left = successor;
                }else{
                    parent.right = successor;
                }
            }
        }
    }

    //BFS-레벨 순회: (위쪽 레벨부터) 왼쪽 노드 -> 오른쪽 노드
    public void levelOrder(Node node){
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while(!queue.isEmpty()){
            Node cur = queue.poll();

            System.out.print(cur.key + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }
}

---

(2) 앞서 (1)을 재귀 호출을 통해 구현

//앞의 BST 삽입, 삭제 코드를 제귀형태로 구현
class BinarySearchTree2{
    Node head;  //헤드 노드 변수 생성
    
    public BinarySearchTree2(int key) {
        this.head = new Node(key, null,null);
    }

    //앞의 코드 참고
    public Node searchNode(int key){
        Queue<Node> queue = new LinkedList<>();
        queue.add(this.head);
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            if(cur.key == key){
                return cur;
            }
            if(key < cur.key){
                if(cur.left != null){
                    queue.offer(cur.left);
                }
            }else{
                if(cur.right != null){
                    queue.offer(cur.right);
                }
            }
        }
        return null;
    }
    //재귀 함수 - 함수 안에서 조건에 맞으면 본인 호출
    public Node addNodeRecursive(Node cur, int key){
        if(this.searchNode(key) != null){  //찾는 값이 트리에 이미 존재하고 있다면
            System.out.println("same key: "+ key);
            return this.head;
        }
        if(cur == null){  //넣으려는 값이 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(this.searchNode(key) == null){  //찾고자 하는 값이 존재하지 않으면
            System.out.println("Not found key: "+ key);
            return this.head;
        }
        if(cur == null){  //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;
    }

    //BFS-레벨 순회: (위쪽 레벨부터) 왼쪽 노드 -> 오른쪽 노드
    public void levelOrder(Node node){
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while(!queue.isEmpty()){
            Node cur = queue.poll();

            System.out.print(cur.key + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }
}

• 이진 탐색 트리는 지우고자하는 타켓의 자식이 존재하는 경우에 연결 해주는 과정이 중요함