[자료구조] 이진 탐색 트리(Binary Search Tree) : 균형과 성능의 조화

이진 탐색 트리를 공부하기 앞서, 탐색 트리란 무엇인가?

 

이는 저장된 데이터에 대해 접근, 탐색, 삽입, 삭제, 갱신 등의 연산을 수행할 수 있는 자료구조를 말한다.

 

탐색 트리의 종류는 굉장히 다양하지만, 제일 기본이고 선행되어 학습되어야 하는 부분이 바로 이진 탐색 트리이다.

(그 외에 AVL트리, 2-3 트리, 2-3-4 트리, B-트리, RB-트리 등은 다른 포스팅을 참고하자)

 

 

---

 

이진 탐색 트리

 

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

이진 탐색의 개념을 트리 형태의 구조에 접목한 자료구조를 말한다.

 

🤔 그렇다면 이진 탐색이란?

정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어 가며 특정 항목을 찾는 탐색 방법이다.

 

다시말해 이진 탐색 트리란, 트리 형태의 구조에서 데이터를 두 부분으로 나누고 비교하며 특정 항목을 찾는 자료구조라고 생각해 볼 수 있다.

 

 

 

이진 탐색 트리의 특징

 

이진 탐색 트리에서 각 노드를 n이라고 했을 때,

 

각 노드 n의 키는 n의 왼쪽 서브 트리에 있는 키보다 크고 n의 오른쪽 서브트리에 있는 키보다 작다.

 

즉, 노드 자신의 왼쪽 자식의 키는 자신의 키보다 작고, 노드 자신의 오른쪽 자식의 키는 자신의 키보다 크다는 것이다.

 

이러한 구조 때문에 중위 순회(왼쪽, 자신, 오른쪽 순서로 방문)를 시행하면, 정렬된 상태로 출력된다는 특징이 있다.

 

 

---

 

이진 탐색 트리의 탐색 연산

 

탐색 연산은 아래와 같은 과정을 따른다.

 

1. 탐색하는 Key가 k라면, 루트의 id와 k를 비교한다.

 

 

2. k가 id보다 작으면, 루트의 왼쪽 서브트리에서 k를 찾고, k가 id보다 크다면 루트의 오른쪽 서브트리에서 k를 찾으며,

id가 k와 같으면, 탐색에 성공한 것이므로 노드의 Value를 반환한다.

 

 

3. 각 서브트리(왼쪽, 오른쪽)에서 k를 탐색하는 연산은 루트에서 탐색하는 과정과 동일하므로 탐색에 성공할 때까지 2. 의 과정을 반복해 준다.

 

 

다음은 탐색연산을 구현한 코드이다.

 

// 루트로 부터 탐색 시작
public Value get(Key k) { return get(root, k);}
public Value get(Node n, Key k) {

	// n이 만약 없는 노드라면 null 리턴
	if (n == null) return null;
    // 키 비교
    int t = n.getKey().compareTo(k);
   
    if (t > 0) return get(n.getLeft(), k);
    else if (t < 0) return get(n.getRight(), k);
    
    // 키가 같다면 탐색에 성공한 것이므로, Value리턴(Value 타입 캐스팅)
    else return (Value) n.getValue();
 }

 

 

---

 

 

이진 탐색 트리의 삽입 연산

 

삽입은 탐색 연산과 유사하다.

 

탐색 연산은 마지막에 null을 반환하지만, 삽입 연산은 여기에 삽입하려는 값을 가진 새 노드를 생성하고 새 노드를 부모와 연결시킨다.

 

이때, 이미 id가 트리에 있으면 name만 갱신한다.

 

다음은 삽입 연산 코드 구현이다.

 

