[k-mooc/자료구조] 08. 이진 탐색 트리(Binary Search Tree)

 

배경: 이진 탐색과 이진 트리의 유사점

↩️ 이진 탐색
배열의 중앙값(mid)를 찾아 배열을 반으로 분할하는 과정을 재귀적으로 반복하며 key를 검색한다.

예: search(6)

[1, 3, 4, 5, 6, 7, 8, 9] 

→ mid 3: arr[0-2], arr[4-7] ⇒ mid < 6 → 오른쪽 탐색
→ mid 5: arr[4-6], arr[6-7] ⇒ mid > 6 → 왼쪽 탐색
→ 왼쪽 배열은 원소가 하나 ⇒ mid 4: mid == 6 [검색 완료]

 

이진 탐색은 배열이 2개의 부분 배열로 재귀적으로 분할된다는 점에서 이진 트리와 유사성이 존재한다.

 

• 분할 구조   

  배열	왼쪽 부분 배열	중앙	오른쪽 부분 배열
  이진 트리	왼쪽 부분 트리	부모 노드	오른쪽 부분 트리

• 재귀 구조

  배열	각 부분 배열이 또다시 분할
  이진 트리	각 부분 트리가 또다시 분할

이러한 이진 탐색 과정을 통해 만들어진 부분 배열 구조를 트리 형태로 표현한 것이 이진 탐색 트리가 된다.

 

https://taylorial.com/dstruct/bst/

 

이진 탐색 트리(Binary Search Tree)

https://www.geeksforgeeks.org/dsa/introduction-to-binary-search-tree/

✅ 조건
1. 모든 노드는 서로 다른 하나의 값(key)를 저장한다.
2. 왼쪽 부분 트리의 모든 값은 루트 노드의 값보다 작다.
3. 오른쪽 부분 트리의 모든 값은 루트 노드의 값보다 크다.
4. 왼쪽 부분 트리와 오른쪽 분 트리는 모두 이진 탐색 트리이다.

 

 

연산

생성(초기화)

이진 탐색 트리의 자료 구조는 이진 트리의 자료 구조와 같다.

typeof class node *nptr;
class node {
	data_type key;
	nptr lchild, rchild;
}

초기화는 root node를 선언하는데, 이 때 원소가 아직 없는 경우 key를 원소로 사용하지 않을 값으로 설정한다.

 

검색

이진 탐색 트리에서 원하는 원소(X)를 찾는 연산으로, 세 가지 경우를 고려한다:

1. X = key: 검색 완료
2. X < key: 왼쪽 서브 트리로 이동
3. X > key: 오른쪽 서브 트리로 이동

구현

재귀 호출을 이용한다.

void node::search(int x) {
	//X=key
	if(x == this->key) printf("찾았습니다. \\n");
	
	//X<key: 왼쪽 서브 트리로 
	else if(x < this->key) {
		if(this->lchild == NULL) printf("찾지 못했습니다. \\n");
		else this->lchild->search(x); //왼쪽 서브 트리에서 재검색
	}
	
	//X>key: 오른쪽 서브 트리로 
	else {
		if(this->rchild == NULL) printf("찾지 못했습니다. \\n");
		else this->rchild->search(x); //오른쪽 서브 트리에서 재검색
	}
}

 

n개의 노드를 가진 이진 탐색 트리의 검색 시간 복잡도

https://www.researchgate.net/figure/a-An-example-of-unbalanced-binary-search-tree-b-A-balanced-binary-search-tree_fig1_379666610

 

최악의 경우 리프 노드에서 검색된다.

(a) 최악의 경우(skewed) — 연결 리스트와 성능이 같음: depth는 O(n)이므로, 시간 복잡도는 O(n)이 된다.

(b) 최선의 경우(balanced): depth는 O(logn)이므로 시간 복잡도는 O(logn)이 된다.

• 🤔 왜 depth가 O(logn)이냐면…
  이진 트리의 depth가 k일 때, 트리의 최대 노드 개수는 2^k - 1이 된다.
  그럼 2^k - 1 = n 이니까, 2^k = n + 1이라고 하면, log_2(n + 1) = k가 되므로 O(logn)

 

추가

이진 탐색 트리에 새로운 원소를 더하는 연산으로, 새로운 원소를 저장하는 노드를 생성하여 추가한다. 이 때 새로 추가되는 노드는 반드시 리프 노드로 추가된다.

세 가지 경우 접근을 고려한다:

1. X = key: 이진 탐색 트리의 각 노드는 서로 다른 값을 저장한다는 조건에 위배되므로 불가능
2. X < key: 왼쪽 서브 트리로 이동
3. X > key: 오른쪽 서브 트리로 이동

구현

void node::insert(int x) {
	//degenerate case: 비어있는 트리에 원소를 처음으로 추가
	if(this->key == -1) {
		this->key = x; return;
	}
	
	//x=key
	if(this->key == x) printf("중복 데이터 불가능");
	
	//x<key
	else if(this->key > x) {
		//lchild에 추가 
		if(this->lchild != NULL) this->lchild->insert(x);
		else { //lchild가 없을 경우 노드를 만들어 넣어주고, 그 노드에 대한 초기화
			this->lchild = (nptr)malloc(sizeof(node));
			this->lchild->key = x;
			this->lchild->lchild = this->lchild->rchild = NULL;
		}
	}
	//x>key
	else {
		//rchild에 추가
		if(this->rchild != NULL) this->rchild->insert(x);
		else { //rchild가 없을 경우 노드를 만들어 넣어주고, 그 노드에 대한 초기화
			this->rchild = (nptr)malloc(sizeof(node));
			this->rchild->key = x;
			this->rchild->lchild = this->rchild->rchild = NULL;
		}
	}
}

 

