1. Binary Search

• 어떤 Array에서 특정 데이터가 존재하는지 그렇지 않은지 찾는 경우, 0번째 index에서부터 마지막까지 비교해가면서 찾는 방법이 가장 떠올리기 쉬운 방법이다. 이 경우, O(n)의 시간이 걸린다.

• 하지만, 만약 Array가 작은 것에서부터 큰 순서대로 정렬되어있다면, 다른 방법을 생각해볼 수 있다.

  	1. Array의 정중앙에 있는 데이터를 확인한다.
  	2. 찾으려는 데이터보다 크다면, 0번 index와 (방금 확인한 index - 1)의 index의 중앙에 있는 데이터를 확인한다.
  	3. 반대로 작다면, 마지막 index와 (방금 확인한 index + 1)의 index의 중앙에 있는 데이터를 확인한다.
  	4. 같은 데이터가 나올 때까지 반복한다.

• 이상의 방법을 사용하면, Array안의 모든 데이터를 확인할 필요가 없으며 시간도 평균적으로 O(log n)으로 걸린다. 오직 크기 순으로 정렬이 되어있는 경우에만 사용할 수 있지만, 시간 효율은 매우 뛰어나다.

2. Binary Search Tree

• Binary Tree는 왼쪽, 오른쪽에 각각 자식을 가질 수 있는 tree이다. 그렇기 때문에, 부모의 왼쪽에는 항상 부모보다 작은 자식을, 오른쪽에는 큰 자식을 저장한다면, 앞서 살펴본 Binary Search 알고리즘을 적용할 수 있는 자료구조가 된다.

• BST는 보통 add, search, remove의 동작을 기본적으로 지원한다.

3. Pointer Reinforcement

• BST에 필요한 여러 동작들 중 add와 search의 경우, 단순히 반복문을 통해 원하는 데이터와 자리를 찾은 뒤 적용하면 그만이지만, 이외의 더 복잡한 동작들은 자리를 찾아 실행하는 것으로 끝나지 않고, 추가로 처리해야할 부분이 있다. 예를 들어, remove의 경우, 자식이 0/1/2일 경우 처리해줘야할 부분들이 각각 다르다.

• 그래서 BST를 구현함에 있어서 편의성을 올릴 수 있는 방법이 recursion stack을 이용한 pointer reinforcement를 사용하는 것이다.

• BST의 node들은 데이터와 자식 node들을 가리키는 pointer를 저장하고 있다. Pointer reinforcement는 이러한 pointer를 recursion을 이용하여 새로 지정해주는 것이다. 다음은 add의 pseudo code이다.

public add(data):
	root = rAdd(root, data) //최초의 stack
    
private Node rAdd(Node curr, data)
	if curr == null:
    	size + 1
        return new Node(data) // 최후의 stack
    else if data < curr.data:
    	left = rAdd(curr.left, data)
    else if data > curr.data:
    	right = rAdd(curr.right, data)
        
    return curr

• add를 실행하면, root부터 데이터의 자리까지 탐색함과 동시에 stack에 탐색 도중에 지나치는 node의 pointer를 재지정하는 코드가 쌓인다. 그리고 탐색이 종료되면, 더하려는 데이터가 들어있는 node가 생성되어 그 이전 부모의 pointer에 더해진다. 그리고 더해진 부모는 그 이전 부모의 pointer가 가리킨다. 이렇게 최종적으로 root의 pointer가 데이터가 더해진 것으로 바뀌면서 종료된다.

• 요약하면, 동작을 실행할 때마다 탐색과정에서 마주치는 모든 node의 pointer를 덮어써준다고 보면 된다.

• 이러한 동작의 이점은 remove를 보면 더 명확하다. Remove동작의 경우, 자식이 없다면 해당 node를 삭제하고, 자식이 하나라면 자식 node로 대체한다. 만약 자식이 둘이라면, BST내부에서 지워야할 값과 가까운 값(다음으로 큰 값(Successor) 또는 다음으로 작은 값(Predecessor))을 정하여 대체해주어야한다.

• Pointer reinforcement를 사용하지 않는다면, 자식이 하나인 경우에는 탐색시마다 이전의 부모를 저장하고 있어야하며, 둘이라면 부모를 저장하는 것은 물론, 기존의 자식들을 따로 저장하고 새로 지정해야하는 등의 비효율이 있다.

• Pointer reinforcement를 사용한다면, 쌓여있는 stack을 차곡차곡 실행하는 것만으로도 동작이 끝나므로, 더 효율적이다. Sucessor를 이용한 Pseudo code는 다음과 같다.

public Node remove(data):
	Node dummy = new Node()
    root = rRemove(root, data, dummy)
    return dummydata
    
private Node rRemove(Node curr, data, dummy):
	if curr = null:
    	//BST에 제거할 data가 존재하지 않음. 예외처리 혹은 그에 걸맞는 처리
    else if data < curr.data:
    	left = rRemove(left, data, dummy)
    else if data > curr.data:
    	right = rRemove(right, data, dummy)
    else: // 제거할 data를 찾음
    	dummy.data = curr.data
        size - 1
        if no child:
        	return null
        else if has left child:
        	return left child
        else if has right child:
        	return right chilf
        else: // 자식 2명 사례
        	Node dummy2 = new Node()
            curr.right = removeSuccessor(curr.right, dummy2) //Successor의 탐색과 삭제를 동시에
            curr.data = dummy2.data
    return curr
    
private Node removeSuccessor(Node curr, Node dummy):
	if left == null:
    	dummy.data = curr.data
        return right
    else:
    	left = removeSuccessor(left, dummy)

• 이상의 code는 탐색 stack을 쌓다가, 데이터를 찾으면 dummy에 넣음과 동시에 pointer를 바꾸어서 데이터를 BST에서 날린다. 자식이 2명인 경우는, 대체 Node stack을 또다시 쌓다가, 대체 node를 다른 dummy에 넣어 반환하는 동시에 pointer를 바꾸어 삭제하고, 다른 dummy의 데이터를 지워야할 데이터 대신 대체한 후, 지운 Node를 dummy에 넣어 최종적으로 반환한다.

• Predecessor로 대체하고 싶다면 Successor코드에서 좌우를 바꾸어주면 동작한다.

출처: https://learning.edx.org/course/course-v1:GTx+CS1332xII+2T2020/home

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.