이진탐색트리(Binary Search Tree, BST)

이진탐색트리란?

이진탐색트리(Binary Search Tree, BST)는 이진 트리의 일종으로 데이터를 효율적으로 저장, 검색, 삽입 및 삭제할 수 있도록 설계된 자료구조이다. 이진탐색트리는 다음과 같은 특징을 가지고 있다.

• 각 노드가 최대 두개의 자식 노드를 가지고 있다.
• 왼쪽 서브트리의 모든 노드의 값은 루트 노드의 값보다 작다.
• 오른쪽 서브트리의 모든 노드의 값은 루트 노드의 값보다 크다.
• 중복 요소는 허용하지 않는다.
• 왼쪽 및 오른쪽 서브트리도 각각 이진탐색트리여야 한다.

 

 

이진탐색트리의 연산

탐색 (Search)

1. root 노드부터 탐색 시작
2. 현재 위치의 값과 비교하여 찾고자 하는 key 가 작으면 왼쪽 서브트리로, 오른쪽 서브트리로 재귀.
3. 일치하는 값을 찾을 때까지 절차 반복.
4. 리프노드에 도달할 때 까지 검색 값이 없으면 Null을 반환

 

 

탐색 연산 Java로 구현

public TreeNode search(TreeNode root, int key) {
    if (root == null || root.value == key) { // 리프노드에 도달했거나, 값을 찾으면 root 반환
        return root;
    }
    if (key < root.value) { // key가 현재 노드 값보다 작으면 왼쪽 재귀
        return search(root.left, key);
    } else { // key가 현재 노드 값보다 크면 오른쪽 재귀
        return search(root.right, key);
    }
}

 

 

삽입 (Insert)

1. root 노드부터 탐색 시작
2. 삽입 값을 현재 노드 값과 비교.
   현재 값보다 작으면 왼쪽으로 재귀, 크면 오른쪽으로 재귀
3. 리프노드에 도달한 후 노드보다 작으면 왼쪽에, 크다면 오른쪽에 삽입.

 

 

삽입 연산 Java로 구현

public TreeNode insert(TreeNode root, int key) {
    if (root == null) { // 리프노드 도달 후 위치에 node 객체 새로 만들어 연결
        return new TreeNode(key);
    }
    if (key < root.value) { // 현재 노드 값보다 key값이 작으면 왼쪽으로 재귀
        root.left = insert(root.left, key);
    } else if (key > root.value) { // 현재 노드 값보다 key값이 크면 오른쪽으로 재귀
        root.right = insert(root.right, key);
    }
    return root;
}

 

 

 

삭제 (Delete)

삭제 연산은 삭제할 노드가 자식 노드를 가지는 경우를 고려해야한다.

• 자식 노드가 없는 경우
  단순히 삭제시킨다.

 

• 자식 노드가 하나만 있는 경우
  삭제할 노드의 자식을 부모 노드와 연결해줘야 한다

 

• 자식 노드가 두개 있는 경우
  삭제할 노드를 오른쪽 서브트리의 최소값으로 변경해주고, 해당 위치의 값을 삭제한다.
  
  1. 삭제 노드를 찾는다.
  2. 해당 노드의 오른쪽 서브트리의 최소값을 찾는다. (이를 successor 노드라고 한다.)
  3. 삭제 노드의 값을 successor 노드의 값으로 변경한다.
  4. successor 노드를 삭제한다.

 

 

삭제 연산 Java로 구현

public TreeNode delete(TreeNode root, int key) {
    if (root == null) {
        return root;
    }
    // 삭제할 값을 찾을 때 까지 key값과 현재 노드 값을 비교하며 재귀
    if (key < root.value) { 
        root.left = delete(root.left, key);
    } else if (key > root.value) {
        root.right = delete(root.right, key);
    } else {  // 노드를 찾았을 때
        if (root.left == null) {
            return root.right;
        } else if (root.right == null) {
            return root.left;
        }
        // 두 자식을 모두 가진 경우
        root.value = minValue(root.right); // 오른쪽 서브트리 최소값을 찾아서 현재 노드 값에 대입
        root.right = delete(root.right, root.value); // 오른쪽 서브트리에서 현재 노드 값과 같은 값을 삭제
    }
    return root;
}

// 노드의 최소 값 찾기
private int minValue(TreeNode root) {
    int minValue = root.value;
    while (root.left != null) {
        root = root.left;
        minValue = root.value;
    }
    return minValue;
}

 

 

 

이진탐색트리의 시간복잡도

• 최적 및 평균: O(log n)
     트리의 높이에 비례.
• 최악: O(n)
     한쪽으로 치우친 경우, 즉, 선형 구조가 될 때.