이진 탐색 트리(binary search tree) 란?

이진 탐색 트리(binary search tree)는 이진 트리 기반의 탐색을 위한 자료 구조이다.  탐색은 내가 생각하기에도 코딩테스트와 같은 곳에서도 자주 출제가 되며 또한 컴퓨터 프로그램에서도 많이 사용되며, 가장 시간이 많이 걸리는 작업 중의 하나이므로 탐색을 효율적으로 수행하는 것은 무척 중요하다.  자주 쓰이는 자료 구조이기 때문에 잘 개념을 익혀놔야겠다. ( "C언어로 쉽게 풀어쓴 자료구조" 라는 책으로 정리 중입니다 ) 

 

https://songeunjung92.tistory.com/31

[자료구조/java] 이진 탐색 트리 BST (Binary Search Tree) - 연결 리스트 구현

위의 블로그에서 트리의 그림만을 가져오고 있습니다. 그리고 이 공간은 제가 공부한 것을 정리하는 TIL 공간입니다

너무 잘 정리를 하셔서 공부가 잘 되었습니다. 

 

 

이진 탐색 트리의 정의 

• 왼쪽 서브 트리 키들은 루트 키보다 작다.
• 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

따라서 찾고자 하는 키 값이 이진트리의 루트 노드의 키 값과 비교하여 루트 노드보다 작으면 원하는 키 값은 왼쪽 서브 트리에 있고 루트 노드보다 크면 원하는 키 값은 오른쪽 서브 트리에 있음을 쉽게 알 수 있다. 이러한 성질을 이용하면 탐색 시간을 많이 줄일 수 있다.

 

 

 

위와 같이 이진트리를 유지하면서 루트 키 값을 기준보다 작은 것은 왼쪽 서브 트리, 큰 것은 오른쪽 서브 트리를 유지하는 구조라고 할 수 있다. 그리고 한 가지 알아두어야 할 점은 이진 탐색 트리를 중위 순회 방법으로 순회하면 2, 3, 5, 8, 10, 11, 14 ,16 으로 숫자들의 크기 순으로 정렬이 된다. 

 

 

순환적인 탐색연산 

이진 탐색 트리에서 특정한 키값을 가진 노드를 찾기 위해서는 먼저 주어진 탐색키 값과 루트노드의 키값을 비교한다. 

비교한 결과에 따라 3가지로 나누어진다.

 

• 비교한 결과가 같으면 탐색이 성공
• 주어진 키 값이 루트노드 보다 작으면 왼쪽서브 트리를 기준으로 다시 탐색
• 주어진 키 값이 루트보드 보다 크면 오른쪽 서브 트리를 기준으로 다시 탐색

 

 

위의 사진에서는 탐색키 = 11로 잡았다.  11은 루트노드의 키 값인 8보다 크기 때문에 오른쪽 서브트리로 이동해서 다시 탐색을 시작한다. 다시 키 값인 11은 루트 노드의 키 값인 10 보다 크기 때문에 오른쪽으로 이동해서 탐색한다.

이러한 과정을 반복하면 된다. 

 

 

코드 구현 

public TreeNode search(TreeNode node, int key) {
   if (node == null) return null;
   if (key == node.key) return node;
 
   else if (key < node.key) {
       return search(node.left, key);
   }
 
   else {
       return search(node.right, key);
   }
        
}

 

 

 

반복적인 탐색연산

이진 탐색트리를 탐색하는 방법에는 반복적인 방법도 존재한다. 효율성을 따지면 반복적인 함수가 순환적인 함수보다 훨씬 우수하다. 

public TreeNode search(TreeNode node, int key) {
        
     while (node != null) {
         if (key == node.key) {
             return node;
         }
         else if (key < node.key) {
             node = node.left;
         }
         else {
             node = node.right;
         }
     }
 
}

 

 

 

 

이진 탐색트리에서 삽입연산

이진 탐색 트리에 원소를 삽입하기 위해서는 먼저 탐색을 수행하는 것이 필요하다. 이유는 이진 탐색트리에서는 같은 키 값을 갖는 노드가 없어야 하기 때문이고 또한 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치이다.

 

 

 

위와 같이 삽입하려는 키 값이 있다면 탐색을 해서 자기 위치를 알아내 그 위치에 노드를 연결한다.

 

 

public TreeNode insertKey(TreeNode root, int data){
        TreeNode p = root;
        TreeNode newNode = new TreeNode(data);
 
        if(p == null){   //가장 처음 값을 insert 할 때 생김
            return newNode;
        }
        else if(p.data > newNode.data){  //루트 키 값보다 작으면 왼쪽
            p.left = insertKey(p.left,data);
            return p;
        }
        else if(p.data < newNode.data){  //루트 키 값보다 크면 오른쪽
            p.right = insertKey(p.right,data);
            return p;
        }
        else{
            return p;
        }
    }
 
    public void insertBST(int data){
        root = insertKey(root,data);
   }
 
 
 

 

이진 트리에서의 삭제연산 

노드를 삭제하는 것은 이진탐색트리에서 가장 복잡한 연산이다. 먼저 노드를 삭제하기 위해서 먼저 노드를 탐색하여야 한다는 것은 삽입과 마찬가지이다. 일단 우리가 삭제하려고 하는 키값이 트리 안에 어디 있는지를 알아야 지울 수 있을 것이다. 

 

1. 삭제하려는 노드가 단말 노드일 경우
2. 삭제하려는 노드가 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우
3. 삭제하려는 노드가 두개의 서브 트리 모두 가지고 있는 경우

 

• 첫번째 경우 : 삭제하려는 노드가 단말 노드일 경우

 

 

