나의개발일지

📌 Set이란?오늘은 Set에 대해서 알아보자 일단 자바 DOC 를 보자 Set는 중복을 허용하지 않는 컬렉션 이다수학적 집합(Set) 개념을 모델링 한것 원칙e1.equals(e2)를 만족하는 두 요소(e1, e2)를 동시에 가질 수 없다.최대 하나의 null 요소만 허용한다. 주의 사항Set에 변경 가능한 객체(mutable object)를 요소로 사용할 때는 조심해야 한다.Set에 들어간 객체의 값이 변경되어 equals() 결과가 바뀌면, Set의 정상 동작이 보장되지 않는다.예외적으로 Set 자신(Set 객체 본인) 을 자신의 요소로 추가하는 것도 금지된다. 📌 HashSetHashSet은 Set 인터페이스를 구현한 클래스이다 내부적으로 HashMap 인스턴스를 이용해 데이터를 저장한다중복을..

📌 Red-Black 삭제요번 포스팅에서는 레드-블랙 트리의 삭제에 대해 알아보자. 이전 포스트에서도 말했듯이 레드-블랙 트리는 이진 탐색 트리 중에서 균형을 보장하는 대표적인 자료구조이다. 삭제하기전 알아야 할 개념- Extra Black삭제시 필요한 개념으로 노드에 임시로 부여 할 수 있다. - Doubly BlackBlack 노드에 Extra Black이 붙은 경우이다. - Red-and-BlackRed 노드에 Extra Black이 붙은 경우이다. - Successor오른쪽 서브트리에서 가장 작은 값 ❗ 레드-블랙 트리에서 삭제 대상 노드가 자식 들을 가질 경우, 실제로 삭제되는 노드는 successor이다 레드-블랙 트리 삭제의 흐름삭제할 노드를 찾는다.자식이 둘이면 successor와 교체..

📌 Red-Black 트리란?레드-블랙 트리는 이진 탐색 트리의 한 종류 이며 일반적인 BST의 worst case(한쪽으로 편향)의 단점을 개선한 트리이다.레드-블랙 트리는 스스로 균형을 잡으며 모든 노드는 red 혹은 black이다.  레드 블랙 트리의 속성모든 노드는 red 혹은 black루트 노드는 black모든 nil 노드는 blackred의 자녀들은 black -> red가 연속적으로 존재할 수 없다.임의의 노드에서 자손 nil 노드 까지 가는 경로들의 black수는 같다 (자기 자신 제외) nil 노드존재하지 않음을 의미하는 노드이고 레드 블랙 트리에서 leaf 노드를 nil노드로 표기한다.  시간복잡도이진 탐색트리와 레드 블랙 트리의 시간 복잡도를 보면 레드 블랙 트리는 최악의 경우 O(..