TreeMap - Red-Black Tree

https://security-gom.tistory.com/30

개념 숙지 후 해당 문제를 풀어보면 도움이 될 것이라고 생각한다.

[프로그래머스] 이중우선순위큐 - TreeMap

TreeMap이란?

• TreeMap은 이진 트리를 기반으로 한 MAP의 컬렉션이다
• 기존의 TreeSet과의 차이는 값만 저장하는 것이 키와 값이 저장될 수 있는 Map, Etnry를 저장하는 것이다.
• TreeMap에 객체를 저장하면 자동으로 정렬된다
  • 숫자 타입 오름차순
  • 문자 타입 유니코드 기준
    • 부모와 비굑해서 낮은 것은 왼쪽 자식 큰 놈은 오른쪽 자식으로 넣어서 저장한다.
    • 즉시 정렬하기 때문에 데이터 저장 시 HashMap대비 느리다
    • 정렬된 데이터를 사용하거나 범위 검색이 필요하면 유용하다

  Red-Black Tree

  • TreeMap은 이진검색트리의 문제점을 보완해서 나온 레드-블랙 트리로 이루어져있음
  • 일반적인 이진검색트리의 경우 트리의 높이 만큼 시간이 필요함
  • 편향이 되어있는 트리의 경우 비효육적으로 검색이 오래걸림
  • 레드 블랙 트리는 부모 노드보다 작은 값은 가지는 노드는 왼쪽으로 큰 값을 가지면 오른 쪽으로 넣어서 데이터의 추가 삭제ㅐ시 트리가 한쪽으로 치우쳐 지는 것을 방지함

사용법

선언

 TreeMap<Integer,String> map1 = new TreeMap<Integer,String>();//TreeMap생성
TreeMap<Integer,String> map2 = new TreeMap<>();    //new에서 타입 파라미터 생략가능
TreeMap<Integer,String> map3 = new TreeMap<>(map1);//map1의 모든 값을 가진 TreeMap생성
TreeMap<Integer,String> map6 = new TreeMap<Integer,String>(){{//초기값 설정
    put(1,"a");
}};

값 추가

 TreeMap<Integer,String> map = new TreeMap<Integer,String>();//TreeMap생성
map.put(1, "가");//값 추가
map.put(2, "나");
map.put(3, "다");

값 삭제

TreeMap<Integer, String> map = new TreeMap<Integer,String>(){{//초기값 설정
    put(1, "가");//값 추가
    put(2, "나");
    put(3, "다");
}};
map.remove(1); //key값 1 제거
map.clear(); //모든 값 제거

단일 값 출력

TreeMap<Integer,String> map = new TreeMap<Integer,String>(){{//초기값 설정
    put(1, "가");//값 추가
    put(2, "나");
    put(3, "다");
}};

System.out.println(map); //전체 출력 : {1=가, 2=나, 3=다}
System.out.println(map.get(1));//key값 1의 value얻기 : 가
System.out.println(map.firstEntry());//최소 Entry 출력 : 1=가
System.out.println(map.firstKey());//최소 Key 출력 : 1
System.out.println(map.lastEntry());//최대 Entry 출력: 3=다
System.out.println(map.lastKey());//최대 Key 출력 : 3

poll

  map.pollLastEntry(); // 최대값 제거
  map.pollFirstEntry(); // 최소값 제거