[알고리즘] Binary Search Tree

사실 더 많은 종류의 트리를 배웠다. 이진 탐색 트리 뿐만 아니라 레드-블랙 트리, B-트리, 뭐 다차원 트리 등등...

다 정리하기에는 조금,, 애초에 레드-블랙 트리 같은 것을 실생활에서 쓸 일이 있을까 싶기도 하고, 가장 일반적인 바이너리 트리를 정리해 보려고 한다.

오늘은 기분이 참 별로다.

 

Binary Search Tree란...

- 각 노드가 최대 두개의 자식을 가진다.

- 각 노드는 record를 unique하게 대표하는 field를 key로 가지고 있다.

- 각 노드는 자신과 다른 노드들의 key의 대소관계에 따라 왼쪽 혹은 오른쪽 subtree를 구성한다.

https://en.wikipedia.org/wiki/Binary_tree

1. 검색

 재귀적으로 하면 된다. root노드부터 시작해서 key값을 비교해 가며 key값이 찾고자 하는 값보다 큰 경우 오른쪽 서브트리, 작은 경우 왼쪽 서브트리로 내려가는 과정을 반복한다.

 

2. 삽입

 먼저 검색을 하고, 검색 과정에서 NIL노드를 만나면 겹치는 key를 가진 노드가 없다는 뜻이므로 그 자리에 insert한다.

 

3. 삭제

 1) 삭제할 노드가 리프노드인 경우 : 그냥 삭제하면 된다.

 2) 삭제할 노드가 하나의 자식을 가지는 경우 : 그 자식(그자식!!)을 삭제할 노드의 부모노드에 붙인다.

 3) 삭제할 노드가 두개의 자식을 가지는 경우 : 왼쪽 서브트리의 가장 오른쪽 값 혹은 오른쪽 서브트리의 가장 왼쪽 값으로 삭제할 노드를 대체한다.

 

그림도 생략, 알고리즘도 생략... 쓸 게 별로 없네. 그렇다고 레드블랙 트리를 쓰기는 너무 양이 많아서 이만..