(알고리즘) 레드블랙트리
2021. 3. 31. 21:27
이번 포스팅은 레드 블랙 트리를 포스팅할 예정이다. 레드 블랙트리를 포스팅하는 이유는 Java를 더 잘 이해하기 위해서이다. Java의 HashMap 사이즈가 64가 넘을 때에 레드 블랙트리를 사용하고 TreeMap 또한 레드 블랙트리를 사용하기 때문에 해당 코드를 이해하기 위해서 우선적으로 레드 블랙트리에 대한 이해가 선행되어야 함을 깨달았다. 조금 힘들더라도 내실있는 포스팅을 해보도록 노력하겠다! 레드 블랙트리는 왜 쓰는가? 이진 탐색 트리의 단점을 보완하기 위해서 쓰는 자료구조이다. 만약에 정렬된 데이터를 이진 탐색 트리로 구현한다면 아래와 같은 구조일 것이다. (이미 정렬된 데이터에 대해서는 비효율적인 자료구조) 그렇다면 시간복잡도를 따진다면 O(n) 이 나오게 된다. 결코 좋은 시간 복잡도라고 ..
