왜 바이너리 검색 트리인가?

사람들이 왜 이진 검색 트리를 사용합니까? 배열에서 이진 검색을 최저 순위에서 최고 순위 순으로 정렬하지 않는 이유는 무엇입니까? 저에게 삽입/삭제 비용은 같아 보이며, 최대/최소량 등의 프로세스로 생명을 복잡하게 만드는 이유는 무엇입니까?왜 바이너리 검색 트리인가?

데이터 구조 내에서 임의 액세스가 필요하기 때문에 그렇습니까?

출처

2014-01-15 Anonymous

여기에 * 어떠한 컨텍스트도 지정하지 않았습니다. 요구 사항이 다른 상황에 대해 서로 다른 데이터 구조가 사용되었습니다. 어떤 상황에 대해 이야기하고 있습니까? –

삽입 비용이 동일하지 않습니다. 배열의 중간에 항목을 삽입하려면 삽입 된 요소의 오른쪽에있는 모든 요소를 한 위치 씩 이동해야합니다. 그 작업량은 배열 크기에 비례합니다 : O (N). 자체 균형을 이진 트리를 사용하면 삽입의 복잡성이 훨씬 낮아집니다 : O (ln (N)).

출처

2014-01-15 07:08:56 pentadecagon

감사합니다. BBST 또는 일반 BST가 배열 형식으로 표시되지만 속성 때문에 새로운 요소를 삽입 할 셀 (나중에 속성 수정)을 알아낼 수 있습니다. 최저 비용 (최악의 경우 O (ln (N))). 그러나 이해할 수 있듯이 BST는 배열이며 목록이 아닙니다. 큰 비어있는 배열은 트리가 내부에서 자랄 수 있도록 준비되어 있지만 크기가 너무 커지거나 적합하지 않은 경우 - 더 큰 새 배열로 복사해야합니다. 추가 성장을위한 공간)? 감사합니다. –

오, 생각합니다. BBST의 가장 낮은 요소를 얻으려면 포인터 _ 로그 n 번에 _ 추적해야합니다. 나는 인덱스를 가지고 접근 할 수 없다. (단순한 바이너리 힙에 대해 말하더라도) @pentadecagon –

왜 바이너리 검색 트리인가?

답변

관련 문제