크기
비교 횟수

연산 평균 최악

자료구조에 대한 자세한 정보

자료구조 시각화

자료구조는 가장 자주 묻는 질문에 빨리 답할 수 있도록 데이터를 담아 두는 방법입니다. 스택부터 레드-블랙 트리까지 고전적인 구조 열한 가지 중 하나를 고르고, 값을 입력한 다음 연산을 누르세요. 어느 노드를 비교하는지, 어느 링크가 바뀌는지, 트리가 왜 회전하고 값이 왜 올라가는지가 무슨 일이 일어나는지 알려 주는 문장과 함께 화면에서 한 단계씩 펼쳐집니다. 타일은 각 연산이 한 일을 세고, 표는 실행 시간을 보여 줍니다. 구조를 고르고 값을 입력한 다음 연산을 누르세요. 모든 연산은 한 단계씩 재생됩니다. 강조된 노드는 무엇이 비교되고 옮겨지고 바뀌는지 보여 주고, 그림 아래 줄은 무슨 일이 왜 일어나는지 알려 줍니다. 이전, 단계, 재생, 끝으로 단계를 다시 살펴볼 수 있습니다. 무작위 채우기와 지우기는 처음부터 다시 시작하고, 실행 취소는 연산 하나를 되돌립니다. 타일에는 크기, 트리의 높이, 마지막 연산이 한 일(비교, 탐사, 따라간 부모 링크 수)과 그 구조에서 중요한 수치가 표시되고, 표에는 각 연산의 실행 시간이 나옵니다.

작동 원리

  1. 이진 탐색 트리, 해시 테이블, 트라이 같은 구조를 고르세요. 처음에는 무작위 내용이 들어 있으며, 무작위 채우기와 지우기로 다시 시작할 수 있습니다.
  2. 값을 입력하고 연산을 누르세요. 푸시, 인큐, 삽입, 삭제, 검색, 순회, Union, Find 등이 있습니다. 단계는 저절로 재생되고, 이전, 단계, 재생, 끝으로 다시 볼 수 있습니다.
  3. 그림 아래 줄에서 각 단계가 하는 일을 읽고, 타일에서 크기, 높이, 마지막 연산이 한 일을 확인한 뒤, 표에서 실행 시간을 비교해 보세요.

리스트, 스택, 큐

가장 단순한 구조는 원소를 한 줄로 놓습니다. 스택은 한쪽 끝에서만 일하므로 마지막에 넣은 원소가 가장 먼저 나옵니다. 쌓아 둔 접시와 같습니다. 큐는 뒤에 넣고 앞에서 꺼냅니다. 창구 앞의 줄과 같습니다. 여기의 큐는 원형 버퍼에 들어 있습니다. 앞과 뒤가 고정된 배열을 돌다가 끝을 지나면 처음으로 돌아오고, 버퍼가 가득 차면 원소들을 두 배 크기의 버퍼로 복사합니다. 연결 리스트는 노드를 포인터로 잇기 때문에 헤드에 넣는 데는 거의 비용이 들지 않지만, 꼬리나 어떤 인덱스를 찾으려면 링크를 하나씩 따라가야 합니다.

트리, 힙, 해시 테이블, 집합

이진 탐색 트리는 작은 값을 왼쪽에, 큰 값을 오른쪽에 두므로, 트리가 무성하게 유지되는 한 검색은 단계마다 후보를 절반으로 줄입니다. AVL 트리와 레드-블랙 트리는 회전으로 이를 지켜 줍니다. 그 회전은 눈으로 볼 수 있고, 경우마다 이름이 있습니다. 힙은 가장 작거나 가장 큰 값만 맨 위에 두며, 우선순위 큐에 필요한 것은 그것뿐입니다. 해시 테이블은 키에서 계산한 버킷으로 곧장 뛰어가며 충돌을 처리해야 합니다. 트라이는 단어의 접두사를 공유하고, 유니온-파인드는 두 원소가 같은 집합에 속하는지 거의 상수 시간에 알려 줍니다.

자주 묻는 질문

어떤 자료구조를 써야 하나요?

가장 자주 묻는 질문에 달려 있습니다. 원소를 도착한 순서나 그 반대로 처리한다면 스택이나 큐, 키를 찾으려면 해시 테이블, 키를 순서대로 꺼내거나 가장 가까운 키도 필요하다면 AVL 트리나 레드-블랙 트리 같은 균형 탐색 트리, 늘 가장 작거나 큰 원소만 필요하다면 힙, 단어와 접두사에는 트라이, 합쳐지는 그룹을 추적하려면 유니온-파인드가 알맞습니다.

AVL 트리와 레드-블랙 트리는 무엇이 다른가요?

둘 다 이진 탐색 트리를 얕게 유지하므로 검색, 삽입, 삭제 모두 log n에 비례하는 시간이 걸립니다. AVL 트리는 더 엄격하게 균형을 잡아 모든 노드의 양쪽 높이 차가 1 이내이므로 검색이 조금 더 빠릅니다. 레드-블랙 트리는 여유를 더 허용하고 바뀔 때 필요한 회전이 적어서, 많은 표준 라이브러리가 정렬된 맵과 셋에 이를 씁니다.

해시 테이블은 왜 최악의 경우 느려질 수 있나요?

많은 키가 같은 버킷에 들어가면 검색은 그것들을 하나씩 확인해야 하므로 리스트와 다를 바 없습니다. 좋은 해시 함수는 키를 고르게 흩뜨리고, 테이블은 너무 차기 전에 커지므로 검색은 평균적으로 상수 시간이 걸립니다. 테이블 크기를 10으로 하고 같은 숫자로 끝나는 수나 서로 애너그램인 단어를 넣어, 충돌이 쌓이는 모습을 보세요.

AVL 노드 옆의 숫자는 무엇인가요?

균형 인수입니다. 노드의 왼쪽 서브트리 높이에서 오른쪽 서브트리 높이를 뺀 값입니다. AVL 트리에서는 모든 균형 인수가 −1, 0, +1 중 하나여야 합니다. 삽입이나 삭제로 그중 하나가 +2나 −2가 되면 트리가 그 노드에서 회전합니다. 경우(LL, RR, LR, RL)는 남는 높이가 어느 쪽으로 기울었는지 알려 주며, 회전이 한 번인지 두 번인지를 정합니다.

서버로 무언가가 전송되나요?

아니요. 모든 연산은 브라우저에서 실행되며, 각 구조의 내용은 이 브라우저의 로컬 저장소에 저장됩니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동