Binary Search Tree

개념

• Binary Tree를 활용한 탐색
• 일정하게 정렬된 상태를 유지해 탐색에 효율적인 구조를 가짐
• 기존 Binary Tree와 동일하게 Traversal 등의 기능을 가지지만 추가적으로 Insertion, Deletion, Search 기능이 추가됨

조건

1. 모든 노드는 유일한 Key값을 가짐
2. 왼쪽 Subtree에 있는 값은 root에 있는 값보다 작음
3. 오른쪽 Subtree에 있는 값은 root에 있는 값보다 큼
4. 왼쪽, 오른쪽 Subtree 모두 Binary Search Tree임
   (=앞선 조건을 만족함)

성능 분석

• Search와 Insertion 그리고 Deletion 모두 tree의 높이 h에 따라 결정되며 O(h)의 시간 복잡도를 가짐
• 일반적으로 균형잡힌 tree일 경우 h는 log₂n (n: 노드의 개수)
• 극단적으로 편향된 tree일 경우 h = n

관계형 데이터베이스의 구성

Field

• 데이터 베이스의 저장하는 가장 작은 단위
• 일반적으로 하나의 속성 값만을 저장

Record

• 다수의 Field로 이루어진 데이터의 단위
• 데이터 베이스의 행

Table

• 같은 형태를 가진 Record의 집합
• 전체 데이터베이스의 표

Key

• Record를 구분하거나 정렬, 검색하기 위한 Field
• 빨리 원하는 값을 찾는 것을 도움
  Ex) 전체 학생 목록에서 학번은 특정 학생을 찾는 것을 도움

Primary Key

• 여러 Key들 중에서 전체 Record 중에서 중복되지 않는 것
• 반드시 중복되지 않아야하며 null 값을 가지지 않음

Search Operation

• 특정 Key값을 가진 노드를 찾기 위해 root에서부터 값을 비교하며 탐색
• 정렬된 구조가 아닐 경우 특정 값을 찾을 때 O(n)의 시간 복잡도 발생
• Recursive한 방법과 Iterative한 방법 모두를 활용해 구현 가능
• tree에 해당 기능을 구현할 수도 있고, node에서 구현할 수도 있음

탐색 과정

1. 현재 root와 찾고자 하는 값이 같다면 성공적으로 값을 찾은 것으로 간주
2. 찾고자하는 값이 현재 root보다 작다면, 왼쪽 Subtree를 탐색
3. 찾고자하는 값이 현재 root보다 크다면, 오른쪽 Subtree를 탐색
   (leaf노드에 이를 때까지 1~3번 과정을 반복)

	BinaryNode* searchRecur( BinaryNode *n, int key ) {
		if( n == NULL ) return NULL;			// n is NULL

		if( key == n->getData() )				// (1) key == n->data
			return n;
		else if (key < n->getData() )			// (2) key < n->data
			return searchRecur( n->getLeft(), key );
		else 									// (3) key > n->data
			return searchRecur( n->getRight(), key );
	}

	BinaryNode* searchIter( BinaryNode *n, int key ) {
		while( n != NULL ) {
			if( key == n->getData() ) return n;
			else if (key < n->getData() ) 
            	n = n->getLeft();
			else n = n->getRight();
		}
		return NULL;
	}

Insert Operation

• Insertion을 위해서는 먼저 Search를 통해 삽입될 위치를 파악해야함
• Binary Search Tree에는 중복되는 key값은 존재할 수 없으므로 이미 존재하는 값은 추가될 수 없음
• Search에서 탐색을 실패한 지점이 새로운 노드를 추가할 지점
• 같은 값이어도 삽입 순서에 따라 Tree의 구조가 달라질 수 있음

구현

	void insertRecur( BinaryNode* r, BinaryNode* n ) {
		if( n->getData() == r->getData() ) 
			return;
		else if( n->getData() < r->getData() ) {
			if( r->getLeft() == NULL )
				r->setLeft(n);
			else
				insertRecur( r->getLeft(), n );
		}
		else {
			if( r->getRight() == NULL )
				r->setRight(n);
			else
				insertRecur( r->getRight(), n );
		}
	}

• 추가하려는 값과 현재 노드의 값을 비교해 값이 더 작을 경우 왼쪽 Subtree를 확인하고, 그때 해당 위치가 비어있다면 노드를 추가, 비어있지 않다면 Search를 이어서 수행
  (값이 더 클 경우에는 오른쪽 Subtree에 대해 같은 작업을 수행)

Deletion Operation

• Binary Search Tree에서 가장 복잡한 작업
• 삭제될 노드가 어떤 노드인지 파악해야함

삭제될 노드의 경우의 수

1. leaf 노드인 경우
2. 해당 노드가 왼쪽 또는 오른쪽 Subtree만 가지는 경우
3. 해당 노드가 왼쪽과 오른쪽 Subtree를 모두 가지는 경우

1. leaf 노드인 경우

• 삭제할 노드의 부모노드를 찾아 삭제할 노드로의 연결을 끊음
  (삭제를 위해서는 삭제할 노드와 해당 노드의 부모노드까지 알아야함)

2. 하나의 Subtree만 가지는 경우

• 삭제할 노드의 부모 노드에 해당 Subtree를 연결
  (삭제할 노드, 부모 노드 그리고 추가로 자식 노드까지 알아야함)

3. 양쪽 Subtree를 가지는 경우

• 삭제할 노드를 양쪽 Subtree 중 하나의 값으로 교체

가능한 옵션

1. 왼쪽 Subtree의 가장 큰 값으로 교체하기
2. 오른쪽 Subtree의 가장 작은 값으로 교체하기

구현

	void remove(BinaryNode *parent, BinaryNode *node) {

		// case 1
		if( node->isLeaf() ) {
			if( parent == NULL ) root = NULL;
			else {
				if( parent->getLeft() == node )
					parent->setLeft(NULL);
				else
					parent->setRight(NULL);
			}
		}
		// case 2
		else if( node->getLeft()== NULL|| node->getRight()==NULL ) {
			BinaryNode *child = (node->getLeft() != NULL )
								? node->getLeft()
								: node->getRight();
			if( node == root )
				root = child;
			else {
				if( parent->getLeft() == node )
					parent->setLeft(child); 
				else 
					parent->setRight(child); 
			}
		}
		// case 3
		else {
			BinaryNode* succp = node;
			BinaryNode* succ = node->getRight();
			while (succ->getLeft() != NULL) {
				succp = succ;
				succ = succ->getLeft();
			}

			if( succp->getLeft() == succ )
				succp->setLeft(succ->getRight());
			else
				succp->setRight(succ->getRight());

			node->setData(succ->getData());

			node = succ;
		}
		delete node;
	}

• 해당 코드는 3번 경우에서 오른쪽 Subtree의 가장 작은 값을 사용
• 삭제할 노드뿐만 아니라 부모, 자식노드 등 전반에 대한 파악이 필요하므로 Tree에서 기능 구현

		// case 3
		else {
			BinaryNode* succp = node;
			BinaryNode* succ = node->getLeft();
			while (succ->getRight() != NULL) {
				succp = succ;
				succ = succ->getRight();
			}

			...

• 왼쪽 Subtree의 가장 큰 값을 찾도록 변경할 수 있음
• 지속적으로 오른쪽 Subtree를 탐색하는 이유는 오른쪽에 root보다 큰 값이 저장되기 때문