Binary Search Tree

Binary search tree(이진 탐색 트리)는 아래의 전제조건들이 존재하는 이진 트리다.

• 모든 노드의 값은 유일하다.
• 값들은 전순서가 있다(임의의 두 원소의 비교가 가능하다).
• 어떤 노드의 왼쪽 서브트리는 그 노드보다 작은 값을 가진 노드들로 이루어져 있다.
• 어떤 노드의 오른쪽 서브트리는 그 노드와 같거나 큰 값을 가진 노드들로 이루어져 있다.
• 좌우 서브트리는 각각이 이진 탐색 트리여야 한다.

탐색

이진 탐색 트리에서 값 x를 가진 노드를 탐색하고자 할 때, 트리에 해당 값을 가진 노드가 존재하면 해당 노드를 반환하고, 존재하지 않으면 NULL을 반환한다고 가정해 보자.

• 값이 root node와 일치하는 경우, root node를 반환한다.
• x가 root node보다 작은 경우, 왼쪽 서브트리에서 재귀적으로 탐색한다.
• x가 root node보다 큰 경우, 오른쪽 서브트리에서 재귀적으로 탐색한다.
• 더이상 탐색할 서브트리가 없다면, NULL을 반환한다.

기본적인 탐색 알고리즘인 이진 탐색과 매우 유사하다.

삽입

• 삽입을 하기 전, 탐색을 수행한다.
• 탐색을 모두 마친 뒤, 삽입하려는 key와 일치하는 노드가 존재하면 삽입에 실패한다.
• 일치하는 노드가 존재하지 않으면(위에 작성한 탐색 순서에 따라, NULL이 반환되면), 가장 마지막으로 탐색한 서브트리의 root node와 값을 비교한 뒤 작으면 왼쪽, 같거나 크면 오른쪽에 해당 노드를 삽입한다.

각 노드들은 값에 대해 unique해야 하기 때문에, 삽입 전 탐색 과정이 존재한다.

삭제

삭제도 삽입과 동일하게 먼저 탐색을 수행하고, 노드가 존재하는 경우에만 삭제를 수행한다. 삭제는 삭제 대상이 되는 노드의 자식 수에 따라 동작이 달라진다.

• leaf node 삭제 : 해당 노드를 단순히 삭제한다. 가장 단순한 형태의 삭제.
• child node가 하나인 노드 삭제 : 해당 노드를 삭제하고, child node를 그 자리에 대입한다.
• child node가 두 개인 노드 삭제 : 해당 노드를 삭제하고, 왼쪽 서브트리에 있는 값 중 가장 큰 값, 또는 오른쪽 서브트리에 있는 값 중 가장 작은 값을 parent node와 연결시켜 준다.

삽입과 삭제가 일어나는 경우, 트리의 한 쪽이 비대해지는 경우가 생긴다. 이로 인해 높이 균형이 맞지 않는(unbalanced) 이진 탐색 트리는, 높이 균형이 맞는(balanced) 이진 탐색 트리에 비해 탐색에 대한 평균 노드 접근 수가 높다. 이는 시간복잡도에 영향을 미치므로, 삽입과 삭제가 일어나는 경우 트리를 높이 균형이 맞도록 변형시켜 트리의 높이를 작게 유지하는 self-balanced binary search tree(자가 균형 이진 탐색 트리)라는 ADT가 있다. 따라서 다음 몇 개의 글에서 self-balanaced binary search tree를 구현하기 위한 이론들에 대해 더 깊게 알아볼텐데, 따라서 Red-black tree처럼 조금 더 우리에게 익숙한 이름들이 보일 것이다.