Hello backEnd

TreeSet!! public class TreeSet extends AbstractSet implements NavigableSet, Cloneable, java.io.Serializable {}TreeSet의 구조를 살펴보면 다음과 같다. 이는 AbstractSet, NavigableSet인터페이스를 구현하여 사용하고 있다. TreeSet은 이름처럼 Tree와 같은 구조를 가지고 원소들을 저장한다. 특징을 나열하자면 중복 불가 원소의 순서 보존되지 않음 집어넣은대로 들어가는게 아니라 알아서 트리 구조로 정렬시킨다. 요소를 오름차순으로 정렬한다. Thread-safe하지 않다. Red-Black-Tree TreeSet은 내부적으로 Red-Black-Tree를 사용하고 있다. 이게 뭘까...? Red-B..

Red-Black-Tree!! 얘는 일종의 자기 균형 이진탐색 트리이다. 이진탐색트리란 자신의 왼쪽 서브 트리에는 현재 노드보다 작은 것, 오른쪽 서브 트리에는 큰 것만을 가질 수 있다. 이 덕분에 이진탐색트리에서는 조회를 할 때에 O(log n)의 시간 복잡도를 갖는다. 그런데 만약 요런 식으로 조회하면 O(n)의 시간 복잡도를 갖는다. Red-Black-Tree 알고리즘은 이런 문제를 해결하기 위해 도입되었다. 트리의 속성 모든 노드는 Red 혹은 Black이다. root node는 Black!!! 모든 nil노드는 Black!!! nil노드? go언어에서 null을 nil로 써넣는데 존재하지 않음을 의미하는 노드이다. 자녀가 없을 때에 자녀를 nil노드로 표기 이 nil노드는 값이 있는 노드와 동등..