TreeSet TreeSet은 HashSet과 마찬가지로 Set 컬렉션 중 하나이다. 그러나 TreeSet 이진탐색트리(BinarySearch Tree)의 구조로 되어있어, 데이터를 넣을 때 자동으로 정렬된다. 따라서 TreeSet은 일반적인 Set보다 데이터 추가, 삭제에는 시간이 오래 걸리지만 정렬되어 저장된다는 점 때문에 조회가 빠르다. 기본적으로 오름차순 정렬을 지원하지만, 생성자의 매개변수로 Comparator 클래스를 구현하여 넣어주면, 정렬 방법도 설정할 수 있다. TreeSet의 구현 레드 - 블랙 트리(Red - Black - Tree) TreeSet은 이진탐색트리의 문제점을 보완한 균형이진탐색 트리 중 하나인 레드-블랙 트리를 사용한다. 이진탐색트리는 데이터가 한쪽으로 치우쳐져 들어올 ..
TreeMap TreeMap은 HashMap과 마찬가지로 Map 컬렉션 중 하나이다. 같은 Tree 구조로 이루어진 TreeSet과 차이점은 TreeMap이 Map.entry()를 저장한다는 점이다. TreeMap은 이진탐색트리(BinarySearch Tree)의 구조로 되어있어, 데이터를 넣을 때 자동으로 정렬된다. TreeMap은 일반 Map보다 데이터 추가, 삭제에는 시간이 오래 걸리지만 정렬되어 저장된다는 점 때문에 조회가 빠르다. 기본적으로 Key값을 기준으로 오름차순으로 정렬된다. 그러나 Key값의 데이터타입이 Comparable이 구현되어있지 않은 클래스 이거나, 정렬 방법을 설정하려면 생성자의 매개변수로 Comparator 클래스를 구현하여 넣어주어야 한다. TreeMap의 구현 레드 - ..
Interface List 공식 문서 https://docs.oracle.com/javase/8/docs/api/java/util/List.html List List는 Array(배열)와 비슷한 자료구조이다. 그런데 배열에는 몇 가지 단점들이 있다. 배열은 미리 크기를 지정하여 그 공간을 확보해 놓고 사용해야 하고, 그 크기를 변경할 수 없다. 이 크기를 조절할 수 없는 것이 가장 큰 단점이다. 그래서 List를 사용한다. List는 생성할 때 크기를 지정하지 않고, 값이 추가될 때마다 List의 크기가 커진다. LinkedList와 ArrayList List는 일반적으로 LinkedList, ArrayList를 사용한다. LinkedList와 ArrayList는 구조적으로 차이가 있다. 우선 Linke..
트라이(Trie) 트라이는 문자열을 저장하고, 빠르게 탐색하기 위한 트리 형태의 자료구조이다. 문자열 저장을 위한 메모리를 사용하지만, 탐색속도가 매우 빠르다. O(N) (Java에서 Queue,Stack,List와 다르게 Trie를 직접적으로 구현해놓은 라이브러리는 없다.) 트라이의 형태 Trie에 들어있는 문자열 apple, april bus, busy, beer, best 트라이의 구조(특징) 루트 노드 루트노드는 항상 비어있다. 루트노드의 자식노드는 각 단어들의 첫 글자들이다. endOfWord 표시 파란색으로 칠해져 있는 노드는 각 문자열의 마지막 글자이다. 각 노드 구성 각 노드의 자식노드들을 Map에 저장한다. 해당 노드가 단어의 마지막을 뜻하는 endOfWord를 저장할 boolean형 필..
우선순위 큐(Priority Queue) 우선순위 큐는 Queue와 비슷하지만, 선입선출 구조인 Queue와 달리 Queue에 들어있는 자료 중 우선순위를 설정하여 우선순위가 높은 순서대로 데이터를 꺼내는 구조이다. 큐에 들어오는 모든 데이터에 우선순위가 존재하며, 데이터를 꺼낼 때 우선순위가 높은 순서대로 나온다. 우선순위가 같은 경우에는 선입선출 방식을 따른다. 자바의 우선순위 큐는 힙(Heap) 방식으로 구현되어 있다. 아래 링크에 Heap에 대해 정리해 두었으니 확인하길 바란다. 2023.06.11 - [자료구조] - [JAVA/자료구조] 힙(Heap), 최소 힙(Min Heap), 최대 힙(Max Heap) 우선순위 지정 PriorityQueue는 생성할 때 우선순위를 지정해주어야 한다. 자바에..
힙(Heap) 힙은 완전 이진트리 형태로 최대, 최솟값을 빠르게 찾아내는데 유용한 자료구조이다. 힙은 중복값을 허용한다. 부모-자식 간 (레벨 별) 정렬은 보장하고, 형제간의 정렬은 보장하지 않아서 반 정렬 상태라고 볼 수 있다. 힙은 최소 힙(Min Heap), 최대힙(Max Heap) 두가지가 있다. 최소 힙은 루트노드가 최솟값이 되고, 부모노드의 key는 자식노드의 key보다 작아야 한다는 규칙이 있다. 최대 힙은 루트노드가 최댓값이 되고, 부모노드의 key가 자식 노드의 key보다 커야 한다는 규칙이 있다. 완전이진트리는 마지막 레벨을 제외하고 노드들이 가득 차 있는 트리를 말한다. https://innovation123.tistory.com/107 [JAVA/자료구조] 트리(Tree), 이진트리..
그래프(Graph) 그래프는 정점 와 간선로 이루어진 자료구조이다. 이는 트리(Tree)와 같지만, 트리는 Acyclic(사이클 x)인 반면 그래프는 사이클이 존재한다. (Cyclic) 각 정점(Vertex)들이 간선(Edge)들로 연결되어, 연결된 정점 간의 관계를 표현할 수 있는 자료구조이다. 그래프의 구조(용어) 정점(Vertex) : 노드 간선(Edge) : 각 노드간의 연결 선 ( = link, branch) 인접 정점(Adjacent Vertex) : 간선 하나만을 통해 바로 연결되어 있는 정점 (정점 1과 정점 4는 인접정점 x) 무방향 그래프 정점의 차수(Degree) : 하나의 정점에 인접한 정점의 수 (정점 1의 차수는 2 ), (정점 A의 차수는 3) 무방향 그래프에서 모든 정점 차수..
HashSet이란? HashSet은 Set 인터페이스를 구현한 클래스이며, 기초수학에서 집합과 같은 개념이다. 특이하게 합집합, 차집합, 교집합 등의 연산을 할 수 있다. List와 차이점은 중복을 허용하지 않는다는 점과, 인덱스(index)로 데이터를 다루지 않는다는 점이 있다. 가장 중요한 것은 역시 중복을 허용하지 않는다는 점인것 같다. HashSet 생성자 Set 인터페이스를 구현한 클래스이니 Set 형으로 선언해 줄 수 있다. 제네릭을 이용하여 데이터타입을 정의해주는 것이 좋다. HashSet set = new HashSet(); Set set = new HashSet(); 생성할 때 배열을 List로 변환하여 넣어주거나, List를 넣어서 생성할 수도 있다. Set setA = new Hash..
