lou@blog $ _

이진 탐색 트리 (Binary Search Tree)이진 탐색트리는 데이터의 크기에 따라 노드의 위치가 다르다.정의는 아래와 같다. (1) 모든 원소는 서로 다른 유일한 키를 갖는다.(2) 왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다.(3) 오른쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 크다.(4) 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리이다. 이진 탐색 트리 C++ 구현이제 이진 탐색트리를 구현할텐데,- 탐색(search)- 삽입(insert)두 가지 기능을 수행하도록 할 것이다.구현해볼 이진 탐색트리는 아래와 같이 생겼다. 주황색 표시된 부분은 새로 추가해볼 노드다.1234567891011121314151617181920212223242526272829303132333..

Binary Search는 순서대로 정렬된(sorted) 리스트에서 아이템을 찾는데 유용한 알고리즘이다.Binary Search는 아이템이 있는 범위까지 계속해서 반으로 나누면서 찾는다.1부터 10까지 수 중 아무거나 하나를 생각해서 맞추는 게임의 알고리즘과 동일하다. Binary Search의 의사 코드는 다음과 같다. 1. min은 범위 중 가장 낮은 것, max는 범위 중 가장 높은 것이다.min = 1, max = n2. min과 max의 평균값을 구해서 반내림을 한다. 이게 추정치다. (정수가 되도록)3. 만약 숫자를 맞췄다면, stop!4. 만약 추정치가 너무 낮다면 min을 그 추정치보다 높게 변경.5. 만약 추정치가 너무 높다면 max를 그 추..