알고리즘 이진트리에 대해서 문의 드립니다(그림설명)
빛초롱
2023.04.01
알고리즘에서 이진 트리에 대한 것인데요
원서로 공부하고 있는데 이해가 잘 안되서 질문을 합니다.
위에 있는 그림 설명해주실분 없나요??
첫번째 그림 보간 검색(interpolation search)
두번째 그림 이진 검색 트리
세번째 그림 이진 검색 트리(가상 노드들로 된것)
네번째 그림 이진 검색 트리에서 (I의) 삽입
그리고 추가 질문이요
1. 보간검색에서 x = ( l + r ) / 2 로 계산한다고 했는데
l 은 무엇이고 r 은 무엇인지요?
그리고 아래는 이진트리 성질인데 왜 그런지 이유를 모르겠습니다 ㅠㅠ
2.이진 검색은 성공적인 경우나 비 성공적인 경우 어느 것에 대해서도 결코 lg N + 1번의 비교이상이 되지 않는다.
3.보간 검색은 무작위 키들의 파일에서 성공적인 것과 비 성공적인 검색에 대해 lg lg N + 1번 비교보다 적게 된다. 만약 N이 10억개이면, lg lg N 5가 된다. 이와 같이, 어떤 레코드는 이진 검색에 대한 부수적인 개선점으로 단지 몇 가지 접근들(평균적인 경우)로서 찾아지게 된다.
4. 이진 검색 트리에서 검색이나 삽입은 N개 무작위 키들로 생성된 트리에서 평균적으로 약 2 ln N 비교를 한다.
5. 최악의 경우에서, N개 키로 이루어진 이진 검색 트리의 검색은 N번의 비교를 한다.
