다수의 노드를 빠르게 삽입할 수 있는 최고의 자체 균형형 BST

Question

여러 가지 자체 균형 조정에 대한 세부정보를 찾을 수 있었습니다. BST여러 소스를 통해 살펴봤지만 다양한 상황에서 어떤 것이 가장 사용하기 좋은지(또는 실제로는 중요하지 않은지) 자세히 설명하는 좋은 설명을 찾지 못했습니다.

나는 BST 이는 천만 개가 넘는 노드를 저장하는 데 최적입니다.노드 삽입 순서는 기본적으로 무작위이며 노드를 삭제할 필요가 없으므로 삽입 시간만 최적화해야 합니다.

퍼즐 게임에서 이전에 방문한 게임 상태를 저장하는 데 이를 사용하여 이전 구성이 이미 발생했는지 빠르게 확인할 수 있습니다.

Answer 1

레드 블랙 삽입이 많은 애플리케이션에서는 AVL보다 낫습니다.상대적으로 균일한 조회를 예상한다면 Red-Black이 적합합니다.최근에 본 요소를 다시 볼 가능성이 더 높은 상대적으로 불균형한 조회가 예상되는 경우 다음을 사용하고 싶습니다. 나무를 펴다.

Answer 2

왜 사용하는가? BST 조금도?귀하의 설명에 따르면 사전은 더 좋지는 않더라도 잘 작동할 것입니다.

을 사용하는 유일한 이유 BST 컨테이너의 내용을 주요 순서대로 나열하려는 경우입니다.확실히 그렇게 하고 싶은 것 같지는 않습니다. 이 경우 해시 테이블을 선택하세요. O(1) 삽입과 검색, 삭제 걱정은 NO, 뭐가 더 좋을까요?

Answer 3

둘은 스스로 균형을 잡는다 BST내가 가장 잘 알고 있는 것은 빨간색-검정색과 AVL, 따라서 다른 솔루션이 더 나은지 확실하게 말할 수는 없지만 기억나는 대로 red-black은 다음 솔루션에 비해 삽입 속도가 빠르고 검색 속도가 느립니다. AVL.

따라서 삽입이 검색보다 우선순위가 높으면 빨간색-검정이 더 나은 솔루션일 수 있습니다.

Answer 4

[해시 테이블에는] O(1) 삽입 및 검색

나는 이것이 잘못된 것이라고 생각합니다.

우선, 키 공간을 유한하게 제한하면 요소를 배열에 저장하고 O(1) 선형 스캔을 수행할 수 있습니다.또는 배열을 섞은 다음 O(1) 예상 시간에 선형 스캔을 수행할 수 있습니다.물건이 유한하면 물건은 쉽게 O(1)입니다.

따라서 해시 테이블이 임의의 비트 문자열을 저장한다고 가정해 보겠습니다.각 키가 유한하고 무한한 키 세트가 있는 한 그다지 중요하지 않습니다.그런 다음 쿼리 및 삽입 입력의 모든 비트를 읽어야 합니다. 그렇지 않으면 빈 해시에 y0을 삽입하고 y1에 쿼리합니다. 여기서 y0과 y1은 사용자가 보지 않는 단일 비트 위치에서 다릅니다.

하지만 키 길이가 매개변수가 아니라고 가정해 보겠습니다.삽입과 검색에 O(1)이 걸리면 특히 해싱에 O(1) 시간이 걸립니다. 즉, 해시 함수의 한정된 양의 출력만 보게 됩니다(이로부터 BE 유한한 출력만 허용됨)

이는 버킷이 한정되어 있으면 모두 동일한 해시 값을 갖는 무한한 문자열 집합이 있어야 함을 의미합니다.내가 많이 삽입한다고 가정하자.그 중 Ω(1)을 선택하고 쿼리를 시작합니다.이는 내 쿼리에 응답하기 위해 해시 테이블이 다른 O(1) 삽입/검색 메커니즘으로 대체되어야 함을 의미합니다.어느 것입니까? 직접 사용하면 어떨까요?