Rope

Rope

긴 문자열을 작은 조각들로 나누어 이진 트리로 구성하는 자료구조로, 문자열 연결·삽입·삭제를 O(log n) 시간에 수행하여 대용량 텍스트 편집에 최적화

목적: 효율적 문자열 편집, 빠른 연결·삽입·삭제, 대용량 텍스트 관리

특징: 이진 트리, 문자열 조각, O(log n) 편집, 불변 부분 공유

구조: 리프 노드 = 짧은 문자열 조각, 내부 노드 = 왼쪽+오른쪽 길이 합, 루트 = 전체 문자열

연산

• •concat(s1, s2): 새 루트 생성, 왼쪽=s1, 오른쪽=s2, O(1)
• •split(i): i번째 위치에서 분할, O(log n)
• •insert(i, s): split(i) → concat(left, s) → concat(result, right), O(log n)
• •delete(i, j): split 2회 → concat, O(log n)
• •index(i): i번째 문자 접근, O(log n)

시간 복잡도: concat O(1), split·insert·delete O(log n), index O(log n)

공간 복잡도: O(n)

장점: 빠른 연결(O(1)), 효율적 편집(O(log n)), 부분 공유(메모리 절약), Undo/Redo 용이

단점: 인덱스 접근 느림(O(log n)), 구현 복잡도, 오버헤드(작은 문자열)

적용사례: 텍스트 에디터(Emacs, Xi), 코드 편집기, 버전 관리, 협업 편집(CRDT)

비교: Rope(O(log n)편집/트리) vs String(O(n)편집/배열) vs Gap Buffer(O(1)지역편집)

연관: 문자열, 이진 트리, 텍스트 에디터, 불변 자료구조