기본 자료구조 - 해시, 트리, 힙

해시 (Hash)

• 임의의 데이터에 대해 고정된 길이의 데이터로 매핑
• 이론적으로 삭제 O(1), 삽입 O(1), 검색 O(1)의 시간복잡도
• 해시 테이블 내부의 값이 많아지면 해시충돌 현상 -> 기본 연산의 시간 길어짐

public class HelloWorld {
	public static void main(String[] args) {
		HashMap<String, String> h1 = new HashMap<String, String>();
		HashMap<String, String> h2 = new HashMap<String, String>();
		
		h1.put("aaa", "1111");
		h1.put("bbb", "2222");
		h1.put("ccc", "3333");
		h1.putIfAbsent("aaa", "0000");
		h1.putIfAbsent("ddd", "4444");
		h2.putAll(h1);
		System.out.println("h1 : " + h1);
		System.out.println("h2 : " + h2);
		
		System.out.println("[1]: " + h1.containsKey("aaa"));
		System.out.println("[2]: " + h1.containsValue("1111"));
		System.out.println("[3]: " + h1.isEmpty());
		System.out.println("[4]: " + h1.size());
		System.out.println("[5]: " + h1);
		System.out.println("[6]: " + h1.remove("aaa", "1111"));
		System.out.println("[7]: " + h1.put("bbb", "0000"));
		System.out.println("[8]: " + h1.replace("ccc", "0000"));
		System.out.println("h1 : " + h1);
		System.out.println("h2 : " + h2);
				
		
		for (String key: h1.keySet()) {
			String value = h1.get(key);
			System.out.println("Key:" + key + ", Value:" + value);	
		}
	}
}

 

 

 

트리 (Tree)

• 루트 노등와 자식 노드의 연결관계가 반복적으로 구성
• 루트 노드의 부모는 0개, 자식 노드의 부모는 1개
• 루트 노드는 0개 이상의 자식 노드, 자식 노드 또한 0개 이상의 자식 노드
• 사이클 갖고 있지 않음

이진트리 (Binary Tree)

• 트리에서, 자식 노드의 개수가 0개 이상 2개 이하로 제한

 

 

힙 (Heap)

• 완전 이진 트리의 일종, 부모의 값이 항상 자식보다 크거나 작아야함
• 루트는 최댓값이거나 최솟값이 보장
• 최댓값/최솟값을 O(1)만에 찾을 수 있음

//최소힙
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

//최대힙
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return - Integer.compare(o1,o2);
        }
    });
PriorityQueue intQueue = new PriorityQueue((a,b) -> b-a);

 

 

 

참고 - https://github.com/VSFe/Algorithm_Study?tab=readme-ov-file