Gap Buffer 자료구조 간단히 알아보기
효율적인 삽입 및 삭제 작업을 위한 배열
Gap Buffer 란 위키피디아에서 아래와 같이 정의하고 있습니다.
동일한 위치 근처에 클러스터링된 효율적인 삽입 및 삭제 작업을 허용 하는 동적 배열 입니다.
이는 텍스트 편집기와 같은 동일 위치에서 삽입 및 삭제 작업이 빈번하게 발생되는 환경에서 자주 사용되는 자료구조 입니다. 예를 들어 이 작업을 일반 배열로 했다고 가정해 봅시다. 그럼 텍스트 삽입이 일어날 때 마다 인덱스를 조정하느라 O(N) 의 시간이 소요될 것입니다. 하지만 갭 버퍼를 이용하여 텍스트를 저장한다면 O(1) 만에 가능합니다.
갭 버퍼의 작동 원리에 대해 보겠습니다. 먼저 사용할 공간들을 확보하는 작업이 필요합니다. 이 작업은 인덱스를 확장하느라 O(N) 이 걸리고, 이렇게 확보된 공간을 Gap 이라고 부릅니다.
_ 는 Gap, (v) 는 현재 cursor 를 나타냄[(v)_, _, _, _, _, _, _, _, _, _]
Hi 글자를 삽입해 보겠습니다. 이 작업은 모두 Gap 에서 진행됨으로 O(1) 에 완료됩니다.
[(v)H, i, _, _, _, _, _, _, _, _]첫 번째 인덱스에 있는 i 를 제거해 보겠습니다. 커서를 i 가 있는 위치로 옮기기 위해 O(N) 이 걸리고, 이후 Gap 에서 값 제거가 진행되므로 O(1) 에 완료됩니다. 값 제거는 해당 값을 Gap 으로 바꾸는 것으로 진행됩니다.
[H, (v)_, _, _, _, _, _, _, _, _]마지막으로 H 를 Bye 로 변경해 보겠습니다. 커서를 H 가 있는 위치로 옮기기 위해 O(N) 이 걸리고, 이후 모두 Gap 에서 값 업데이트가 진헹되므로 O(1) 에 완료됩니다.
[(v)B, y, e, _, _, _, _, _, _, _]
Gap Buffer 에 대한 자세한 설명 및 구현은 여기를 참고해 주세요. 감사합니다.
안드로이드 개발자 분들을 위한 카카오톡 오픈 채팅방을 운영하고 있습니다.