public void put(Key k, Value v) { root = put(root, k, v);}
public Node put(Node n, Key k, Value v) {

	// 삽입 위치에 도달
	if (n == null) return new Node(k, v);
    
    // 키를 비교하며 위치를 찾음
    int t = n.getKey().compareTo(k);
    
    // 위치를 찾아가며, setLeft, setRight함수를 통해 부모 노드와 연결 시킴
    if (t > 0) n.setLeft(put(n.getLeft(), k, v));
    else if (t < 0) n.setRight(put(n.getRight(), k, v));
    
    // 만약 같은 키 값을 가진 노드가 있다면 Value만 갱신
    else n.setValue(v); 
    return n;
}

 

 

 

---

 

최솟값 찾기 및 최솟값 삭제 연산

 

이진 탐색 트리에서 최솟값은 어떻게 찾고 또 어떻게 삭제해야 하는지 알아야 하는 이유는,

 

이진 탐색 트리의 삭제 연산이 이 최솟값 삭제 연산을 이용하기 때문이다.

 

 

🤔 최솟값 찾기란?

루트로부터 왼쪽 자식을 따라 내려가며, null을 만났을 때 null의 부모가 가진 id이다.

 

public Key min() {
	// root가 null이면 null을 리턴
	if (root = null) return null;
    
    // Key값으로 타입 캐스팅, root로 부터 탐색 시작
    return (Key) min(root).getKey();
}

private Node min(Node n) {

	// 왼쪽 자식이 null일때까지 재귀적으로 탐색
	if (n.getLeft() == null) return n;
    return min(n.getLeft());
}

 

 

왼쪽 자식이 null일때까지 찾아감

 

 

---

 

최솟값 삭제 연산

 

최솟값을 가진 노드 x를 찾아낸 뒤,  x의 부모 p와 x의 오른쪽 자식 c를 연결한다.

 

public void deleteMin() {
	// 트리가 빈 경우 처리를 해준다.
	if (root = null) System.out.println("empty 트리");
 	root = deleteMin(root);
}

public Node deleteMin(Node n) {
	// n이 최솟값이라는 것을 발견
    // 왼쪽 노드로 탐색하며 내려오다가 n.getLeft()가 null이 되기 때문
    // n의 오른쪽 자식 값이 n의 자리를 대체
	if (n.getLeft() == null) return n.getRight();
    
    // n의 왼쪽 자식으로 순환 호출
    n.setLeft(deleteMin(n.getLeft()));
    return n;
}

 

 

 

최솟값이 삭제되는 과정

 

최솟값이 삭제되는 코드를 그림으로 구상해 보자.

 

그림에서 우리가 원하는 것은 결국 10이 삭제되는 결과일 것이다.

이를 위해 최솟값을 발견해야 하고, 이는 위 코드 중 deleteMin 메서드가 순환 호출되는 과정에서 이루어진다.

 

만약 n노드가 최소라는 것을 발견한다면, 최솟값 삭제를 위해 n의 오른쪽 노드를 반환해야 한다.

그 이유는 왼쪽 노드는 어차피 null 값일 것이고, 중요한 것은 n을 삭제하는 것이기 때문에 오른쪽 값이 null이라고 하더라도 삭제엔 문제가 없기 때문이다.

 

마지막으로 연쇄적으로 부모와 자식의 관계를 재설정하기 위해 순환 호출 함수를 n.setLeft()로 감싸준다.

 

 

---

 

이진 탐색 트리의 삭제 연산

어찌 되었든, 이 모든 것은 삭제 연산을 구현하기 위함이다.

 

삭제에 있어서 필연적으로 지켜져야 하는 것은 이진 탐색 트리의 조건을 만족시키는 것이다.

그렇기 때문에 삭제된 노드의 부모와 자식 간의 관계를 연결시켜 주는 것이 중요하다.

 

 

삭제는 총 3가지 경우의 수를 생각해 볼 수 있다.

 

첫 번째는 삭제되는 노드가 자식이 없는 경우,

두 번째는 자식이 하나인 경우,

세 번째는 자식이 둘인 경우이다.

 

각 경우는 순서대로 다음과 같은 과정을 통해 처리할 수 있다.

 

1. 삭제될 노드 x의 부모가 x를 가리키던 레퍼런스를 null로 만든다.

