[자료구조] 이진탐색트리

1. 이진탐색트리란?​

이진탐색트리란 이진탐색(Binary Search)와 연결리스트(Linked List)를 결합한 자료구조의 일종이다.

 

	이진 탐색	연결 리스트
장점	탐색에 소요되는 시간복잡도가 O(logN) 로 빠르다	삽입과 삭제에 걸리는 시간 복잡도가 O(1)로 빠르다
단점	삽입과 삭제가 불가능하다	탐색의 시간 복잡도가 O(N) 이다

 

위와 같은 이진 탐색과 연결리스트의 장점을 고안하기 위해 만들어졌으며, 

이진 탐색의 효율적인 탐색 능력을 유지하면서도

빈번한 자료 입력과 삭제가 가능하기 위해 사용된다.

 

---

2. 이진탐색트리 특징​

 

 

이진탐색트리는 이진트리의 일종으로 다음과 같은 규칙으로 구성한다.

• 모든 노드는 유일한 키를 갖음. (중복된 노드 X)
• 각 노드의 왼쪽 서브 트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어짐.
• 각 노드의 오른쪽 서브 트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어짐.
• 각 노드의 왼쪽, 오른쪽 서브트리 또한 이진탐색트리로 구성.

 

다음은 이진탐색트리가 가진 특징이다.

탐색의 시간 복잡도는 트리의 높이를 h라고 할 때 O(h) 이다.

위와 같은 편향 트리의 경우 탐색에 O(N)의 시간이 소요된다.

 

• 이진탐색 트리의 순회는 중위 순회 (in order) 방식이다. (왼쪽 - 루트 - 오른쪽)
  
  
  중위 순회: 4, 7, 16, 20, 37, 38, 43 (중위 순회 방식으로 정렬된 순서를 얻을 수 있다)

 

• 이진탐색트리의 삽입 연산은 루트노드에서 탐색을 시작해 서브트리가 없는 리프 노드에서 이루어진다.
  
  

이진탐색트리의 삭제 연산은 세가지 케이스로 나누어 연산한다.

• 자식 노드가 없는 경우 -> 삭제할 노드를 그냥 없앤다.
• 자식 노드가 하나 있는 경우 -> 삭제할 노드의 자식을 올린다.
• 자식 노드가 두 개 있는 경우 -> 오른쪽 서브 트리에서 가장 작은 값 or 왼쪽 서브 트리에서 가장 큰 값을 올린다.

Q: 자식 노드가 두 개인 경우 오른쪽 서브트리와 왼쪽 서브트리 중 어느 것을 선택해야 하나요?

A: 오른쪽 서브트리와 왼쪽 서브트리를 정하는 규칙은 따로 정해져있지 않으며 두 방식에 차이가 있지 않습니다.
따라서 구현자가 두 방식 중에 자유롭게 선택해 규칙을 정할 수 있습니다.

 

 

3. 시간복잡도

Q: 이진탐색트리의 시간복잡도는?

A. 트리의 높이를 h라고 할 때 O(h)이다.
노드의 개수 N이 주어졌을 때 균등 트리 일 경우, O(logN) 이며
편향 트리일 경우 최악의 경우, O(N) 이다.

Q. 이진탐색트리의 삽입,삭제 연산 시간복잡도는?

A. 이진탐색트리의 삽입과 삭제 연산은 탐색이후 이루어지기 때문에
탐색에 필요한 O(h)이 소요되며 연결리스트를 사용하므로
입력과 삭제에는 O(1)이 사용된다.

따라서 총 소요되는 시간 복잡도는 O(h)이며
최악의 경우 탐색과 동일하게 O(N)이 소요된다.

※ 따라서, 이진 탐색 트리는 한쪽 방향으로 노드가 집중된 편향트리에서는 효율적이지 않다.