이진 검색 트리 밀도?

나는 이진 탐색 나무를 다루는 숙제를하고 있는데, 나는 꽤 이해하지 못하는 문제를 발견했다. 이 질문은 밀도가 어떻게 이진 트리를 검색하는 데 걸리는 시간에 영향을 주는지 묻습니다. 바이너리 서치 트리와 big-O 표기법을 이해하지만 이전에는 밀도를 다루지 않았습니다.이진 검색 트리 밀도?

출처

2012-06-19 kubiej21

이진 검색 트리의 밀도는 레벨에 누적되는 노드 수로 정의 할 수 있습니다. 완벽한 이진 트리가 가장 높은 밀도를가집니다. 따라서 질문은 기본적으로 각 레벨의 노드 수가 트리에서 검색 시간에 미치는 영향에 대해 묻습니다. 그게 확실하지 않으면 알려줘.

출처

2012-06-19 00:21:55

좋아, 그게 도움이된다. 이진 검색 트리의 검색 기능은 부모를 일부 값과 비교하기 때문에 왼쪽 또는 오른쪽 자식으로 이동하여 비교됩니다. bst가 더 높은 밀도를 가지면 발생하는 비교 횟수가 증가하므로 지정된 값을 찾는 데 걸리는 시간이 증가합니다. 나는 올바른 길을 가고 있는가? – kubiej21

@ kubiej2 이진 트리의 가장 좋은 경우는 밀도가 높은 경우 트리에 삽입하기 전에 항목을 정렬하면 어떻게되는지 생각해보십시오. – mikek3332002

오우. 나는 그것을 지금 이해한다. 감사. – kubiej21

이진 검색 트리 밀도?

답변

관련 문제