BST : Binary Search Tree(이진 검색 트리)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다.

BST : Binary Search Tree(이진 검색 트리)

- Dynamic Set 

- 여러개의 Key(키)를 저장

- 다음과 같은 연산들을 지원하는 자료구조

Insert : 새로운 키의 삽입

Search : 키 탐색

Delete : 키의 삭제 

다양한 방법들

- 정렬된 혹은 정렬되지 않은 배열 혹은 연결리스트를 사용할 경우

Insert, Search, Delete 중 적어도 하나는 O(n)

- 이진 탐색 트리, 레드-블랙 트리, AVL-트리 등의 트리에 기반한 구조들(이진 트리의 확장형들)

- Direct Address Table, 해쉬 테이블 등

속성

- 각 노드에 값이 있다.

- 각 노드들의 키 값은 모두 달라야 한다.

- 값들은 전순서가 있다.

- 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.

- 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.

- 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.

- 중복된 노드가 없어야 한다.

최소값

- 최소값은 항상 가장 왼쪽 노드에 존재

TREE-MINIMUN(x){
	while left[x] != NIL
		do x <- left[x]
	return x
}

최대값

- 최대값은 항상 가장 오른쪽 노드에 존재

Tree-MAXIMUM(x){
	while right[x] != NIL
		do x <- right[x]
	return x
}

Successor

- 노드 x의 Successor란 key[x]보다 크면서 가장 작은 키를 가진 노드

- 모든 키들이 서로 다르다고 가정

- 3가지 경우

1. 노드 x의 오른쪽 부트리가 존재할 경우, 오른쪽 부트리의 최소값

2. 오른쪽 부트리가 없는 경우, 어떤 노드 y의 왼쪽 부트리의 최대값이 x가 되는 그런 노드 y가 x의 Successor

부모를 따라 루트까지 올라가면서 처음으로 누군가의 왼쪽 자식이 되는 노드

3. 그런 노드 y가 존재하지 않을 경우 Successor가 존재하지 않음(즉, x가 최대값)

- Successor <-> Predecessor

Successor : 나보다 크면서 가장 작은 노드

Predecessor : 나보다 작으면서 가장 큰 노드

노드 x의 Predecessor란 key[x]보다 작으면서 가장 큰 키를 가진 노드, Successor과 반대의 의미

TREE-SUCCESSOR(x){
	if right[x] != NIL
		then return TREE-MINIMUM(right[x])
	y <- p[x]
	while y != NIL and x = right[y]
		do x <- y
		   y <- p[x]
		return y
}

Search

TREE-SEARCH(x, k){
	if x = NIL or k = key[x]
		then return x
	if k < key[x]
		then return TREE-SEARCH(left[x], k)
		else return TREE-SEARCH(right[x], k)
}

반복문으로 변경

INERATIVE-TREE-SEARCH(x, k){
	while x != NIL and k != key[x]
		do if k < key[x]
			then x <- left[x]
			else x <- right[x]
		return x
}

Insert

TREE-INSERT(T, z){	// T : Tree, z : insert할 노드
	y <- NIL
	x <- root[T]
	while x != NIL
		do y <- x
			if key[z] < key[x]
				then x <- left[x]
				else x <- right[x]
	p[z] <- y
	if y = NIL
		then root[T] <- z
	else if key[z] < key[y]
		then left[y] <- z
		else right[y] <- z
}

Delete

TREE-DELETE(T, z){	// T : tree, z : 삭제할 노드
	if left[z] = NIL or right[z] = NIL
		then y <- z
		else y <- TREE-SUCCESSOR(z)
	if left[y] != NIL
		then x <- left[y]
		else x <- right[y]
	if x != NIL
		then p[x] <- p[y]
	if p[y] = NIL
		then root[T] <- x
		else if y = left[p[y]]
			then left[p[y]] <- x
			else right[p[y]] <- x
	if y != z
		then key[z] <- key[y]
			copy y's satellite data into z
	return y
}

소스 코드(Java)