로프(Rope) 자료구조 계산기
문자열을 이진트리로 쪼갠 로프에서 자르기(split)·이어붙이기(concat)·중간 삽입이 실제로 어떻게 되는지 계산해 보여줍니다. 텍스트 에디터가 대용량 문서를 빠르게 편집하는 원리입니다.
이 크기로 잘라 균형 트리를 만듭니다
트리 높이
4단계
조각 9개 → log₂(9) ≈ 3.17. index·split은 이 높이만큼만 내려가면 됩니다.
split — 한 위치에서 둘로 자르기
insertAt — split 두 번 + concat 두 번
삽입 결과
the quick [여기]brown fox jumps over the lazy dog
일반 문자열의 slice+concat 결과와 항상 같습니다.
사용 방법
- 1텍스트를 입력하고 조각 크기를 정합니다 — 그 크기로 잘게 나눠 균형 트리를 만듭니다.
- 2트리의 높이(잎까지 최대 깊이)를 확인합니다.
- 3자를 위치를 입력해 split이 만드는 두 조각을 확인합니다.
- 4삽입 위치와 삽입할 문자열을 입력해 insertAt 결과를 확인합니다.
자주 묻는 질문
일반 문자열 중간에 글자를 끼워 넣으면 그 뒤쪽 전체를 복사해야 해 O(n)이 걸립니다. 로프는 문자열을 이진트리로 쪼개 두고, 중간에 끼워 넣을 때 지나가는 경로의 노드만 새로 만들면 되므로 O(log n)에 끝납니다. 텍스트 에디터가 기가바이트급 문서에서도 매끄럽게 편집되는 이유입니다.
두 로프를 이어붙이는 concat(A, B)는 새 가지 노드 하나를 만들어 왼쪽에 A, 오른쪽에 B를 매다는 것뿐입니다. A·B의 내용을 복사하지 않으므로 A·B의 크기와 무관하게 O(1)입니다.
자를 위치가 속한 잎까지 트리를 타고 내려가 그 잎만 둘로 쪼개고, 지나온 가지들만 다시 얽습니다. 손대지 않은 서브트리는 그대로 재사용(공유)하므로 지나온 경로 길이, 즉 트리 높이만큼만 일합니다. 트리가 균형 잡혀 있으면 이 높이가 O(log n)입니다.
가지(concat) 노드마다 왼쪽 서브트리에 담긴 글자 수를 저장합니다. i번째 글자를 찾을 때 i가 weight보다 작으면 왼쪽으로, 아니면 i에서 weight를 뺀 뒤 오른쪽으로 내려가면 됩니다. 이 숫자 하나로 충분히 길찾기가 됩니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.
알아두면 좋은 점
- Boehm, Atkinson, Plass, "Ropes: An Alternative to Strings"(1995)의 표준 정의(잎에 문자열 조각, 가지에 왼쪽 서브트리 길이)를 그대로 구현했습니다.
- 임의 위치에서 잘라 다시 이어붙이면 원본 문자열로 정확히 돌아오는 것(왕복 검증), 모든 위치의 charAt이 원본 문자열의 같은 위치와 일치하는 것, 균형 트리의 높이가 log2(조각 수)와 같은 것을 테스트로 확인했습니다(2026-09-05).
- 이 계산기가 만드는 트리는 항상 균형이 잡혀 있습니다(조각을 절반씩 나눠 짓기 때문). 실전 구현은 편집이 누적되면 균형이 무너질 수 있어 주기적으로 재균형을 잡습니다 — 이 계산기는 재균형 로직까지는 다루지 않습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 5일 · 결과는 참고용 추정치입니다.