트리와 이진 탐색 트리 - 2

트리와 이진 탐색 트리 - 2

이진 탐색 트리 삭제

 

삭제는 많이 복잡하지만 로직만 잘 세우면 단순한 것 같음

• Leaf Node 삭제 (제일 마지막 노드 삭제)
• Child Node 가 하나인 Node (중간 노드 삭제)
• Child Node 가 두개인 Node (중간 노드 삭제)

 

삭제할 Node 찾기

public boolean delete(int value) {
    boolean search = false;
    
    Node curParentNode = this.head;
    Node curNode = this.head;
    
    // Node 가 하나도 없을 경우
    if(this.head == null) {
        return false;
    
    // Node 가 하나만 있고 해당 Node 를 삭제 할 경우
    } else {
        if(this.head.value == value
           && this.head.left == null && this.head.right == null) {
            this.head = null;
            return true;
        }
        
        while(curNode != null) {
            if(curNode.value == value) {
                search = true;
                break;
                
            } else if(value < curNode.value) {
                curParentNode = curNode;
                curNode = curNode.left;
                
            } else {
                curParentNode = curNode;
                curNode = curNode.right;
            }
        }
        
        if(search == false) {
            return false;
        }
    }
    
    
    // 삭제할 Node가 Leaf Node 인 경우
    if(curNode.left == null && curNode.right == null) {
        // 왼쪽 노드
        if(value < curParentNode.value) {
            curParentNode = null;
            // 해당 노드 삭제
            curNode = null;
            
        } else {
            curParentNode.right = null;
            curNode = null;
        }
        return true;
        
    // 삭제할 Node가 Child Node를 한 개 가지고 있을 경우 (왼쪽)
    } else if(curNode.left != null && curNode.right == null) {
        if(value < curParentNode.value) {
            curParentNode.left = curNode.left;
            curNode = null;
            
        } else {
            curParentNode.right = curNode.left;
            curNode = null;
        }
        return true;
        
    // 삭제할 Node가 Child Node를 한 개 가지고 있을 경우 (오른쪽)
    } else if(curNode.left == null && curNode.right != null) {
        if(value < curParentNode.value) {
            curParentNode.left = curNode.right;
            curNode = null;
            
        } else {
            curParentNode.right = curNode.right;
            curNode = null;
        }
        return true;
        
    // 삭제할 Node가 Child Node를 두 개 가지고 있을 경우
    } else {
        // 삭제할 Node의 오른쪽 자식 중, 가장 작은 값 (왼쪽)을 가진 Node 찾기
        // 삭제 할 노드가 왼쪽에 있는 경우
        if(value < curParentNode.value) {
            Node changeNode = curNode.right;
            Node changeParentNode = curNode.right;
            
            // 가장 작은 값 (왼쪽) 찾기
            while(changeNode.left != null) {
                changeParentNode = changeNode;
                changeNode = changeNode.left;
            }
            
            // changeNode의 오른쪽 자식이 있을 경우
            if(changeNode.right != null) {
                changeParentNode.left = changeNode.right;
                
            } else {
                // changeNode의 오른쪽 자식이 없을 경우
                changeParentNode.left = null;
            }
            
            // curParentNode 왼쪽을 삭제할 노드의 가장 작은 changeNode 연결
            curParentNode.left = changeNode;
            
            // 현재 curParentNode의 왼쪽 노드는 changeNode
            // changeNode의 왼쪽/오른쪽 노드를 curNode의 기존 왼쪽/오른쪽으로 변경
            changeNode.right = curNode.right;
            changeNode.left = curNode.left;
            
            // 현재 노드 삭제
            currNode = null;
            
        // 삭제 할 노드가 오른쪽에 있는 경우
        } else {
            Node changeNode = curNode.right;
            Node changeParentNode = curNode.right;
            
            // 가장 작은 값 (왼쪽) 찾기
            while(changeNode.left != null) {
                changeParentNode = changeNode;
                changeNode = changeNode.left;
            }
            
            // changeNode의 오른쪽 자식이 있을 경우
            if(changeNode.right != null) {
                changeParentNode.left = changeNode.right;
                
            } else {
                // changeNode의 오른쪽 자식이 없을 경우
                changeParentNode.left = null;
            }
            
            // curParentNode 오른쪽에 삭제할 노드의 가장 작은 changeNode 연결
            curParentNode.right = changeNode;
            
            // 현재 curParentNode의 왼쪽 노드는 changeNode
            // changeNode의 왼쪽/오른쪽 노드를 curNode의 기존 왼쪽/오른쪽으로 변경
            changeNode.right = curNode.right;
            changeNode.left = curNode.left;
            
            // 현재 노드 삭제
            currNode = null;
        }
        return true;
    }
}

 

 

시간 복잡도

https://blog.penjee.com/wp-content/uploads/2015/12/optimal-binary-search-tree-from-sorted-array.gif

• depth 를 h라고 표기하면, O(h)
• 각 depth 마다 노드가 2배씩 늘어남, 하지만 1/2 씩 제거를 함
• n개의 노드를 가진다면, h = log₂n 에 가까움 ➡️ O(logn)
• 한번 실행 시 절반의 실행시간을 단축

 

단점

• 균형 잡힌 트리의 경우, 평균 시간 복잡도는 O(logn)
• 완전 불균형한 형태일 경우 링크드 리스트와 동일한 성능을 보여줌 (O(n))

https://blog.penjee.com/wp-content/uploads/2015/11/binary-search-tree-degenerating-demo-animation.gif

 

 

 

 

 

 

 

feat.한 번에 끝내는 코딩테스트369 Java편 - 패스트캠퍼스