풀소유

자가 균형 이진 탐색 트리의 일종으로, 데이터베이스와 파일 시스템에서 널리 사용된다.높은 차수의 균형 트리로, 각 노드가 여러 자식을 가질 수 있다.모든 리프 노드는 동일한 레벨에 존재하기 때문에, B 트리는 O(logN)의 시간 복잡도를 갖는다. 특징각 노드는 최대 M개의 자식을 가질 수 있다. 이러한 트리를 M차 B 트리라고 부른다.루트 노드를 제외한 모든 노드는 최소 ⌈M/2⌉개의 자식을 가져야 한다.노드는 데이터와 포인터로 구성되며, 데이터는 오름차순으로 정렬되어 있다. 정렬된 순서에 따라 자녀 노드들의 키 값의 범위가 결정된다.각 노드는 최대 ⌈M/2⌉ - 1개에서 최대 M - 1개의 키를 가질 수 있다. 데이터 삽입삽입은 항상 리프 노드에서 시작한다.해당 리프 노드에 여유 공간이 있다면 데이터..

Red-Black 트리는 이진 탐색 트리(BST)의 한 종류로, 스스로 균형을 유지하는 트리이다. 이 트리는 이진 탐색 트리에서 발생할 수 있는 최악의 경우(한쪽으로 치우친 트리)를 개선하여, 모든 연산(삽입, 삭제, 검색)이 O(log n) 시간 복잡도를 가지도록 설계되었다.  nil 노드nil 노드는 트리에서 존재하지 않는 자식을 나타내기 위해 사용되며, 이는 모든 리프 노드(자녀가 없는 노드)를 나타내는 데 사용된다.Red-Black 트리에서는 nil 노드도 블랙으로 간주되며, 트리의 균형을 유지하는 데 중요한 역할을 한다. Black HeightBlack Height는 노드 x에서 자손 nil 노드까지의 경로에 있는 블랙 노드의 수를 의미한다. 이때 x 자신도 이 수에 포함된다.  Red-Blac..

AVL 트리는 이진 탐색 트리의 한 종류로, 엄격하게 스스로 균형을 유지하는 트리이다.각 노드의 균형 인수(balance factor, BF)를 사용하여 균형을 유지하며, 모든 노드의 BF 값은 -1, 0, 1 중 하나이다.장점:트리의 높이가 O(log n)으로 유지되어, 검색, 삽입, 삭제 연산의 시간 복잡도가 O(log n)이다.균형을 유지하므로 최악의 경우에도 성능이 일정하다.단점:엄격하게 균형을 유지하기 때문에 삽입/삭제 시 트리 균형을 확인한다.균형이 깨졌을 시 재조정하기 때문에 시간이 꽤 소요된다. 균형 인수 (Balance Factor)임의의 노드 x에 대해 균형 인수는 x의 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다.BF(x) = x의 왼쪽 서브트리의 높이 - x의 오른쪽..

이진 탐색 트리는 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값이, 오른쪽 서브트리에는 큰 값이 저장되는 이진트리이다.중위 순회를 통해 이진 탐색 트리의 모든 노드를 오름차순으로 정렬된 형태로 방문할 수 있다.장점삽입 삭제가 유연하다.이진 탐색 트리의 구조 덕분에 검색 연산이 빠르다.노드를 추가하거나 삭제할 때 트리의 크기가 동적으로 조절된다.단점트리가 불균형해지면, 최악의 경우 성능이 O(n)으로 떨어질 수 있다.이진 탐색 트리는 간단하고 효과적인 자료구조지만, 균형을 유지하지 않으면 성능이 저하될 수 있다. 따라서 균형을 유지하는 변형 트리(예: AVL 트리, 레드-블랙 트리 등)를 사용하여 성능을 보장할 수 있다. 후임자 (Successor)정의: 특정 노드보다 값이 큰 노드들 중에서 가장 작..

Set의 주요 특징중복된 데이터를 허용하지 않음: Set은 중복된 요소를 저장하지 않으며, 데이터의 유일성을 보장한다. 동일한 값을 여러 번 저장하려고 시도해도 단 하나의 값만 저장된다.순서 보장 안 됨: Set은 요소의 순서를 보장하지 않는다. 데이터의 삽입 순서와 상관없이 요소들이 저장되며, 순서가 중요한 경우에는 다른 컬렉션을 사용하는 것이 좋다.빠른 조회 성능: Set은 데이터를 검색할 때 평균적으로 O(1)의 시간 복잡도를 가진다. 이는 해시 테이블을 사용하기 때문이다. 다만, TreeSet의 경우에는 O(log n)의 시간 복잡도를 가진다.메모리 사용: Set은 해시 테이블을 사용하여 데이터의 유일성을 보장하는데, 이는 추가적인 메모리 오버헤드를 발생시킬 수 있다. 특히, LinkedHashS..