bst에서 중복을 다루기

Question

bst는 중복 된 항목에 대처할 수 있어야합니다. 과도한 양의 코드를 필요로하지 않는 방법에 대한 전략을 가진 사람이 있습니까? 필자는 일관되게 오른쪽에 중복을 추가한다고 생각했지만 그때는 bst 순서가 엉망이되었습니다. 예를 들어 복제물에 두 명의 자녀가 있고 두 명의 자녀가있는 경우 어떻게됩니까? 복제물을 삽입하는 것은 쉽지만 대체 된 노드로 수행해야 할 작업은 무엇입니까?

Answer 1

이진 검색 트리의 노드를 링크 된 목록으로 만들 수 있습니다. 여기

class Data implements Comparable<Data> 
{ 
    // These are the data elements in your binary search tree 
} 

class TreeNode 
{ 
    TreeNode left; // elements less than current node, or null 
    TreeNode right; // elements greater than current node, or null 
    List<Data> items = new LinkedList<Data>();  
} 

는 treeNode.items는 항상 같은 그 item1.compareTo(item2) == 0item1 모든과 treeNode.items에 item2를 비어 있지 않은 목록입니다.

중복 요소를 삽입하려면 TreeNode 개체를 찾고 items에 새 항목을 추가하십시오.

요소를 찾는 논리는 이전에했던 것과 거의 동일합니다. 단, 관련 TreeNode 개체를 찾으면 연결된 목록을 탐색해야합니다.

Answer 2

자체 균형 조정 BST가 아닌 한 노드의 왼쪽 또는 오른쪽에 동일한 노드를 배치하는 데는 문제가 없습니다.

편집 (의 simonn 후 발언) : 문제의 "중복 노드는"이미 두 아이가있는 경우

후 간단히 왼쪽에있는 "새 중복 노드"를 삽입하고 왼쪽 아이를하자 " 오래된 중복 노드 "가"새 중복 노드 "의 왼쪽 하위 노드가됩니다.

예를 들어 설명해 드리겠습니다. 다음은 중복을 삽입하기 전에 나무 :

4' 
/\ 
    2 5 
/\ 
1 3 

이제 요소 4''가 삽입됩니다 :

 4' 
    /\ 
    4'' 5 
/
    2 
/\ 
1 3 

만큼 나무가 자기 분산되지 않습니다, 당신은 괜찮을 것 같네요.

Answer 3

실제로 중복 된 항목을 별도의 노드로 저장해야하는지 궁금합니다. 귀하의 노드에 카운터 변수를 추가하는 것으로 충분합니까? 그렇게하면 트리를 가로 지르면 중복 된 항목의 수를 알 수 있고 순서를 유지할 수 있습니다.