바이너리 검색을 사용하는 정렬 된 배열에 비해 바이너리 검색 트리의 이점은 무엇입니까? 수학적 분석을 통해 차이점을 알 수는 없으므로 저수준 구현 오버 헤드에 차이가 있어야한다고 가정합니다. 평균 사례 실행 시간의 분석은 아래와 같습니다.바이너리 검색 대 바이너리 검색 트리
와정렬 된 배열 이진 검색
검색 : O (로그 (N))
삽입 : O (로그 (N))
삭제 (우리는 여기서 요소가 삽입 찾을 이진 검색을 실행) O를 (로그 (N)) (우리가 삭제할 수있는 요소)
이진 검색 트리
검색 찾는 이진 검색을 실행 : O (N 로그())
삽입 : O (N 로그())
삭제 : O (log (n))
이진 검색 tre 위에 나열된 연산에 대해 O (n)의 최악의 경우가 있습니다 (트리가 균형을 이루지 않는 경우). 따라서 이진 검색을 사용하는 정렬 된 배열보다 실제로 좋지 않은 것처럼 보입니다.
또한 O (nlog (n))의 비용이 들기 전에 배열을 미리 정렬해야한다고 가정하지 않습니다. 이진 트리에 대해 할 것처럼 요소를 배열에 하나씩 삽입합니다. . 내가 볼 수 BST의 유일한 장점은 중위, 예약 주문, postorder 같은 순회의 다른 유형을 지원한다는 것입니다.
는
이진 검색 배열에서 삽입 및 삭제는 O (n)이고 찾기 만 O (log (n))입니다. –
예를 들어, 배열 대신 링크 된리스트라면, 삽입/삭제는'O (log n)'을 취할 것입니다. 그러나 배열을 위해서는 그렇지 않습니다. – Bhaskar
@Bhaskar, 다른 잘못된 설명인데, 연결된 목록에서 조회하는 것은 O (n)입니다. – Blindy