어떤 데이터 구조가 빠른 삽입, 삭제 및 검색을 지원합니까?

나는 이것이 존재해야한다고 느낀다. 그러나 나는 단지 그것을 생각할 수 없다. 정렬 된 값 목록을 보유하고 신속하게 검색 (배열과 같이 log (N) 시간) 할 수 있고 log (N) 또는 일정 시간에 요소를 삽입 및 제거 할 수있는 데이터 구조가 있습니까?어떤 데이터 구조가 빠른 삽입, 삭제 및 검색을 지원합니까?

출처

2013-07-15 Bi Rico

당신은 어떤 언어를 말하지 않았지만 정렬 된 링크 된 목록은 이진 검색 알고리즘 (삽입 및 삭제에도 사용됨)으로 모든 것을 수행합니다. – kevinsa5

@ kevinsa5, 내 이해는 연결된 목록이 상수 시간 조회를 지원하지 않기 때문에 이진 검색을 지원하지 않으며 O (N) 조회 만 지원합니다. 내가 틀렸다면 나를 바로 잡아주세요. 또한 이것은 언어에 불가항력적인 질문입니다. 그런 데이터 구조가 합리적인 언어로 구현 될 수 있어야한다고 생각합니다. –

이진 트리, 그럼? 일정한 시간이 아니라 O (log (n)). – kevinsa5

이것은 정렬 된 순서로 요소를 저장하고 O (log n) 삽입, 삭제 및 검색을 허용하고 모든 요소의 O (n) 탐색을 허용하는 균형 이진 검색 트리에 대한 설명입니다.

빨강/검정 나무, AVL 나무, 희생양 나무, 스플래쉬 나무, AA 나무, 트랩, (a, b) 트리 등 다양한 방법으로 밸런스드 BST를 구축 할 수 있습니다. 너의 문제. 그 중에서도 분출 나무가 아마 코딩하기 쉽고, AA 나무와 AVL 나무가 뒤 따른다.

희망이 도움이됩니다.

출처

2013-07-15 06:15:05 templatetypedef

어떤 데이터 구조가 빠른 삽입, 삭제 및 검색을 지원합니까?

답변

관련 문제