삽입·삭제·탐색을 단계별로 재생하며 자료구조가 어떻게 동작하는지 눈으로 확인해 보세요.
각 자료구조마다 작은 챌린지가 준비되어 있어요.
연속된 메모리에 값이 나란히 저장됩니다. 인덱스로 즉시 접근하지만, 중간 삽입·삭제 시 뒤 원소들이 한 칸씩 밀리거나 당겨집니다.
각 노드가 다음 노드를 가리키는 next 포인터 하나만 가집니다. 맨 앞 삽입은 O(1)이지만, 특정 위치를 찾으려면 head 부터 순회해야 합니다.
각 노드가 next 와 prev 포인터를 모두 가져 양방향 순회가 가능합니다. 노드를 삭제하면 앞뒤 노드의 포인터를 서로 다시 연결해야 합니다.
왼쪽 자식은 부모보다 작고, 오른쪽 자식은 큽니다. 균형이 맞으면 탐색이 O(log n)이지만, 정렬된 값을 순서대로 넣으면 한쪽으로 치우쳐 O(n)이 됩니다.
삽입할 때마다 모든 노드에서 양쪽 높이 차(균형 인수)를 ±1 이내로 유지하는 자가 균형 BST입니다. 균형이 깨지면 LL·RR·LR·RL 회전으로 즉시 복구해 항상 O(log n)을 보장합니다.
노드를 빨강/검정으로 칠하고 규칙(빨강 연속 금지, 모든 경로의 검정 수 동일)을 지켜 균형을 유지합니다. 삽입 후 빨강이 연속되면 재색칠하거나 회전해 복구합니다.
한 노드가 키 1~2개와 자식 2~3개를 가질 수 있는 균형 트리입니다. 노드가 키 3개로 가득 차면 분할되어 가운데 키가 위로 올라가고, 모든 리프는 항상 같은 깊이에 있습니다.
한 노드에 여러 키를 담아 트리를 낮고 넓게 유지합니다(여기선 자식 최대 5개, 키 최대 4개). 디스크·DB 인덱스에 쓰이며, 노드가 가득 차면 분할되어 가운데 키가 위로 전파됩니다.
실제 값은 모두 리프에만 저장하고 내부 노드는 분기용 분리키만 가집니다. 리프끼리 연결되어 범위 검색이 빠르며, DB 인덱스의 사실상 표준입니다.