검색·삽입·합계에 맞는 자료구조 관찰하기
자료를 담는 그릇을 바꾸면 비용이 큰 연산도 달라집니다. 같은 값을 추가하고, 찾고, 지우는 동안 어떤 위치를 다시 방문하는지 살펴보세요.
툴허브 편집 ·
맨 먼저 넣은 값의 출구 찾기
A, B, C를 차례로 넣은 뒤 한 번 꺼내 보세요. 스택에서는 C, 큐에서는 A가 나오는 순서를 실행 취소 기록과 대기 줄에 연결해 봅니다.
스택 & 큐 열기 →중간 노드에 닿는 길 세기
세 번째 노드의 값을 보려면 앞에서 링크를 따라가야 합니다. 이미 위치를 아는 노드 뒤에 삽입할 때 어떤 연결을 갱신하는지 확인하세요.
연결 리스트 열기 →같은 위치를 가리키는 키 구분하기
서로 다른 키가 같은 버킷으로 들어가는 순간을 찾아보세요. 해시가 같아도 실제 키가 같은지 확인해야 조회 결과를 구분할 수 있습니다.
해시테이블 열기 →입력 순서로 트리 높이 바꿔 보기
1, 2, 3을 차례로 넣을 때와 2, 1, 3 순서일 때를 비교하세요. 같은 값이 있어도 검색할 때 지나가는 노드 수가 달라집니다.
이진탐색트리 (BST) 열기 →회전 전후에도 정렬 순서 보존하기
치우친 가지가 회전할 때 루트로 올라오는 값을 보세요. 회전 뒤 중위 순회 순서는 같고 왼쪽과 오른쪽의 높이 차이는 줄어듭니다.
AVL 트리 열기 →색 변경과 회전 구별하기
노드를 넣은 직후 빨간 부모와 빨간 자식이 이어지는 경우를 찾아보세요. 색만 바뀌는 단계와 구조까지 다시 잇는 단계를 나눠 관찰합니다.
레드-블랙 트리 열기 →가득 찬 노드에서 위로 올라가는 키 보기
노드 하나에 여러 키가 정렬되어 있는 모습을 먼저 보세요. 분할 시 가운데 키가 부모로 올라가면 두 자식이 담당하는 값 범위도 갈라집니다.
B-트리 열기 →최댓값이나 최솟값을 뺀 자리 복구하기
루트를 제거한 자리에 끝 값을 올렸을 때 어느 자식과 바꾸는지 살펴보세요. 힙은 부모와 자식 사이의 순서를 보장하므로 같은 층 전체가 정렬될 필요는 없습니다.
힙 (우선순위 큐) 열기 →구간 합 하나를 몇 개의 노드로 읽는지 보기
일부만 겹치는 노드는 둘로 내려가고 완전히 포함되는 구간에서는 저장한 값을 사용합니다. 원소 하나를 바꿨을 때 영향을 받는 조상 노드도 따라가 보세요.
세그먼트 트리 열기 →두 누적 합의 차이로 가운데 구간 얻기
1번부터 5번까지의 합에서 1번부터 2번까지의 합을 빼면 3~5번의 합입니다. 두 누적 합을 읽을 때 실제로 방문하는 인덱스를 살펴보세요.
펜윅 트리 (BIT) 열기 →‘없음’과 ‘있을 수 있음’ 구분하기
키를 넣고 해시가 가리키는 비트를 관찰하세요. 다른 키가 우연히 같은 비트를 쓰면 삽입하지 않았어도 조회가 양성으로 나올 수 있습니다.
블룸 필터 열기 →