CH06 : Dynamic Sets and Searching 2 - Binary Search Tree

Intro

Dynamic Set과 Binary Search Tree

 Dynamic set은 1. 크기가 동적으로 변화하면서, 2. 삽입/삭제/탐색 연산을 지원해야 한다. BST는 dynamic set 중 하나이다. 한편, 일반적인 tree는 1 조건은 만족하나, 2 조건은 만족하지 않으므로 dynamic set이라 하기 어렵다. 

Binary Search / Binary Tree / Binary Search Tree

 셋은 전부 다른 것! 뒷단어에 유의해 보도록 한다.

• binary search : 이진 '탐색' 알고리즘
• binary tree : 이진 '트리' 자료구조
• binary search tree : 이진 '탐색' 조건을 만족하는 '트리' 자료구조 ($\subset$ binary tree)

Binary Search Tree란 무엇인가?

 Binary Search Tree는 다음의 구조조건, 순서조건을 만족해야 한다.

• 구조조건 : binary tree의 구조여야 한다. (자식 수가 2개 이하)
• 순서조건 : 임의의 노드 v에 대하여 v의 key값은 left child key값 이상, right child key값 이하여야 한다.
  
  • v.left.key $\leq$ v.key $\leq$ v.right.key
    • 결국 v에 대하여 left subtree안 모든 노드의 key값 이상, right subtree안 모든 노드의 key값 이하의 key값을 갖는다. 
  • 구현시에는 v.left.key < v.key $\leq$ v.right.key 혹은 v.left.key $\leq$ v.key < v.right.key 중 골라야 하는데, 아래에선 전자를 기준으로 설명한다. 

 한편, BST는 다음의 특성을 가진다.

• BST에서의 inorder traversal은 key값이 오름차순으로 정렬된 list를 만든다.
  • inorder traversal(중위 순회) : 왼쪽 서브트리 방문 → 현재 노드 방문 → 오른쪽 서브트리 방문

Binary Search Tree Example

balance 정도가 다른 BST

 둘 다 20, 30, 40, 50, 60, 80 여섯 개의 노드로 이뤄진 BST이다. 이처럼 삽입방식에 따라 BST의 height가 상이할 수 있다. 왼쪽 subtree와 오른쪽 subtree의 height 차이가 작을수록 balanced하다고 한다. 

Binary Search Tree의 구현

 black dots는 empty tree를 의미한다. 즉, leaf에는 특별한 값을 저장하지 않는다. 그렇기에 leaf를 NULL로 설정할 수 있는데, NULL로 설정하면 예기치 못한 runtime error가 발생할 수 있어 보통 nil이라는 노드로 설정하고, nil 노드에 연결된 경우 NULL로 처리하는 방법을 쓴다. 

 구체적으로 얘기하자면, 

class BST {
    Node* root;
    Node* nil = new Node; //dummy node nil
}

 메모리 공간 사용을 줄이기 위해 매번 nil이라는 노드를 만들기보단, BST class에 dummy node nil을 정의하고 해당 nil에 각 leaf를 연결해주는 방식으로 구현한다. root의 parent 또한 존재하지 않으므로 nil로 연결해 준다. 

Binary Search Tree Algorithm 

Element bstSearch(BinTree bst, key K)
    Element found //key값이 K인 노드를 탐색하면 found에 저장
    if (bst == nil) //base case : leaf까지 내려가는 경우
        found = null; //탐색실패시 null
    else //recursive case
        Element root = root(bst); //root에 current node
                		//bst에는 처음 BST의 subtree가 들어감
        if (K == root.key) //K를 찾은 경우
            found = root;
        else if (K < root.key) // K<현재 key
            found = bstSearch(leftSubtree(bst), K); //더 이상 right subtree 확인x
        else //K>현재 key
            found = bstSearch(rightSubtree(bst), K); //더 이상 left subtree 확인 x
    return found;

Element root= root(bst);

 bstSearch의 동작이 binary search와 유사하게 동작함을 알 수 있다. (절반을 탐색하지 않는다는 면에서) 다만, binary search는 중앙값과 비교하여 항상 탐색범위를 절반으로 줄이지만 bstSearch는 탐색범위가 절반이 되는 것을 보장할 수 없다는 점에서 차이가 있다. (left subtree와 right subtree의 크기가 동일하다는 보장이 없기에)