• 삭제하려는 노드의 부모와 자식 관계만 처리하면 된다. 삭제 노드의 자식이 없기 때문이다.

2. x가 한쪽 자식인 c만 가지고 있으면, x의 부모와 x의 자식 c를 직접 연결한다.

 

3. x의 자리에 중위 순회하면서 x를 방문하기 직전 노드(중위 선행자) 또는 직후에 방문되는 노드(중위 후속자)를 이동한다.

 

 

1, 2의 경우는 생각해 보기 쉬우나, 3의 경우는 다소 까다로워 보인다.

 

코드를 통해 이해해 보자.

 

public void delete(Key k) { root = delete(root, k); }

public Node delete(Node n, Key k) {
	
	if (n == null) return null;
    
    // 키를 비교하며 삭제 대상이 되는 노드에 접근
    int t = n.getKey().compareTo(k);
    // setLeft와 setRight는 부모 자식 연결 관계를 재설정하는 부분!

    if (t > 0) n.setLeft(delete(n.getLeft(), k));
    else if (t < 0) n.setRight(delete(n.getRight(), k));
    
    // 만약 삭제 대상이 되는 노드를 발견했을 경우
    else {
    
    	// 삭제 노드의 자식 리턴 -> 이로써 삭제 노드가 제외됨
    	if (n.getRight() == null) return n.getLeft(); // 이 경우는 1과 2의 경우 모두 해당
        
        // 이 경우는 2의 경우만 해당
        // n의 오른쪽 자식은 있기 때문에 연결해줄 수 있다.(위에 조건에 의함)
        if (n.getLeft() == null) return n.getRight(); 
        
        // 3의 경우에 해당 -> 위 두 조건을 모두 통과했기 때문이다.
        // target = 삭제할 노드
        Node target = n;
        
        // 삭제할 노드와 교환할 하위 자식 노드를 찾아야 한다.
        // 그렇게 하기 위해 삭제할 노드의 오른쪽 서브트리 내에서 최솟값을 찾는다.
        // 그 최솟값을 n에 할당해 준다. -> 즉, n이 새롭게 구성
        n = min(target.getRight());
        
        // 새로이 할당된 n의 왼쪽 자식과 오른쪽 자식을 새롭게 할당해준다.
        // 이때, 오른쪽 자식 설정 시, 삭제 노드 대신 들어간 노드를 제거하여 재구성
        // 오른쪽 서브트리에서 결국 삭제 노드 대신 들어갔기 때문에 반영해주어야 한다.
        n.setRight(deleteMin(target.getRight()));
        
        // 왼쪽은 그대로 설정
        n.setLeft(target.getLeft());
    }
    return n;
}

 

 

결국  3의 경우는 삭제 노드 자신을 대체할 노드를 오른쪽 서브트리 내에서 찾아 바꾸어 주는 것이 전부이다.

 

 

 

---

이진 탐색 트리의 수행 시간

 

이진 탐색 트리에서 각 연산의 수행 시간은 트리의 높이에 비례한다. : O(h)

 

각 연산은 루트에서 탐색을 시작하여 최악의 경우 이파리까지 내려가고, 삽입과 삭제 연산은 다시 루트까지 거슬러 올라가기 때문이다.

 

트리를 1층 내려갈 때는 순한 호출이 발생하고 1층을 올라갈 때는 setLeft() 혹은 setRight() 메서드를 수행한다. 이는 각각의 O(1)의 시간이 소요된다.

 

 

🤔 그렇다면 n개의 노드가 있는 이진 탐색 트리의 경우, 가장 시간 복잡도가 큰 경우는 무엇인가?

 

바로 편향 이진트리라고 한다. 즉, 한쪽으로만 트리가 치우 처져 있는 형태인 것이다.

 

반대로 완전 이진트리의 형태일 때 가장 시간 복잡도가 작다고 말할 수 있다.

 

 

 

🤔 Empty 이진 탐색 트리에 랜덤 키 n개를 삽입하면 트리의 높이는 어떻게 되는가?

: 약 1.39 logn