n개의 노드를 가진 이진 탐색 트리의 추가 시간 복잡도

새로운 노드는 항상 리프 노드로 추가된다.

(a) 최악의 경우(skewed): depth가 O(n)이므로, 시간 복잡도는 O(n)이 된다.

(b) 최선의 경우(balanced): depth가 O(logn)이므로 시간 복잡도는 O(logn)이 된다.

 

제거

이진 탐색 트리의 노드를 지우는 연산으로, 제거할 노드를 찾아가는 과정은 검색/추가와 비슷한 재귀 구조로 구현한다. 그러나 어떤 노드를 제거하느냐에 따라 다른 연산 방법이 필요하다.

1. 리프 노드 제거
2. 자식 노드 1개를 가진 노드: 노드를 제거하고 자식 노드로 대체
3. 자식 노드 2개를 가진 노드:
   노드의 값을 왼쪽 부분 트리의 최대값/오른쪽 부분 트리의 최소값으로 대체하고, 최대값/최소값에 해당하는 노드는 제거한다.

구현

int node::remove(int x) {
	//x=key
	if(x == this->key) {
		prinft("원소를 찾았습니다.");
		
		//(1)리프 노드
		if(this->lchild == NULL && this->rchild == NULL) return 1;
		
		//(2)자식 노드 1개: 오른쪽 자식 노드만 존재
		if(this->lchild == NULL && this->rchild != NULL) {
			this->key = this->rchild->key; //현재 노드값(x)을 오른쪽 자식 노드값으로 대체
			this->lchild = this->rchild->lchild; //현재 노드에 오른쪽 자식 노드의 자식 노드들 연결
			this->rchild = this->rchild->rchild; //현재 노드에 오른쪽 자식 노드의 자식 노드들 연결
			return 0;
		}
		
		//(2)자식 노드 1개: 왼쪽 자식 노드만 존재		
		if(this->lchild != NULL && this->rchild == NULL) {
			this->key = this->lchild->key; //현재 노드값(x)을 왼쪽 자식 노드값으로 대체
			this->lchild = this->lchild->lchild; //현재 노드에 왼쪽 자식 노드의 자식 노드들 연결
			this->rchild = this->lchild->rchild; //현재 노드에 왼쪽 자식 노드의 자식 노드들 연결
			return 0;
		}
		
		//(3)자식 노드 2개
		if(this->lchild != NULL && this->rchild != NULL) {
			//왼쪽 서브 트리에서 최대값을 탐색해와 그 값으로 노드값 대체 
			this->key = this->lchild->get_max(); 
			//대체한 그 노드값에 해당하는 노드는 제거 
			if(this->lchild->remove(this->key) == 1) this->lchild = NULL;
			return 0;
		}
	}
	
	//x<key
	else if(x < this->key) {
		if(this->lchild != NULL) {
			//왼쪽 자식 노드로부터 1이 리턴되면 자식 노드 제거 
			if(this->lchild->remove(x) == 1) this->lchild = NULL;
		}
		else printf("왼쪽 자식 노드가 없습니다.");
		return 0;
	}
	
	//x>key
	else {
		if(this->rchild != NULL) {
			//오른쪽 자식 노드로부터 1이 리턴되면 자식 노드 제거 
			if(this->rchild->remove(x) == 1) this->rchild = NULL;
		}
		else printf("오른쪽 자식 노드가 없습니다.");
		return 0;
	}
}

 

n개의 노드를 가진 이진 탐색 트리의 제거 시간 복잡도

최악의 경우 리프 노드에서 제거된다.

(a) 최악의 경우(skewed): depth가 O(n)이므로, 시간 복잡도는 O(n)이 된다.

(b) 최선의 경우(balanced): depth가 O(logn)이므로 시간 복잡도는 O(logn)이 된다.

 

 

✅ 이진 탐색 트리에서 최선의 성능을 기대하려면 균형을 유지해야 한다.

	추가	제거	검색	최대값 찾기	최소값 찾기
정렬된 배열	O(n)	O(n)	O(logn) - 이진 검색	O(1)	O(n)
정렬된 연결 리스트	O(n)	O(n)	O(n)	O(1)	O(1)
이진 탐색 트리	최선: O(logn) 최악: O(n)	최선: O(logn) 최악: O(n)	최선: O(logn) 최악: O(n)	최선: O(logn) 최악: O(n)	최선: O(logn) 최악: O(n)

 

균형 이진 탐색 트리(Balanced Binary Search Tree)

Self-balancing search tree, Height-balanced search tree라고도 한다.

Height를 최소로 유지하도록 설계된 이진 탐색 트리로, 가장 많이 사용되는 균형 이진 탐색 트리로는 AVL tree, Red-black tree, 2-3 tree, B+ tree가 있다.