이진탐색트리 (Binary Search Tree)

# 개념 이진 트리이다. 각 노드에 하나의 키를 저장한다. 노드 n의 왼쪽 서브 트리에는 n의 값보다 같거나 작은 노드들이 있다. 노드 n의 오른쪽 서브 트리에는 n의 값보다 같거나 큰 노드들이 있다. @검색 이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴한다. 검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다. 불일치하고 검색하고자 하는 값이 루트노드의 값보다 작을 경우 왼쪽 서브트리에서 재귀적으로 검색한다. 불일치하고 검색하고자 하는 값이 루트노드의 값과 같거나 큰 경우 오른쪽 서브트리에서 재귀적으로 검색한다. @삽입 삽입을 하기 전, 검색을 수행한다. 트리를 검색한 후 키와 일치..
컴퓨터 공학/자료구조 2019. 8. 20. 22:45
1