처리는 AVL 트리 내에서 키를 복제합니다

Question

나는 내 만들고 싶다 avl-tree 중복 키를 지원하지만 기본 동작에 문제가 있습니다. binary search tree 회전이 동일한 키를 가진 노드가 부모의 왼쪽과 오른쪽에있을 수 있다는 중복으로.

예를 들어 키 A가있는 3 개의 노드를 추가 할 때 트리가 회전을 수행하게됩니다.

   A
  /  \ 
 A    A

따라서 그 키로 모든 항목을 얻는 것은 문제가 될 것입니다 ... 두 방향으로 검색하는 것이 좋지 않습니다.

내가 생각했던 솔루션은 각 노드를 매장으로 만드는 것입니다. 이미 존재하는 새 항목을 추가 할 때 배열에 새 항목을 추가하면 키를 사용하여 항목을 제거하면 모든 항목을 찾는 동안 전체 노드가 삭제됩니다. 키가 있으면 해당 배열이 반환됩니다.

복제를 처리 할 다른 방법이 있습니까?

삽입 항목은 키와 값을 가져옵니다. 따라서 특정 키 메소드로 Findall에 의해 값을 반환하려면 값을 내면에 저장해야합니다.

Answer 1

또 다른 일반적인 접근 방식은 더 이상 중복 키를 갖지 않도록 내부적으로 키의 가치를 키우는 것입니다. 중복을 허용하는 트리에서 항목을 삭제하려면 어쨌든 키와 값이 모두 필요합니다.

값을 알지 못하고 키를 검색하려면 (의사 코드)와 같은 작업을 수행합니다.

searchResult = myTree.SearchGreaterOrEqual(Key);
found = (searchResult != null) && (searchResult.Key == Key);

Answer 2

각 노드에 카운트가 포함되어 있으면 : 복제물을 추가하면 카운트가 증가하면 제거는 1이 아닌 한 카운트가 줄어 듭니다.이 경우 전체 노드가 제거됩니다.