Binary Search Tree

Tree

---

실제 나무를 거꾸로 한 것과 같은 모양을 하고 있기 때문에 트리라고 부른다. 나뭇가지처럼 노드들이 서로 연결된 비선형 계층 구조를 가지고 있다. 또한 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 하다. 컴퓨터의 direcory구조가 트리 구조의 대표적인 예가 될 수 있다.

 

트리와 관련된 용어

---

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
• 내부(internal) 노드: 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선 (link, branch라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

 

이진 탐색 트리

---

일반적인 이진트리란 각각의 노드가 최대 2개의 자식 노드를 가질 수 있는 트리이다. 반면 이진 탐색 트리는 기본적인 특징은 이진트리와 같지만 하나 다른 점은 자기 왼쪽에는 자신보다 값이 작은 노드가 오른쪽에는 자신보다 값이 큰 노드가 와야 한다. 이와 같은 특징으로 인해 delete나 insert를 할 시 올바른 위치를 찾아 곧바로 넣거나 뺄 수 있으며 최댓값과 최솟값을 쉽게 찾을 수 있다. 시간 복잡도 또한 평균적으로 O(log n)이며 최악의 경우는 O(n)으로 우수한 자료구조라고 할 수 있다. 이러한 이유로 트리 중에서 가장 널리 쓰이는 자료구조이다.

 

 

이진 탐색 트리의 구조

---

• 최상위 레벨에 루트 노드가 있다.
• 루트 노드는 0개 이상 2개 이하의 자식 노드를 갖고 있다.
• 그 자식 노드 또한 0개 이상 2개 이하의 자식 노드를 갖고 있고 이는 반복적으로 정의된다.
• 노드들과 노드들을 연결하는 간선들로 구성되어 있으며 사이클이 존재할 수 없다.
• 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있다.

 

 

이진 탐색 트리 insert, select 구현

---

public class MyTree{
    
    //트리의 최상위 노드
    public Node head;
    
    //각각의 노드
    public class Node{
        int data;
        Node left = null;
        Node right = null;
        
        public Node(int data){
            this.data = data;
        }
    }
    
    //트리에 노드를 삽입하는 메소드
    public boolean insertNode(int data){
        
        if(this.head == null){
            //트리에 노드가 하나도 저장이 안되어 있을 때
            this.head = new Node(data);
            return true;
        } else {
            //트리에 노드가 하나 이상 저장이 되어 있을 때
            Node findNode = this.head;
            while(true){
                //insert하려는 data가 저장되어 있는 data보다 작을 때
                if(data < findNode.data){
                    if(findNode.left == null){
                        //노드가 저장이 안되어 있으면 저장하기
                        findNode.left = new Node(data);
                        break;
                    } else {
                        //노드가 저장되어 있으면 왼쪽 노드로 이동하기
                        findNode = findNode.left;
                    }
                } else {
                    //insert하려는 data가 저장되어 있는 data보다 클 때
                    if(findNode.right == null){
                        //노드가 저장이 안되어 있으면 저장하기
                        findNode.right = new Node(data);
                        break;
                    } else {
                        //노드가 저장되어 있으면 오른쪽 노드로 이동하기
                        findNode = findNode.right;
                    }
                }
            }
            return true;
        }
    }
    
    //트리의 노드를 검색하는 메소드
    public Node searchNode(int data){
        
        if(this.head == null){
            //트리에 노드가 하나도 없을 시
            return null;
        } else {
            //트리에 노드가 하나 이상 있을 시
            Node findNode = this.head;
            while(findNode != null){
                if(data == findNode.data){
                    //search하려는 data와 노드의 data가 동일할 시
                    return findNode;
                } else if(data < findNode.data){
                    //search하려는 data가 노드의 data보다 작을 시
                    findNode = findNode.left;
                } else {
                    //search하려는 data가 노드의 data보다 클 시
                    findNode = findNode.right;
                }
            }
            //해당 트리에 일치하는 노드가 없을 시
            return null;
        }
    }
    
}

 

 

이진 탐색 트리 delete 구현

---

delete의 구현을 케이스로 나누면 하기와 같은 케이스로 정리할 수 있다.

•  삭제 대상인 노드가 leaf 노드 일 경우 : 삭제할 노드의 부모 노드가 삭제 대상 노드를 가리키지 않도록 한다.
•  삭제 대상인 노드가 자식 노드를 한 개 가지고 있을 경우 : 삭제할 노드의 부모 노드가 삭제할 노드의 자식 노드를 가리키도록 한다
• 삭제 대상인 노드가 자식 노드를 두 개 가지고 있을 경우 :
  •   삭제할 노드의 오른쪽 자식 중 가장 작은 값을 삭제할 노드의 부모 노드가 가리키도록 한다.
  •   삭제할 노드의 왼쪽 자식 중 가장 큰 값을 삭제할 노드의 부모 노드가 가리키도록 한다.

        //트리의 노드를 삭제하는 메소드
        public boolean deleteNode(int data){
            if(this.head == null){
                //트리에 노드가 하나도 없을 시
                return false;
            } else if(this.head.data == data && this.head.left == null && this.head.right == null){
                //트리에 노드가 하나있고 해당 노드가 삭제 대상의 노드일 시
                this.head = null;
                return true;
            } else {
                //트리에 노드가 여러개 있고 삭제 대상 노드가 존재하는지 모를 시
                
                //삭제대상 노드가 트리에 있는지 체크하는 플래그
                boolean searchedFlag = false;
                
                Node curNode = this.head;
                Node curParentNode = this.head;
                
                //삭제 대상 노드가 트리에 있는지 체크
                while(curNode != null){
                    if(data == curNode.data){
                        //삭제 대상 노드가 있을 시
                        searchedFlag = true;
                        break;
                    } else if(data < curNode.data){
                        curParentNode = curNode;
                        curNode = curNode.left;
                    } else {
                        curParentNode = curNode;
                        curNode = curNode.right;
                    }
                }
                
                if(searchedFlag == false){
                    //삭제 대상 노드가 트리에 없을 시
                    return false;
                }
                
                if(curNode.left == null && curNode.right == null) {
                    //1. 삭제 대상 노드가 리프 노드일 경우
                    if(data < curParentNode.data){
                        curParentNode.left = null;
                        return true;
                    } else {
                        curParentNode.right = null;
                        return true;
                    }
                } else if(curNode.left != null && curNode.right == null) {
                    //2-1.삭제 대상 노드가 왼쪽 자식 노드만을 가지고 있을 경우
                    if(data < curParentNode.data) {
                        curParentNode.left = curNode.left;
                        return true;
                    } else {
                        curParentNode.right = curNode.left;
                        return true;
                    }
                } else if(curNode.left == null && curNode.right != null) {
                    //2-2. 삭제 대상 노드가 오른쪽 자식 노드만을 가지고 있을 경우
                    if(data < curParentNode.data){
                        curParentNode.right = curParentNode.right;
                        return true;
                    } else {
                        curParentNode.right = curParentNode.left;
                        return true;
                    }
                } else {
                    //3. 삭제 대상 노드가 두개의 자식 노드를 가지고 있을 경우
                    Node changeNode = curNode.right;
                    Node changeParentNode = curNode.right;
    
                    //삭제 대상 노드의 오른쪽 자식 노드들 중 가장 왼쪽 값찾기
                    //(즉, 오른쪽 자식 노드 들 중 가장 작은 값 찾기)
                    while(changeNode.left != null){
                        changeParentNode = changeNode;
                        changeNode = changeNode.left;
                    }
    
                    if(changeNode.right != null){
                        //삭제 대상 노드의 오른쪽 자식 중 가장 작은 값을 가진 노드의 오른쪽에 자식 노드가 있을 사
                        changeParentNode.left = changeNode.right;
                    } else {
                        //삭제 대상 노드의 오른쪽 자식 중 가장 작은 값을 가진 노드의 오른쪽에 자식 노드가 없을 시
                        changeParentNode.left = null;
                    }
                    
                    if(data < curParentNode.data){
                         //삭제 대상의 부모 노드의 왼쪽 자식 노드에 삭제할 노드의 오른쪽 자식중
                        //가장 작은 값을 가진 노드를 연결
                        curParentNode.left = changeNode;
                        changeNode.left = curNode.left;
                        changeNode.right = curNode.right;
                        
                        curNode = null;
                        
                        return true;
                    } else {
                        //삭제 대상의 부모 노드의 오른쪽 자식 노드에 삭제할 노드의 오른쪽 자식중
                        //가장 작은 값을 가진 노드를 연결
                        curParentNode.right = changeNode;
                        changeNode.left = curNode.left;
                        changeNode.right = curNode.right;
                        
                        curNode = null;
                        return true;
                    }
                }
            }
        }