이진 트리

일반적으로 배열을 검색할 때는 선형 검색을 수행한다. 즉, 앞에서부터 쭉 비교해보는 것이다. N 크기의 배열일 경우 O(N)의 효율을 가진다. 하지만, 배열을 정렬하면 우리는 다음과 같이 검색할 수 있다.1) 검색하고자 하는 수를 배열의 가운데 위치한 수(기준 수) 와 비교한다.2) 기준 수와 비교하여 작으면 기준 수의 왼쪽 배열을 가져와 다시 1)을 반복한다. (이때 다른 반대쪽 배열은 버리면 된다!)이는, 내가 생각한 숫자를 맞추는 게임에서도 자주 사용하는 방법이다. 어떤 수를 제시하면 크다, 작다를 통해 범위를 줄이게 되는 알고리즘이다. 이를 이진 검색이라고 한다. 배열을 분할하는 차수에 의존하므로 O(logN)의 효율을 가진다..........

이진 트리에 대한 요약내용입니다.

자세한 내용은 아래에 원문링크를 확인해주시기 바랍니다.

원문링크 : 이진 트리