한양과기고 에듀테크 수업도구 대시보드

로프 자료구조 (Rope)

메모장에서 100MB짜리 로그 파일을 열고 맨 앞에 글자 하나를 넣으면 어떻게 될까? 문자열을 하나의 긴 배열로 저장하면 뒤의 1억 글자를 전부 한 칸씩 밀어야 한다(O(n)). 로프는 긴 문자열을 작은 조각(잎)으로 쪼개 이진 트리로 매달아 둔다. 각 내부 노드는 왼쪽 서브트리의 글자 수(weight)만 들고 있어서, i번째 글자 찾기도, 중간에 글자 넣기도 트리 높이 O(log n) 만에 끝난다. 큰 배열 복사가 사라진다.

1. 로프 트리 직접 편집하기

파란 노드는 내부 노드(숫자 = weight, 왼쪽 서브트리 길이), 분홍 노드는 실제 글자를 담은 잎(leaf)이다. 삽입/삭제는 경계에 걸친 잎만 쪼개고 리스트를 잇는다 — 큰 문자열 복사 없음. 밑줄 _ 은 공백을 뜻한다.

삽입할 글자

위치 i

삭제 start

삭제 end

index(i) 조회

준비 완료. 버튼을 눌러 로프를 편집해 보자.

2. i번째 글자는 어떻게 찾을까? — weight로 길 찾기

루트에서 시작해 각 내부 노드에서 딱 한 번만 비교한다.

weight와 비교

i < node.weight 이면 찾는 글자는 왼쪽 서브트리 안에 있다. 그대로 왼쪽으로 내려간다.

오른쪽이면 i 보정

i ≥ node.weight 이면 오른쪽으로 가되, 왼쪽을 건너뛰었으니 i -= node.weight 로 좌표를 옮긴다.

잎에 도착

잎에 닿으면 남은 i 로 leaf.text[i] 를 바로 반환. 방문 노드 수 = 트리 높이.

왜 weight만 저장할까? 오른쪽 서브트리 길이는 필요 없다. 부모가 이미 "여기부터는 내 담당"이라고 좌표를 넘겨줬기 때문. 삽입·삭제 때도 조상 노드의 weight 몇 개만 갱신하면 된다.

3. 한 덩어리 문자열 vs 로프

연산	평면 문자열 (배열)	로프 (균형 트리)
i번째 글자 읽기 `charAt`	O(1)	O(log n)
중간에 삽입 `insert`	O(n) — 뒤 전체 밀기	O(log n)
중간 구간 삭제 `delete`	O(n)	O(log n)
두 문자열 잇기 `concat`	O(n + m) 복사	O(1) — 새 루트 하나
부분 문자열 `substring`	O(길이) 복사	O(log n) — 조각 공유
메모리 지역성 / 캐시	연속 → 빠른 스캔	포인터 점프 → 조각화
구조 자체 오버헤드	없음	노드마다 포인터·weight

로프의 약점은 캐시 지역성과 노드 오버헤드다. 그래서 잎을 1글자로 쪼개지 않고 수백~수천 글자 덩어리로 두고, 트리가 한쪽으로 치우치면 재균형(AVL·splay 등)한다. 오늘날 편집기는 로프 외에 gap buffer(커서 근처에 빈 칸을 두는 방식)나 piece table(원본 + 추가분을 조각 목록으로 참조)도 많이 쓴다.

4. 핵심 연산 (의사 코드)

# 잎 노드: 실제 문자열 조각 / 내부 노드: 왼쪽 길이(weight)만 보관 class Leaf: text class Node: left, right, weight # weight = len(left 서브트리) def index(node, i): while not node.is_leaf: if i < node.weight: node = node.left else: i -= node.weight # 왼쪽을 건너뛴 만큼 좌표 이동 node = node.right return node.text[i] def concat(a, b): return Node(left=a, right=b, weight=length(a)) # O(1) def split(node, i): # i번째 글자 앞에서 로프를 (왼쪽, 오른쪽) 두 로프로 자른다 -> O(log n) # 경계에 걸친 잎 하나만 두 조각으로 나눈다 ... def insert(root, i, s): left, right = split(root, i) return concat(concat(left, Leaf(s)), right) # 큰 복사 없음