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

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

• 아래의 규칙으로 구성된 이진 트리
  • 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음
  • 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼
  • 각각의 서브 트리도 이진 탐색 트리를 유지
  • 중복된 키를 허용하지 않음
    

    

2. 이진 탐색 트리 특징

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

    

3. 이진 탐색 트리 - 탐색

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

  

4. 이진 탐색 트리 - 삽입

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

  

5. 이진 탐색 트리 - 삭제

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

    

• 삭제 대상 노드에 자식 노드가 하나 있는 경우
  • 자식 노드를 삭제 대상 노드의 부모 노드에 연결
  • 삭제 대상 노드 삭제
• 삭제 대상 노드에 자식 노드가 둘인 경우
  1. 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드 선택
  2. 삭제 대상 노드의 오른쪽 서브 트리에서 가장 작은 노드 선택
  3. 1번 또는 2번에서 선택한 노드를 삭제 대상 노드 위치로 올림
  4. 위로 올리는 과정에서 다른 자식 노드들의 링크 연결 작업 진행
  5. 삭제 대상 노드 삭제
     

     

6. 코드

class Node {
    char data;
    Node left;
    Node right;
    
    public Node(char data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.righr = right;
    }
}

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 removeNode(int key) {
        Node parent = null;
        Node successor = null; // 후계자를 저장할 노드
        Node predecessor = null; // successor의 부모 노드
        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("key에 해당하는 노드가 없습니다.");
            return;
        }
        
        if(cur.left == null && cur.right == null) { // leaf 노드인 경우
            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) { // 자식 노드가 1개인 경우
            if(cur.left != null) {
                child = cur.left;
            } else {
                child = cur.right;
            }
            
            if(parent == null) { // 현재 루트 노드인데 자식 노드가 1개인 경우
                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;
                }
            }
        }
    }
    
    public void levelOrder(Node node) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        
        while(!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.print(cur.data + " ");
            
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
}

// 재귀 함수 사용하여 이진 탐색 트리 구현
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(keu > 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;
    }
}