나는 나무 기반지도를 구현하도록 요청, 다음과 같이 내가

Question

할당을 뭘하는지 아무 생각이 없다가 봤는데 :

(50 점)라는 클래스 트리 맵, 2 유형의 제네릭 클래스를 쓰기를 변수, K 및 V (K는 키이고 V는 키를 통해 검색 할 수있는 값임) 클래스에는 다음과 같은 메서드가 있어야합니다.

public V get (K 키); 이 메서드는 지정된 키의지도에 저장된 값을 검색해야하며, 키가지도에 없으면 null을 반환해야합니다.

공개 V put (K 키, V val); 이 메서드는 지정된 값을 키 아래에 저장해야합니다. 맵에 키가 이미있는 경우 이전 값을 반환하고 새 값으로 덮어 씁니다. 열쇠가 존재하지 않는 경우, 메소드는 null를 돌려 주어야합니다.

공개 세트 <k> keySet(); 이 메소드는, 키의 자연 순서 부 (예를 들어, 캐릭터 라인의 알파벳 순서)로, 맵 내의 모든 키를 포함한 Java 세트를 돌려줍니다.

get 및 put 메소드는 최악의 경우 Θ (log n) 시간, Θ (n) 시간의 keySet에서 작동해야합니다. 당신은 그냥 도움이 필요, 코드

---

난 그냥 나에게 답을 줄 사람을 기대하고 여기에 게시 아니에요을위한 출발점으로 강의에서 레드 - 블랙 트리 코드를 사용해야합니다. 나는 웹을 둘러싼 모든 것을 수색했는데이 질문과 관련된 모든 것은 내 머리 위이거나 과제의 범위를 벗어나는 것 또는 존재하지 않는 것으로 보인다.

get(), put() 및 keySet()이 필요한 유일한 방법 일 수 있습니까? 어떻게 red-black tree가 rotateRight(), rotateLeft() 등과 같은 메소드없이 작동 할 수 있습니까? put() 메서드를 방대하게 만드는 것만으로 그 메서드가 수행하는 모든 작업을 수행해야합니까?

당신은 웃을거야,하지만 지금까지 내가 가진 전부이고 어디에서 계속 해야할지 모르겠다.

import java.util.Set; 

public class TreeMap301<K, V> { 

    K key; 
    V value; 
    private int size = 0; 

public V get(K key){ 
    return null; 
} 

public V put(K key, V val){ 

    size += 1; 
    return null; 
} 

public Set<K> keySet(){ 
    return null; 
} 

public int size(){ 
    return size; 
} 
}  

어떻게 구현해야하는지 잘 모르겠습니다. 모든 키와 모든 값의 목록을 만드는 것입니까? 그 목적을 무너 뜨리는 것 같아. 나는 약간의 지침을 찾고 있습니다. 나는이 수업에서 길을 잃어 버렸으니 제발 그렇게 말하지 마세요.

Answer 1

나는 누군가가 당신을 위해 당신의 임무를 수행하는 것보다 (당신이 임무임을 우리에게 알려 줘서 고마워) 힌트를 찾고 있다고 가정합니다. 여기에 당신이 시작하는 몇 가지 아이디어가 있습니다 :

1. 이미 레드 - 블랙 트리 코드가있는 경우

   다음 이미지도에 긴 방법입니다. RB 트리의 각 노드는 키와 값을 보유해야합니다.

2. get 메소드는 실제로 트리에서 키를 검색하고 찾은 노드의 값을 리턴합니다. 그것은 사소한 것이어야합니다.

3. put 메서드는 그다지 어렵지 않습니다. 지정된 키와 값 (키가 이미있는 상황을 적절하게 처리 함)을 사용하여 트리에 새 노드를 추가하는 것입니다. 이것은 모든 재조정 코드가 호출되는 곳입니다.

4. keySet 메서드는 약간 더 복잡합니다. 트리의 모든 노드를 살펴보고 세트에 키를 추가 한 다음 반환합니다. 다시 도전하지 마라.

이러한 특정 도움이 필요하시면 구현을 시도하는 코드를 게시하십시오. 도움을 제공 할 수있는 사람이있을 것입니다.