Binary Trees, Binary Search Trees

• 트리에 포함되는 모든 노드의 차수가 2 이하인 트리
• 모든 노드는 자식이 없거나 (리프 노드의 경우), 하나만 있거나, 아니면 둘 있는 세 경우 중 하나에 해당

연산

• size() - 현재 트리에 포함되어 있는 노드의 수
• depth() - 현재 트리의 깊이 (또는 높이)
• 트리는 정의 자체가 재귀적이기 때문에, 이를 대상으로 하는 연산들도 대부분 재귀적으로 구현 가능

Traversal(순회) 연산

• 트리의 각 노드를 정해진 순서로 방문하는 것
• 트리를 순회하는 순서를 크게 나누면 깊이 우선 순회 (depth first traversal) 와 넓이 우선 순회 (breadth first traversal)
• 이 순회 방식들은 그래프에도 적용되는데, 많은 알고리즘들이 트리 또는 그래프의 순회를 이용하여 주어진 문제를 해결

Depth First Traversal(깊이 우선 순회)

• 이진 트리를 대상으로 하는 경우에는, 세 가지의 서로 다른 순서를 정의할 수 있.
• 어느 노드 x 를 기준으로 할 때, (이 정의는 또 다시 재귀적)

1.중위 순회 (in-order traverasl): 왼쪽 서브트리를 순회한 뒤 노드 x 를 방문, 그리고 나서 오른쪽 서브트리를 순회
2.전위 순회 (pre-order traversal): 노드 x 를 방문한 후에 왼쪽 서브트리를 순회, 마지막으로 오른쪽 서브트리를 순회
3.후위 순회 (post-order traversal): 왼쪽 서브트리를 순회, 오른쪽 서브트리를 순회, 그리고 나서 마지막으로 노드 x 를 방문 하는 순서

• 이러한 순회 알고리즘 또한 (정의에서 느껴지는 바와 같이, 당연히) 재귀적으로 구현하는 것이 매우 자연스럽다.

Breadth First Traversal(넓이 우선 순회)

• 하나의 노드를 방문했을 때, 나중에 그 노드의 자식 노드들을 방문하기로 해 두고, 같은 수준에 있는 다른 노드들 (직접 연결되어 있는 노드들이 아닌) 을 우선 방문해야 하기 때문에, 이 알고리즘은 재귀적인 성질을 가지지 않는다.

• "나중에 다시 방문하기로 하고 그 순서를 기억해 두자" 에 적합한 자료 구조 : 큐 (queue)

• 먼저 넣은 원소가 먼저 나오는, 선입선출 (FIFO; first-in first-out) 성질을 가지고 있기 때문에, 큐는 이러한 종류의 응용에 딱 적합

Binary Search Trees(이진 탐색 트리)

• 이진 탐색 트리 (binary search tree) 는 이진 트리의 일종
• 이진 탐색 알고리즘과 이진 탐색 트리를 이용한 탐색 알고리즘은 똑같은 것은 아니지만, 매우 유사

이진 탐색 알고리즘 vs. 이진 탐색 트리

이진 탐색 알고리즘

• 이미 정렬된 선형 배열을 대상으로, 배열을 절반씩 잘라 가면서 찾고자 하는 원소 (또는 키 - key) 가 들어 있을 수 없음이 보장되는 절반을 탐색 대상에서 제외함으로써 매 반복에서 탐색 대상이 되는 배열의 길이를 반으로 만들어 나가는 알고리즘
• 따라서 이 알고리즘의 실행 시간은 배열의 길이를 n 이라고 할 때 log(n) (밑은 2 입니다) 에 비례
• 이진 탐색을 적용하기 위해서는 탐색 대상인 배열이 미리 정렬되어 있어야 하므로, 이 배열에 데이터 원소를 추가하거나 배열로부터 데이터 원소를 삭제하는 일은 n 에 비례하는 시간을 소요

이진 탐색 트리

• 모든 노드에 대해서 왼쪽 서브트리에 들어 있는 데이터는 모두 현재 노드의 값 (키) 보다 작고 오른쪽 서브트리에 들어 있는 데이터는 모두 현재 노드의 값 (키) 보다 크도록 트리를 유지
• 이러한 성질을 만족하는 이진 트리를 이진 탐색 트리라고 부른다.

  탐색을 할 때는 루트 노드에서 시작해서 한 번에 한 단계씩 간선을 따라 아래로 아래로 내려간다.
  어느 노드를 방문했을 때, 이 노드에 담긴 데이터 원소보다 찾고자 하는 키가 더 작은 경우에는 왼쪽 서브트리를, 더 큰 경우에는 오른쪽 서브트리를 택한다.
  반대쪽 서브트리에는 찾고자 하는 값이 없음을 보장할 수 있으니까 탐색할 필요가 없다는 성질을 이용하는 것.
  이렇게 해서 리프 노드에까지 이르렀는데도 그 사이에 찾고자 하는 값을 만나지 못하면 이 이진 탐색 트리에는 찾으려는 값이 없다는 것을 알 수 있다. 트리라는 자료 구조가 매우 재귀적인 성질을 갖는다.

연산

insert(): 트리에 주어진 데이터 원소를 추가
remove(): 특정 원소를 트리로부터 삭제
lookup(): 특정 원소를 검색 (탐색)
inorder(): 키의 순서대로 데이터 원소들을 나열
min(), max(): 최소 키, 최대 키를 가지는 원소를 각각 탐색

• 가장 중심이 되는 연산은 탐색 (lookup)
• 이 연산의 실행 시간은 트리의 높이 (또는 깊이) 에 비례하므로, 평균적으로 (노드의 개수, 즉 데이터 원소의 개수를 n 이라 할 때) log(n) 에 비례
• 또한, 선형 배열이 아닌 트리 구조를 택하기 때문에 삽입/삭제 (insert/remove) 연산 또한 평균적으로 log(n) 에 비례하는 시간을 소요
• 왜 "평균적" ? 어떤 특수한 경우에 대해서는 이진 탐색 트리가 효과를 발휘할 수 없는 모습을 가지기 때문