[C언어 #69] 이진탐색트리 (Binary Search Tree)

c언어 이진탐색트리 (Binary Search Tree)

 

[C언어 #69] 이진탐색트리 (Binary Search Tree) - 구현 (1) - 노드 생성, 노드 삽입

[C언어 #69] 이진탐색트리 (Binary Search Tree) - 구현 (2) - 노드 탐색

[C언어 #69] 이진탐색트리 (Binary Search Tree) - 구현 (3) - 노드 삭제

[C언어 #69] 이진탐색트리 (Binary Search Tree) - 구현

 

 

 

 

I 이진탐색트리 (Binary Search Tree)

숫자와 같은 데이터를 체계적으로 저장하기 위한 노드 (node) 기반의 이진 트리 형태의 자료구조

• 노드 저장소의 왼쪽 서브 트리에는 작은 수를 가진 노드만 존재
• 노드 저장소의 오른쪽 서브 트리에는 큰 수를 가진 노드만 존재
• 노드 저장소의 양쪽 노드 역시 이진탐색트리 구조
• 중복 노드는 존재 X

 

I 이진탐색 (Binary Search)

이진탐색에서는 'n' 개의 요소에서 시작하여 중간값(mid element)을 지정하고 'n/2'개 요소의 중간값을 찾아나간다.

탐색은 해당 값을 찾거나 값이 하나도 남지않을 때까지 지속한다.

 

 

I 이진탐색트리(Binary Search Tree)에서의 탐색

탐색을 뿌리 위치(root)에서 시작하여 탐색값과 노드저장소의 값을 비교하여 한쪽 서브트리를 제거하며 순회한다.

'n'개의 노드에서 한쪽을 제거하면 'n/2'개의 노드에서 탐색을 진행하며 값을 가지고 있는 노드를 찾거나, 하나의 노드만 남아있을때까지 지속한다.