이 경우에는 단말노드 아래에 더 이상의 노드가 없으므로 가장 쉽게 할 수 있다. 단말 노드를 지운다는 것은 단말 노드의 부모노드를 찾아서 부모노드안의 링크필드를 null로 만들어서 연결을 끊으면 된다.

 

 

 

• 두번째 경우 : 삭제하려는 노드가 하나의 서브트리만 가지고 있는 경우

두 번째 경우도 그다지 나쁘지 않다. 즉 삭제되는 노드가 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우에는 자기 노드는 삭제하고 서브 트리는 자기 노드의 부모 노드에 붙여주면 된다. 

 

 

 

 

• 세 번째 경우 : 삭제하려는 노드가 두개의 서브트리를 가지고 있는 경우

서브트리에 있는 어떤 노드를 삭제 노드 위치로 가져올 것이냐가 문제이다. 당연히 서브트리를 가지고 있는데 그냥 가져와서 붙히면 안된다. 삭제되는 노드와 가장 값이 비슷한 노드를 후계자로 선택하여야 다른 노드를 움직이지 않아도 이진 탐색 트리가 그대로 유지된다. 

 

그렇다면 가장 값이 가까운 노드는 어디에 있을까? 

왼쪽서브트리에서 가장 큰 값이나 오른쪽 서브트리에서 가장 작은 값이 삭제되는 노드와 가장 가깝다는 것을 쉽게 알 수 있다. 왼쪽 서브트리에서 가장 큰 값은 왼쪽 서브트리의 가장 오른쪽에 있는 노드이며 오른쪽 서브트리에서 가장 적은 값은 오른쪽 서브트리의 가장 왼쪽에 있는 노드가 된다.

 

 

 

 

 

C언어로 예전에 공부 했을 때도 세 번째 경우가 구현하기가 좀 까다로웠다. 이제는 JAVA로 공부중 이니 JAVA로 구현해봐야겠다.

public boolean deleteBST(int x){
        //현재 위치로부터의 루트 노드
        TreeNode parent = root;
        TreeNode current = root;
 
        boolean isLeftChild = false;
        while(current.data != x){
            parent = current;
            if(current.data > x){
                isLeftChild = true;
                current = current.left;
            }
            else if(current.data < x){
                isLeftChild = false;
                current = current.right;
            }
            if(current == null){
                System.out.println("트리가 존재하지 않습니다");
                return false;
            }
        }
        //여기까지 while이 돌고나면 x의 위치 찾음
 
        // 1. 자식노드가 없는 경우(단말노드)
 
        if(current.left == null && current.right == null){
            if(current == root){   // 트리 전체에서 노드가 루트 하나인 경우
                root = null;
            }
            //단말 노드와 연결을 끊음
            if(isLeftChild){
                parent.left = null;
            }
            else{
                parent.right = null;
            }
        }
        // 2. 하나의 자식을 갖는 경우
        //왼쪽 자식을 갖는 경우
        else if(current.right == null){
            if(current == root){
                root = current.left;
            }
            else if(isLeftChild){
                parent.left = current.left;
            }
            else{
                parent.right = current.left;
            }
        }
        //오른쪽 자식을 갖는 경우
        else if(current.left == null){
            if(current == root){
                root = current.right;
            }
            else if(isLeftChild){  //루트 노드를 기준으로 왼쪽으로 갔을 때
                parent.left = current.right;
            }
            else{  //루트 노드를 기준으로 오른쪽으로 갔을 때
                parent.right = current.right;
            }
        }
        //3. 두개의 자식을 갖는 경우
        else if(current.left != null && current.right != null){
            TreeNode suc = getSuc(current);
            if(current == root){
                root = suc;   //삭제 할 노드가 root 라면 root 자리에 current 놓기
            }
            else if(isLeftChild){  //삭제 할 노드의 위치가 루트를 기준으로 왼쪽이라면
                parent.left = suc; //자기 자리에 suc 을 대입
            }
            else{
                parent.right = suc;
            }
            suc.left = current.left;  // current 는 삭제할 노드
            //suc 은 삭제할 노드의 위치를 대체 할 노드
            //삭제할 노드의 왼쪽 서브트리를 새로운 대체 노드의 왼쪽 서브트리로 만듬
            //대체 노드를 삭제 노드 기준으로 오른쪽 서브트리 중에 가장 작은 것을 선택했기 때문
        }
        return true;  //위에서 존재하지 않으면 return false 문이 있기 때문에 삭제를 성공하면 return true
    }
 
    public TreeNode getSuc(TreeNode deleteNode){
        TreeNode suc = null;
        TreeNode sucparent = null;
        TreeNode current = deleteNode.right;
 
        //오른쪽 서브트리에서 가장 작은 값을 찾는 과정
        while(current != null){
            sucparent = suc;
            suc = current;
            current = current.left;
        }
 
        if(suc != deleteNode.right){
            sucparent.left = suc.right;
            suc.right = deleteNode.right;
        }
        return suc;  // 삭제 할 노드 위치에 올 노드를 반환
    }
 
 
 

 

역시 이진탐색트리에서 삭제연산을 구현하는 것은 진짜 어렵다..  코드를 읽는 것도 나에게 아직 버겁지만, 계속 익히면서 숙달해야겠다. 

 

 

 

이진 탐색 트리의 분석

이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을 때 O(h)가 된다. 따라서 n개의 노드를 가지는 이진 탐색 트리의 경우, 일반적인 이진 트리의 높이는 [log2n]이므로 이진 탐색 트리 연산의 평균적인 경우의 시간 복잡도는 O(log2h)이다. 

 

그러나 이는 좌우의 서브 트리가 균형을 이룰 경우이고 최악의 경우에는 한쪽으로 치우치는 경사 트리가 되어서 트리의 높이가 n이 된다. 이 경우에는 탐색, 삭제, 삽입시간이 거의 선형 탐색와 같이 O(n)이 된다.